알고리즘

코딩테스트 알고리즘별 전략 및 요약 (수정 중...)

그래프 다익스트라 그리디, DP로 분류되기도 함 단일 시작점 알고리즘 (최단거리) 양수 가중치 사이클 존재 INF 사용 BFS 처럼 큐를 통해 루프 우선순위 큐 사용(가중치,end노드) 일차원 dp 사용 O(|E||log|V|) 벨만-포드 최단경로 찾기 단일 시작점 알고리즘 음수 가중치 음수 사이클 판별 INF 사용 v, mid, end 순서로 루프 V-1번의 완화 과정, 1번의 음수사이클 판별 과정 (완화가 실패할 때까지 완화함.) 일차원 dp 사용 O(VE) 플로이드 워셜 모든 쌍 최단 거리 알고리즘 음수 사이클 없으면 사용가능(음수 사이클 있으면 벨만 포드 N번하기) 메모리 초과 날 가능성 존재 INF 사용 k , i , j 순서로 루프 구현 간단 DP[i][j] = min(DP[i][k] + DP..

[python3] 백준 1916 풀이 ( 최소비용 구하기, 다익스트라, 그래프 )

문제를 읽어보면 한 도시에서 다른 도시까지 가는데에 걸리는 최소 비용을 구하는 문제이다. 최소 비용알고리즘은 대표적으로 다익스트라, 벨만-포드, 플로이드-워샬이 존재한다. 이 문제에서는 시작 정점이 주어지기 때문에 단일 시작점 알고리즘인 다익스트라와 벨만-포드를 사용할 수 있다. (시간제한이 0.5초라서 플로이드-워샬을 사용하면 시간초과 날것임.) 추가적으로, 음수 가중치가 나오지 않으므로 다익스트라를 사용해서 문제를 풀면 된다. 다익스트라 알고리즘을 사용해야한다는 것을 알면 문제 풀이가 어렵지는 않다. 일반적으로 쓰이는 다익스트라 알고리즘을 적용하여 풀이하면 된다. 다익스트라를 간단히 설명하자면 플로이드-워샬처럼 INF로 초기화 시키고 dp를 갱신하며 최솟값을 찾아내는 것이다. 다만 플로이드-워샬은 모..

[python3] 백준 1389 풀이 ( 케빈 베이컨의 6단계 법칙, 플로이드 워샬 )

이번 문제는 케빈 베이컨의 6단계 법칙이다. 케빈 베이컨이 할리우드의 핵 인싸라는 것을 인지하고 문제에 들어가자. 문제를 보자 문제가 상당히 길다. 읽어보면 그냥 네트워크 안에서 여러 사람들과 연결되어 있을때 모든 타인과 몇번만에 연결되어 있는지를 알아내어 최솟값을 가지는 즉, 허브 역할을 하는 사람을 구하면 된다. 문제를 잘 읽어보면 결국 N정점에서 N정점으로의 갈 때 얼마나 걸리는지를 구해야 한다. 그래야 한 노드에서 모든 노드에 방문할 때 케빈 베이컨의 수를 구할 수 있다. 즉, 모든 쌍 최단 거리 알고리즘을 사용하면 구할 수 있다. 모든 쌍 최단 거리 알고리즘의 대표적인 놈이 "플로이드 워샬"이다. 그러나! 플로이드 워샬은 O(N^3)이 걸리기 때문에 N값이 너무 크면 문제가 발생할 수 있다. 다..

[python3] 프로그래머스 입국심사 풀이 ( 이분 탐색 )

이거 어려웠다. 처음에 점화식을 세워야하나 많이 당황했다. 솔직히 이분탐색 문제가 아니었다고 한다면 제한된 시간내에 풀지 못했을거 같다. 일단 문제를 보자 문제를 읽어보면 입국심사가 필요한 인원과, 입국심사에 걸리는 시간이 존재한다. 이때 입국심사를 모두 마치기 위한 최소시간을 구하면 된다. 처음에는 이분탐색을 어디에 적용해야할지 몰라서 당황했다. 이후에 문제를 차분히 살펴보니 return값을 살펴보는게 어떨까라는 생각이 들었다. 정리된 생각은 아래와 같다. 1. 입국심사에 적은 시간이 걸리는 심사관이 많은 입국자를 받아야 총 시간이 줄어든다. 2. 최소시간을 times로 나누었을때 값을 더하면 n이 된다. 처음에는 1번에 꽂혀서 무조건 작은 시간을 많이 주고 하나씩 줄여가며 연산을 하면 되겠지라는 생각..

[python3] 백준 14360 풀이 ( 구슬 탈출 2, BFS, 방문체크 없음 )

이번 문제는 저번 주 스터디에서 풀지 못한 문제였는데, 생각할 시간이 상당히 많았기 때문에 겨우 풀었다. 우선 문제를 살펴보자 문제를 요약하면 상하좌우로 움직일 수 있는 판을 가지고 있을 때, 빨간공만을 출구로 뽑아내는 경우 얼마나 시간이 걸리는지 알아내는 문제이다. 이때 한 방향으로 움직이는 경우 두 공이 못 움직일 때까지 움직인다. 우선 우리는 최소로 움직여서 공을 뽑아낼 것이다. 즉, 최단 거리나 최단 경우의 수를 구할 때는 역시 BFS를 사용해야한다. 두번째로 우리는 2공(빨강,파랑)을 상하좌우로 움직일 것이다. 움직일 때는 한번에 움직이지 못하고 한 칸씩 이동하면서 움직여야한다. 왜냐하면 그래야 겹치는 경우를 피할 수 있다. 그런데 겹치는 경우를 위해 한 칸씩 움직인다고 한다면 방향에 따라 두 ..

[python3] 백준 16236 풀이 ( 아기상어, 그래프, BFS, sort, pq? )

이번 문제도 역시나 좀 헤맸다. 이번 문제는 BFS로 쉽게 풀릴 줄 알고 살짝 깝쳐 봤으나 역시나 생각치 못한 케이스가 존재해서 결국 다시 코딩한 문제이다. 문제를 쓰악 읽어보자. 우선 문제는 아기상어의 성장에 관한 이야기다. 스토리처럼 느껴져서 문제 읽는 동안 재밌었다. 여튼 문제에서 나오는건 아기 상어가 성장하기 위해서 물고기를 먹어야한다. 그런데 먹이를 먹는데 여러 조건이 존재한다. 조건 1. 먹을 수 있어야함. (자기보다 크기가 작아야함.) 2. 거리가 가까워야 함. 3. 위 물고기 선호 4. 왼쪽 물고기 선호 1번 조건과 2번 조건은 BFS로 최단 경로를 찾으며 먹을 수 있는 물고기를 찾으면 된다. 3번 조건과 4번 조건은 같은 거리에 존재하는 물고기들의 좌표를 비교하여 조건에 맞는 물고기부터 ..

[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 )

이번 문제 풀이 사실 봐버렸다. 거의 풀었다고 생각했는데 내가 생각한 방법으로는 도저히 풀리지가 않아서 그냥 풀이를 봤다. 바로 문제를 보자 문제를 읽어보면 낮은 방향으로만 진행한다고 한다. -> 사이클이 존재하지 않는 그래프이다. 가장 빠른게 도착하는게 아닌 도착하는 경우의 수를 구한다. -> BFS가 아닌 DFS를 여러 번 써야한다. 문제를 통해 2가지를 확인할 수 있다. 그런데 DFS만을 쓰는 경우에는 너무 많은 케이스가 존재한다. 실제로 DFS만으로 제출한다면 시간초과가 뜬다. 따라서 DFS만이 아닌 DP를 함께 활용해 주어야한다. 그럼 DP를 어떻게 활용해야 할지 고민을 해본다. DFS만 써서 시간초과가 나는 것은 빙빙 돌아 목적지에 도착하는 경우까지 기다려야 하기 때문이다. 그렇다면 빙빙 돌아..

[python3] 백준 2293 풀이 ( 동전 1, 다이나믹 프로그래밍 )

아주 상당히 헤매면서 풀었다. 실버 1이라 어려울 것이라 생각했는데 정답비율이 높았다. 난이도는 높지만 알고리즘만 이해하면 코드 구현을 쉬웠기 때문인거 같다. 우선 나는 노가다를 해가며 풀었다. k가 1일때부터 1,2,5가 가능한 조합을 전부 때려 넣어가며 숫자를 보았는데 규칙 일랑 하나도 보이지 않았다. 그래서 덩어리를 생각하며 풀어보기로 했다. 그래서 생각한 것이 이차원 배열로 나타내는 것이었다. 문제에서 주어진 예제가 아닌 다른 예제로 생각해 보겠다. 2 10 2 3 K 0 1 2 3 4 5 6 7 8 9 10 2 1 0 1 0 1 0 1 0 1 0 1 3 coin이 2인경우 k값에 따라 만들 수 있는 경우는 2로 나누어 떨어지는 경우이다. 이때는 2만 들어 가기 때문에 한가지 경우만 존재한다. 따..