처음엔 플로이드 워셜로 시도했다. 플로이드 워셜이 N^3 인데 N 이 1000 이고 대충 1초 정도를 예상했음. 그런데 시간초과가 나서 다익스트라로 AC 를 받았다. (32ms) 그런데 0ms 가 기록에 있는 걸 보고 풀이를 봤는데, 다익스트라로 생각지 못한 풀이가 있어서 남겨봄.* 참고로 플로이드워셜로도 최적화하면 풀리긴 함. 가장 먼저 떠오른건 플로이드 워셜 알고리즘이었다. 왜냐하면 다익스트라는 한점에서 다른 모든 점까지의 최단거리를 구하는 알고리즘인데, 이번 문제의 조건은 모든 점에서 특정 점까지의 최단거리를 구해야하니까 적절하지 않다고 생각했음. 그런데 다익스트라는 한점에서 다른 모든 지점으로의 최단거리 뿐만 아니라 한 점으로 도착하는 다른 모든 점에서부터의 최단거리 또한 구할 수 있다. !!..
Algorithm
https://www.acmicpc.net/problem/11049 그리디와 dp 를 두고 세시간 넘게 고민하다가 뇌가 안되는거 같아서 포기하고 풀이방향을 보고 풀었다. dp 는 어느정도 익숙해졌다 싶었는데, 이렇게 과감하게도 풀 수 있구나 싶어서 꼭 기억을 해두려고 한다. 너무 분해.dp 라는 생각이 가장 직관적으로 다가왔는데, 점화식을 어떻게 잡아야 할지 감이 안왔다. 기본적으로 dp[start][end] = start 부터 end 까지 연산의 최소값 으로 메모이제이션을 하는 쉽게 알 수 있다. 그런데 여기서dp[start][end] 와 dp[start][end + 1] 사이의 관계식(점화식)은 어떻게 만들까? 둘에 관계가 보이지 않았다.start ~ end 에서 start ~ end + 1 한개만 ..
이 문제는 2022 카카오 인턴십 코딩 테스트 문제로, 이번에 본 2024 겨울 인턴십 코딩 테스트를 대비하기 위해서 풀었던 문제이다. 처음에 dp 로 시도했다가 테스트 케이스를 다 맞추지 못해서, 다익스트라를 적용해서 간신히 풀어내었다. 다익스트라도 자꾸 시간 초과가 나서 최적화를 하는데 애먹었다. 각각의 접근 방식을 정리해두고 최종적으로 AC 받은 다익스트라 알고리즘의 최적화 방법도 남겨 놓는다. 1. 기본 아이디어 1) 정상에서 다시 입구로 갈때 중복된 간선을 이용해도 되기 때문에, 입구에서 정상까지 가는 단일한 경로만 고려한다. 2) 다른 출발점이나 정상을 경유하는 경로는 고려하지 않는다. 위 두가지 아이디어를 전제로 두고 아래와 같이 알고리즘을 짰다. 2. DP [틀림] 1) 각 출발점에서 df..
백준에서 골드 문제를 랜덤으로 돌리던 중 1414번 불우이웃돕기를 만나게 되었다. 한 30 ~ 40분 정도를 고민해서 풀이의 방향은 잡았었는데, 내 생각에 자신이 없어서 결국 풀이를 검색했다. MST(Minimum Spanning Tree) 라는 부류의 문제였고 MST 를 푸는 대표적인 알고리즘 중 하나인 크루스칼 알고리즘이 내 초기 아이디어와 거의 동일한 방법이었다는 것을 알게 되었다. '그냥 내 풀이대로 밀고나가볼걸' 이라는 아쉬움을 느끼긴 했지만, 확신할 수 없는(다시 말해 증명할 수 없는) 직관은 허무할 수 밖에 없다라는 결론에 도달하게 되었다. 크루스칼 알고리즘은 사실 간단하다. 그리디라는 기본 자세를 가지고 가지를 뻗어나가면 되는 것이다. 나 정도의 사람도 직관적으로 떠올릴 수 있는 방법이다...
아이디어 아주 예전에 다익스트라 알고리즘 설명글을 살짝 본 것을 토대로 아이디어를 잡아서 해보려 했으나, 정점과 간선을 어떻게 다루어야 할지 방법이 잘 떠오르지 않았다. 결국 몇번 틀리고 나서(TLE, MLE) 해답을 보고 한참을 고민해서 AC 할 수 있었다. 항상 가장 최단거리의 간선을 먼저 선택해야 최단거리를 계속 갱신할 수 있기 때문에 간선을 선택하는 순서를 잘 고르는 것인 관건이었다. 이는우선순위큐를 활용해서 했다. 사실 해답을 보고도 한참을 고민하다가 머리 좀 식혀야겠다 하고 밥먹고 누워있다가 가만히 고민해보니 금방 정리가 됐었다. 알고리즘은 항상 자기 전이나 누워서 가만히 생각할 때 아이디어가 툭 튀어나온다. 문제풀이 다익스트라 + 우선순위 큐 #include #define INF 987654..
사실 DP 문제는 겁부터 난다. 다른 알고리즘과 마찬가지로 익숙해지고 많이 풀어보면 쉽게 느껴지지만 처음에는 도무지 내 지능이 닿지 못하는 영역인것만 같은 느낌이 들고, 그 좌절감이 참 씁쓸하기 때문이다. DP 문제는 가장 쓴 맛이 컸던 알고리즘이었다. 쉬운 문제부터 천천히 시작하자는 마음으로 만만한 녀석을 골랐다. 초기 아이디어 사실 타일 채우기는 DP 의 가장 쉬운 문제인 피보나치와 닮아있다. 다만 이전 타일에서 새로운 경우의 수를 곱해주는 것과 별개로 아예 새로운 배열이 생겨난다는 점을 염두에 두어야 한다. 처음에는 dp[n-2] *3 + dp[n-3] *2 두가지만 고려했었는데, 아예 새로운 배열도 나오겠구나 라는 생각에서 dp[n-2*i]*2 로 전부 더해주어야 한다는 생각에 닿았다. 문제풀이 ..
초기 아이디어 딱맞는 알고리즘이 별다르게 방법이 안 떠오를는 완전탐색이 먼저 떠오른다. 이럴 때는 치킨집의 최대 개수가 13 인것도 하나의 힌트가 된다. 이 이상 넘어가면 조합의 개수가 너무 커지기 때문이다. 재귀적으로 치킨집의 조합을 만들고 마지막에 최소 거리를 계산하는 식으로 정답을 찾았는데, 이전에 푼적이 있던 문제였다. 그때 참 최적화를 잘 해놓았는데, 벡터 배열에 모든 경우의 수를 담아내고 차례로 이걸 꺼내서 최소거리를 만들어내는 방식이었다. 이번에는 비트마스킹을 써서 개선해 보았다. 사용하는 메모리가 더 적어졌다. 문제풀이 조합 벡터배열 이용 #include using namespace std; int n, m; int a[55][55]; vector house; vector chicken; ..
초기 아이디어 조합이 가장 먼저 떠올랐다. 알파벳 스물여섯개 중 주어진 숫자만큼 조합으로 이용해서 뽑고, 단어마다 해당 단어가 뽑은 단어에 포함되어 있는지를 셈해보는 것이다. 최악의 경우 21C10 의 경우의 수에 각각 50개의 단어를 판별해야 한다. (acnti 다섯글자는 반드시 있어야 하므로) 대충 보면 시간 초과가 날 것 같진 않은데 ... 비슷한 문제를 재귀를 이용한 조합으로 단순히 풀었다가 시간 초과가 난 기억이 있어서 그냥 비트마스킹 연습도 할겸 비트마스킹으로 풀어보기로 한다. 비트마스킹은 사실 근본적인 알고리즘이라기 스킬의 일종이다. 이진법으로 나타낸 수의 각 자리를 하나의 불리언이라고 생각하고 특정 조합을 하나의 숫자로 나타내는 것이다. 예컨대 13을 이진수로 표현하면 1101 인데 '첫번..
초기 아이디어 부분적으로 최단거리를 구하는 문제이므로 DFS, BFS 가 쓰일 것 같다는 생각은 바로 들었는데, 다소 복잡하다. 처음엔 "가장 먼 두 지점" 이라는 말에서 DFS 를 생각했는데 돌아서 가면 안된다는 조건 때문에 결국 가장 먼 지점이라고 해도 BFS 로 풀어내야 한다는 것을 깨달았다. 모든 육지에 대해서 BFS 를 수행하고 가장 멀리까지 갈 수 있는 지점을 계산 해보기로 했다. 문제풀이 1. 모든 두 지점을 순회하면서 BFS #include using namespace std; int n, m; char a[51][51]; int visited[51][51]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int bfs(int sX, int..
초기 아이디어 최단 거리를 묻는 문제는 우선 직관적으로 DFS, BFS 를 생각할 수 있다. 더 코드가 짧은 DFS 를 하기로 해보고 연습겸 BFS 로도 구현해보기로 한다. 문제 풀이 1. DFS #include using namespace std; int a[101][101]; int visited[101][101]; int n, m, ret=987654321; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void dfs(int x, int y, int dept){ if(x==n-1 && y==m-1) { ret = ret>dept?dept:ret; return; } for(int i=0;i> n >> m; for(int i=0;i> m; for(in..
