다익스트라 알고리즘 정리 | BFS와 차이, 우선순위 큐 구현까지

최단거리 문제라고 해서 항상 BFS를 쓰는 것은 아니다.BFS가 정확하게 동작하는 경우는 모든 간선의 가중치가 같을 때다. 이 경우에는 먼저 도달한 경로가 곧 최단거리이기 때문에, 레벨 순서대로 탐색하는 BFS가 자연스럽다. 반면 간선마다 비용이 다르면, 더 적은 횟수로 이동한 경로가 더 짧다는 보장이 사라진다. 이때 필요한 알고리즘이 다익스트라(Dijkstra) 다. 다익스트라는 음의 가중치가 없는 그래프에서, 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 대표 알고리즘이다.즉, 다익스트라는 이렇게 이해하면 된다.BFS: 간선 비용이 전부 같을 때 최단거리다익스트라: 간선 비용이 서로 다를 때 최단거리이 글에서는 파이썬 기준으로, 왜 다익스트라가 필요한지, 어떤 방식으로 구현하는지, 코드..

• format_list_bulleted Coding Test/Python & Algorithm
• · 2026. 4. 28.

DFS와 BFS 차이 정리 | 코딩테스트에서 문제에 맞게 고르는 기준

DFS와 BFS는 정의만 외우면 계속 헷갈린다.실제로 코테에서 중요한 건“DFS는 깊이 우선, BFS는 너비 우선” 같은 문장 자체가 아니라,문제를 봤을 때 어느 쪽이 더 자연스러운지 판단하는 기준이다.정리하면 이렇다.최단거리 / 레벨 / 한 칸씩 퍼지는 구조면 보통 BFS가 맞고연결된 덩어리 처리 / 끝까지 파고들기 / 완전탐색이면 DFS가 더 자연스러운 경우가 많다즉, DFS/BFS는 알고리즘 이름을 외우는 문제가 아니라문제 구조를 보고 고르는 문제에 가깝다.이 글에서는 그 기준만 정리해보려고 한다.🔗 주제DFS와 BFS 차이 정리개념 요약둘 다 탐색이다.즉, 그래프나 격자에서 어떻게 방문할지를 정하는 방식이다.차이는 방문 순서다.DFS한 방향으로 끝까지 들어간다막히면 돌아온다스택 흐름이랑 잘 맞는..

• format_list_bulleted Coding Test/Python & Algorithm
• · 2026. 4. 28.

파이썬 리스트 컴프리헨션 정리 | 코딩테스트에서 바로 쓰는 패턴 모음

리스트 컴프리헨션은 그냥 for문 짧게 쓰는 문법이 아니다.코딩테스트에서는 보통입력을 가공하거나, 조건에 맞는 값만 뽑거나, 간단한 변환을 한 줄로 처리할 때 제일 많이 쓴다.즉, 이걸 문법 하나로만 보면 잘 안 남고,반복 + 조건 + 변환을 한 번에 묶는 패턴으로 봐야 실전에서 손에 붙는다.처음에는 나도 그냥 “짧게 쓰는 문법” 정도로만 봤는데,막상 문제 풀다 보니까 이게 꽤 자주 나왔다.숫자 리스트 만들기조건에 맞는 값만 남기기문자열을 문자 단위로 쪼개기입력값을 가공해서 바로 리스트 만들기이런 데서는 그냥 반복문보다 더 자연스럽다.🔗 주제파이썬 리스트 컴프리헨션 정리+ 마지막에 연습문제 첨부합니다 필요하면 사용하시면 되어요개념 요약리스트 컴프리헨션 기본형은 이거다.[표현식 for 변수 in 반복가능..

• format_list_bulleted Coding Test/Python & Algorithm
• · 2026. 4. 23.

파이썬 split과 map 정리 | 코딩테스트 입력 처리에서 자주 쓰는 이유

코딩테스트에서 split()이랑 map()은 거의 기본이다.처음엔 둘 다 따로 보면 애매한데,실제로는 입력 문자열을 쪼개고 → 원하는 자료형으로 바꾸는 패턴으로 계속 같이 나온다.특히 아래 한 줄은 코테에서 진짜 많이 쓴다.nums = list(map(int, input().split()))이걸 그냥 외우는 것도 방법이긴 한데,왜 이렇게 쓰는지 이해해두면 나중에 변형 문제에서도 덜 꼬인다.이번 글은 split()과 map()을입력 처리 관점에서 정리해보려고 한다.🔗 주제파이썬 split / map 정리+ 마지막에 연습문제 첨부합니다 필요하면 사용하시면 되어요개념 요약둘 역할은 딱 나뉜다.split() → 문자열을 나눈다map() → 나눠진 각 요소에 같은 변환을 적용한다즉 이 흐름이다.입력은 보통 문자..

• format_list_bulleted Coding Test/Python & Algorithm
• · 2026. 4. 22.

파이썬 deque 정리 | BFS에서 리스트 대신 deque를 쓰는 이유

deque는 BFS 풀 때 거의 기본처럼 나오는 자료구조다.파이썬으로 코테 풀다 보면 처음엔 큐를 그냥 리스트로 만들고 pop(0)으로 꺼내도 되지 않나 싶다.실제로 작은 입력에서는 돌아가기도 한다.근데 BFS는 구조상 앞에서 꺼내는 작업이 계속 반복된다.그래서 이 시점부터는 리스트보다 deque가 맞다.정리하면 이 글의 핵심은 딱 이거다.스택처럼 뒤에서 뺄 거면 리스트도 괜찮다큐처럼 앞에서 계속 뺄 거면 deque가 맞다BFS는 큐 구조라서 deque를 거의 기본처럼 쓴다이 글에서는 deque를 코딩테스트 기준으로만 정리해보려고 한다.주제 정리deque는 double-ended queue의 약자다. 말 그대로 양쪽 끝에서 넣고 뺄 수 있는 큐다.파이썬에서는 collections 모듈에서 가져온다.fro..

• format_list_bulleted Coding Test/Python & Algorithm
• · 2026. 4. 20.