[알고리즘] 그래프

파이썬의 그래프그래프 관계(relationship)을 표현하는 자료 구조로, 파이썬에서는 어떤 관계를 표현할때 적합한 것은 사전(dictionary)이다. 그래프는 인접 행렬, 인접 리스트로도 나타낼 수 있다. 키(key) : 노드값(value) : 키와 연결된 노드 리스트#무방향 그래프graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}#방향 그래프graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}리스트를 이용하여 그래프를 나타내 보자. 리스트의 인덱스가 사전의 key에 해당하고, 인덱스의 값은 사전의 값과 똑같다.#무방향 그래프graph1 = [[], [2, 3, 5], [1, 3], [1, 2, ..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

[알고리즘] 트리 구조

트리 구조루트 : 트리의 가장 위쪽에 있는 노드. 루트는 트리에 1개만 존재리프 : 가장 아래쪽에 있는 노드. aka 단말 노드 (terminal node), 외부 노드 (external node). 가지를 더 이상 뻗을 수 없다비단말 노드 (non-terminal node) : 리프를 제외한 노드. aka 내부 노드자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라 한다.부모 : 어떤 노드와 가지가 연결되었을 때 위쪽 노드를 부모라 한다형제 : 부모가 같은 노드를 형제라 한다조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라 한다자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라 한다레벨 : 루트에서 얼마나 멀리 떨어져 있는지. 루트의 ..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

백준 : 2665 미로 만들기

백준 : 2665 미로만들기문제 분석입력:첫 줄에 방의 수 N(1≤N≤50)이 주어진다.다음 N개의 줄에는 길이가 N인 수열이 주어지며, 각 수열은 '0'과 '1'로 이루어져 있다.출력:시작점에서 도착점까지 이동하기 위해 부숴야 하는 검은 방의 최소 개수를 출력한다.이 문제는 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾는 문제로 볼 수 있다. 각 방을 노드로, 상하좌우 이동을 간선으로 간주하며, 흰 방('1')은 가중치 0, 검은 방('0')은 가중치 1로 설정할 수 있다. 이러한 특성 때문에 0-1 BFS 또는 다익스트라 알고리즘을 활용하여 해결할 수 있다.최종 코드0-1 BFS를 활용한 해결import sys, mathfrom collections import dequeinput = sys..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 31.

백준 : 14888 연산자 끼워넣기

백준 : 14888 연산자 끼워넣기문제 접근N개의 수가 주어지고, 그 사이에 넣을 수 있는 +, , , // 연산자의 개수가 주어집니다.모든 연산자를 한 번씩 사용하여 식을 만들 수 있고,가능한 모든 결과 중 최댓값과 최솟값을 출력해야 합니다.각 숫자 사이에 들어갈 연산자의 조합을 모든 경우의 수로 시도해봐야 한다. 즉 완전 탐색이 필요하고, 이 때 DFS + 백트래킹이 가장 적합하다.최종 코드import sys, operatorinput = sys.stdin.readlinedef dfs(index, current): global maxV, minV # 모든 숫자를 다 사용했다면 최대/최소값 갱신 if index == N : maxV = max(maxV, current) ..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 30.

백준 : 1260 DFS와 BFS

백준 : 1260 DFS 와 BFS문제 분석M : 정점의 개수 , N : 간선의 개수, V : 탐색 시작할 정점N개의 간선으로 연결된 정점의 번호DFS, BFS 탐색 결과를 출력한다.단, 1) 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 2) 입력으로 주어지는 간선은 양방향이다.우리는 저 두 가지에서 키를 얻어야 한다. 첫 번째는 입력값이 주어졌을 때, 정렬을 통해 작은 숫자부터 탐색하도록 탐색 함수를 설계해야 한다는 것이며. 두 번째는 주어진 그래프는 무방향 그래프이다. 이 두가지에 유의해서 탐색 함수를 만들어보자.최종 코드인접 리스트를 활용하여 구현한 DFS, BFS 탐색import sysfrom collections import defaultdict, deque..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 29.

백준 : 1197 최소 스패닝 트리

Kruskal 은 “ 간선 중심 “ 알고리즘이다가장 작은 가중치의 간선부터 하나씩 선택하며 사이클이 생기지 않도록 주의해서 신장 트리를 만들어간다이때 가장 중요한 건 간선 정렬과 Union-Find 자료구조를 통한 사이클 판별이다Prim 은 “ 정점 중싱 “ 알고리즘이다하나의 정점에서 시작해서, 아직 방문하지 않은 정점 중에서 가장 가까운 정점으로 확장해나간다이때는 Min-Heap (우선순위 큐)을 활용해서 매번 가장 짧은 간선을 빠르게 선택한다두 알고리즘 모두 MST를 구하지만, 그 접근 방식이 다르기 떄문에 구현을 해보면서 내가 어떤 자료구조를 다루고 있는지, 문제가 어떤 그래프 구조를 가졌는지에 따라 알고리즘 선택이 달라질 수 있음을 알 수 있었다.결론 도출결과는 같더라도, 과정은 전혀 다르다→ 같..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 29.