Dev Note

이해도 ★★★☆☆ 문제 접근방법 [공통] 함수에서 이차원 배열과 시작점의 x 및 y 좌표를 파라미터로 사용한다. 델타 탐색으로 진행한다. 이차원의 visited 배열(0 또는 False)을 만들어 방문처리한다. 벽을 빠져나가지 않도록 처리한다.(추가 벽을 세우거나, 델타 범위를 제한한다.) [다양한 방식] 1. DFS 사용 1-1. 스택 사용하여 반복문으로 구현 1-2. 재귀함수로 구현 2. DFS 사용하지 않고 구현(스택.pop()대신 좌표를 감소시킴) 나의 코드 스택 사용한 반복 DFS 구현 def dfs(board, start): visited = [[False] * N for _ in range(N)] stack = [start] while stack: curr = stack.pop() visit..

분할정복 알고리즘 유형중에 분할정복 유형이 있다. 문제를 부분 문제로 나누어 각 부분 문제를 해결하고, 부분 문제들의 결과를 합쳐 기본 문제를 해결하는 유형이다. 정렬 알고리즘에서 합병정렬과 퀵정렬이 이에 속하는데, 합병 정렬에 대해 알아보고자 한다. 합병정렬 크게 세 부분으로 생각하면 된다. 1. 나눈다. 2. 정복한다. 3. 합친다. 1. 나눈다. 리스트를 절반씩 나눈다. 이를 재귀적으로 실행하기 때문에 계속해서 절반씩 나누어진다. 그림에서 1~3번째 줄 과정이다. 2. 정복한다. 1.나눈다 와 같은 함수라고 보면 된다. 나누다가 길이가 1이 된다는 것은 더 이상 나눌 수 없을 뿐더러 '정렬'된 상태라는 것이다. 그러므로 이 때 결과를 return 한다. 그림에서 4번째, 가운데 과정이다. 3. 합친..

+ 추가가능한 부분 [순열] 서로 자리를 바꾸어 순열을 만드는 알고리즘으로 시간복잡도 최소화 [조합] n개에서 r개를 택할 때, r의 갯수를 하나씩 줄여가며 재귀로 푸는방식 (nCr = n-1Cr-1 + n-1Cr 활용) 순열(Permutation)과 조합(Combination) 순열 : 서로 다른 n개의 원소를 가진 집합에서 r개를 선택하여 순서대로 배열한다. 조합 : 서로 다른 n개의 원소를 가진 집합에서 r개를 선택하여 그룹을 만든다. 차이점은 순열은 수를 뽑은 후 순서를 생각해야 하지만 조합은 뽑은 것으로 끝난다는 것이다. 내장 패키지 모듈 또는 재귀로 구현할 수 있다. 순열은 어느정도 이해가 되었는데 조합은 조건부분을 아직 완전히 이해하진 못했다. 내장 패키지 모듈 사용 - 순열 from ite..

최단 경로란? 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 1. 다익스트라 알고리즘(Dijkstra) 음의 가중치를 허용하지 않는다. 어떤 경로로 가는게 효율적일까? 특정 시작점에서 도착점까지의 최소거리를 구하자. 시작점 0, 나머지는 INF 무한대로 배치. 갈래길을 가기 위해 cost에 원래값(현재 위치의 cost)에 앞으로 갔을때의 갚을 덮어씌운다. (갱신이 아닌 누적) 하나의 노드가 끝나면, 그 다음으로 cost가 가장 작은 node로 간다. 방문하지 않은 노드로 가는데 cost에 더해주고, 기존의 길과 비교해서 더 작은 길을 선택한다. 가장 cost가 작은 노드로 시작한다. 방문체크하고, 방문하지 않은..

서로소 집합 서로소(상호배타) 집합(Disjoint-sets) 서로소 또는 상호배타 집합이란 서로 중복 포함된 원소가 없는 집합, 교집합이 없는 집합이다. 집합에 속한 하나의 특정 멤버(대표)로 집합을 구분하며 이를 대표자(representative)라 한다. 상호배타 집합 연산 Make-Set(x) : x 를 대표로 하는 집합을 만들어라! # 초기설정 Make-Set(a) ~ Make-Set(f) : [0, 1, 2, 3, 4, 5, 6] 또는 [a, b, c, d, e, f] : 대표는 자기자신을 가리킨다. Find-Set(x) : x 가 속한 집합의 대표원소를 알아내라! 자기자신을 가리키는 원소(=대표원소)를 만날때 까지 찾는다. Union(x, y) : x가 속한 집합과 y가 속합 집합을 합쳐라!..

BFS에 거리를 추가하는 방식으로 구현하였다. 테스트케이스 2개만 맞고 계속해서 오류가 떴다. 추가로 테스트케이스를 넣어봤는데 맞는 답이 나왔는데도 통과하지 못했다. 초기화도 했는데 무엇이 문제인지 머리가 터질 것 같다. ㅠㅠ 대부분의 사람들이 dfs로 문제를 풀어서 힌트를 얻지 못했다. 결론 : BFS 로 풀 수 없다. BFS 1차수정 (오류) 일단 따로 table 필요 없이 visited 를 숫자배열로 배치 global 로 maxV 변수를 쓰기 때문에 return 따로 해주지 않아도 된다. bfs 는 초기화시킬 필요 없을것 같고.. bfs로 풀 수 있는건가? import sys sys.stdin = open('input.txt') from collections import deque def numbe..

문제 접근 import sys sys.stdin = open('input.txt') from collections import deque V, E = map(int, input().split()) # 7, 8 edge = list(map(int, input().split())) # [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] # 인접 행렬을 만든다. graph = [[0]*(V+1) for _ in range(V+1)] # (V+1 * V+1) 행렬 for i in range(E): ni, nj = edge[2*i], edge[2*i+1] graph[ni][nj] = 1 graph[nj][ni] = 1 # 무방향 그래프 # 큐와 visited 설정한다. dequ..

문제 접근방법 깊이 우선 탐색의 기본 알고리즘 구현 방향을 확인해보니 무방향 그래프이고 정점은 7개, 간선은 8개이다. 간선 정보는 1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7 시작 정점은 1이다. 1) 인접 행렬 또는 2) 인접 리스트로 받아올 수 있다. DFS 경로이므로 1) 재귀를 사용하거나 2) 반복문과 스택(pop메서드) 사용할 수 있다. ✅ 인접행렬 + 재귀로 구현 1-2-4-6-5-7-3 import sys sys.stdin = open('input.txt') from collections import deque V, E = map(int, input().split()) # 7, 8 edge = list(map(int, input().split())) # [1, 2, 1, 3, ..