파이썬

[python] 백준 - 7562. 나이트의 이동

🤔문제 해결 S2 | BFS BFS로 다 돌아주다가 도착지를 만나면 끝! 💻소스 코드 from collections import deque def bfs(): q = deque() q.append((start_x, start_y)) while q: cx, cy = q.popleft() if cx == end_x and cy == end_y: print(chess[cx][cy]) return for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0

크루스칼 알고리즘(kruskal)

📔 크루스칼(kruskal) 이란 간선을 하나씩 선택해서 MST를 찾는 알고리즘 ( 프림은 정점을 선택, 크루스칼은 간선을 선택 ) 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다 사이클이 존재하면 패쓰 ( 사이클의 존재를 파악하는게 중요! ) V-1개의 간선이 선택될 때 까지 반복 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 disjoint-set 알고리즘을 이용한다. 📔 크루스칼(kruskal) 구현 def make_set(x): p[x] = x def find_set(x): if p[x] == x: return x else: p[x] = find_set(p[x]) return p[x] def union(x, y): px ..

너비 우선 탐색(Breath First Search, BFS)

📔 너비 우선 탐색(BFS) 이란 너비를 우선으로 하여 탐색을 수행하는 알고리즘 최단경로(최단길이)를 찾을 때 주로 사용한다. 큐와 그래프로 해결한다. (파이썬에서는 데크(deque)를 쓰면 속도가 빠름) 📔 너비 우선 탐색(BFS) 구현 from collections import deque # 인접리스트 # 노드: 1,2,3,4,5,6,7 n = 7 adj = {x: [] for x in range(1, n + 1)} edges = [ [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7] ] # 무방향 그래프이므로 반대쪽도 성립 for edge in edges: s, e = edge adj[s].append(e) adj[e].append(s) print(adj) # bfs..

계수 정렬(counting sort)

📔 계수 정렬(counting sort) 이란 작은 범위 조건이 있는 경우에 한해서 빠른 알고리즘 시간복잡도: O(N), 최악의 경우 O(N^2) 크기를 기준으로 갯수만 세주면 된다. 비교정렬 X 📔 계수 정렬(counting sort) 구현 N = 5 # 5 이하인 수들을 정렬해라 numbers = [1, 2, 3, 4, 5, 1, 1, 2, 3, 4, 5, 3, 3, 2, 1, 2, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5] print(f'정렬 전: {numbers}') count_list = [0] * (N + 1) for number in numbers: count_li..

[python] 백준 - 4883. 삼각 그래프

🤔문제 해결 S1 | 다이나믹프로그래밍 최소가중치? 라고 생각해서 별 생각없이 다익스트라로 풀었더니 바로 시간초과 다시 읽어보니 경로가 각 지점마다 단순해서 다이나믹프로그래밍으로 푸는 문제였다. 문제에서 주어진 삼각그래프와 똑같은 크기의 2차원리스트를 만든다. 리스트의 각 요소는 i,j에 도달 할 때의 가장 최솟값을 저장한다. 이제 dp 값을 저장하는 방법을 설명하면 먼저 1행까지는 직접 값을 채워 넣고, 나머지는 for문을 돌린다. (1,0): (0,1)에서 오는 값 (1,1): (0,1), (1,0)에서 오는 값 (1,2): (0,1), (1,1), (0,1)+(0,2) 에서 오는 값 여기서 중요한건 노란색으로 표시한 저 부분이다. 문제에서 각 노드의 가중치는 정수이다. 다시 말해서 음수가 포함되어 ..

[python] 프로그래머스 - N-Queen

🤔문제 해결 Lv3 | 백트래킹, DFS 규칙은 체스말의 좌우, 위아래, 대각선 모두 겹치지 않게 하는 것이다! 하지만 모든 규칙을 하나하나 체크하면 효율성 마지막에서 시간초과가 발생한다! 위아래 규칙: visited 리스트를 만들어서 세로(열) 한칸에 하나씩만 들어갈 수 있게 한다. 좌우 규칙: 한번 말을 놓으면 무조건 다음 행으로 넘어간다. 대각선 규칙: 말을 놓을 준비를 하고, 그 자리의 왼쪽 위대각선과, 오른쪽 위대각선에 말이 있는지 체크! 마지막 행까지 말을 둘 수 있으면 성공! 💨 💻소스 코드 def solution(n): answer = 0 chess = [[0] * n for _ in range(n)] # 체스판 visited = [0] * (n + 1) # 세로칸 방문 체크 # 조건에 일..