알고리즘
백준 17370번 육각형 우리 속의 개미
문제 문제 분석 일반적인 벌집 모양 문제이다. 다만 처음에 종료조건을 조금 오인했는데, 하나의 벌집 칸을 모두 돌 때 끝나는 것이 아닌, 이미 지나온 어떠한 칸을 마주치더라도 종료되는 것이다. 그래서 그냥 좌표에다가 벌집을 찍고, 회전에 대한 구현을 하여 이미 지나온 점을 만날 때 회전한 횟수가 P일 때 카운트를 더하게 하여 문제를 해결하였다. 우선 벌집을 좌표로써 표현한 방법은, 가로와 세로로 나눌 수 있는데, 세로의 경우, 한 변의 길이가 a라고 가정했을 때, 직선으로 올라가는 것, 대각선으로 올라가는 것 (내려가는 것 포함)으로 나눌 수 있다. 직선으로는 y좌표로 그대로 a가 추가되고, 대각선으로는 a * 1/2가 추가된다 (30, 60, 90 직사각형으로 보았을 때 길이의 비율로 따짐). 가로로 ..
백준 10879번 Speak your mind!
문제 문제 분석 복잡해 보이지만, 결국 요점은 입력을 2의 제곱의 덧셈 뺄셈으로 나타내는 것이다. 현재 값이 A라고 할 때 A를 X(2의 제곱수) - Y(나머지) 혹은 X'(2의 제곱수) + Y'(나머지)로 나타내고, 그 중에서 작은 값을 선택하면 된다. 이를 점화식으로 나타내면 다음과 같다. N(A) = min((N(X/2)+N(A-X/2)+4), (N(X)+N(X-A)+4)) 나는 이를 DP + DFS로 풀었다. 좀 더 디테일 하게 설명해보자면, DP를 확인하여 값이 있으면 그 값을 리턴하고, 없으면 재귀 호출로 쭉 내려가서 값을 계산하여 그를 사용하는 방식 말이다. 내가 이렇게 한 이유는 A보다 큰 값이 문제 해결에 쓰이기 때문이었다(A = X - Y). 그런데 다시 보니, X는 A보다 크더라도 2..
백준 14003 번 : 가장 긴 증가하는 부분 수열 5
문제 문제 분석 증가 수열 문제 시리즈를 몇개 풀어봐서 얕봤었다.... 어려웠다. 다른 점이라곤 범위가 0에서 -10만정도로 바뀐 것이고 경로를 추가로 출력해야 했었다. 가장 먼저 생각난 것은 갯수를 구할때 쓰인 DP를 그대로 이용하는 것이었다. DP[i]는 길이가 i인 증가하는 수열에서 가장 작은 끝값을 저장하는 것이었는데 이 모양이 부분 증가수열이라서 그대로 이것을 출력했는데 틀렸었다. 당연한게 이것은 가장 긴 증가하는 부분 수열을 위해서 계속 갱신되기 때문이다. 예를 들어 456712이런 수열이 존재한다면 DP에는 4567이 아닌 1267이 존재할 것이고 이는 입력의 증가하는 부분 수열이 아니므로 틀리게 되는 것이다. 그래서 이 경로를 저장할 두번째 방식으로 생각해낸 것이 각 인덱스 별로 (부분수열..
백준 1238 : 파티 / 플로이드 워셜 알고리즘
문제 문제 분석 노드간의 최단거리를 만들어 두고, 파티 노드 X로 오고 가는 거리의 최댓값을 구하는 문제였다. 즉, 모든 노드간의 거리가 최단거리라고 할 때 A -> X -> A의 최댓값을 구하는 문제였다. 모든 노드로 부터 모든 노드로의 최단거리 문제를 구하는 문제였으므로 Floyd-warshall 알고리즘을 적용시켜서 풀면 된다고 생각했다. 근데 ㅋㅋㅋㅋ 적용시키면 풀릴것같은데 구현을 까먹었어서 잠시 현타가 왔었다. 아직 내 지식이 아닌가보다 하고 다시 서치했다. 알고리즘의 핵심은 모든 경로에 대해서 모든 노드를 거쳐갈 때를 확인하는 것이다. 즉, 1->3이라는 경로가 존재할 때 1->(2,4....) ->3 와 같이 그 외의 모든 노드를 중간에 넣어보면서 그 노드가 들어갈 때 총 거리가 더 줄어드는..
백준 20543 번 : 폭탄 던지는 태영이 / 2D prefix-sum
문제 1 ≤ M ≤ N ≤ 2,000 (M은 홀수) -2,147,483,648 ≤ H[r][c] ≤ 0 문제 분석 정말 어려운 문제였다. 해결할 아이디어는 문제에서 나온 "폭탄의 폭발 범위가 밖을 넘어가지 않게 한다"라는 조건에서 비롯된 "모서리에 영향을 미치는 칸은 반드시 하나"라는 점이다. 만약에 그렇다면 모서리가 영향을 끼치는 만큼 ( M/2, M/2 )만큼 떨어진 칸에 그만큼의 폭탄이 존재할 것이다. 모서리를 처리하면, 모서리에 인접한 다른 테두리에 영향을 미치는 칸도 하나로 확정되므로 이를 바탕으로 차례대로 폭탄을 처리하면 된다는 것이다. i,j칸의 관점에서 영향을 줄 수 있었던 칸을 모두 처리한다면 칸 i,j에 영향을 미치는 칸은 (i + m/2, j + m/2) 뿐일 것이다. 하지만 이에 ..
2020 카카오 인턴십 for Tech developers 코딩테스트 3번
문제 programmers.co.kr/learn/courses/30/lessons/67258# 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 분석 접근법은 어렵지 않았던것 같다. 배열의 길이가 100,000 = 10^5이므로, n^2는 안되고 nlogn정도로 불어야 하기 때문에, 모든 인덱스를 기준으로 한칸씩 움직이며 모든 보석이 확인될 때 까지 순회를 하면 안된다. 대충 n^2이니까 그렇다면 배열을 한번만 돌아야 한다는게 키 포인트인데, 이를 위해서 현재 insert하는 인덱스와 pop하는 인덱스를 저장하고, 그 사이에 모든 원소가 들어간다면 out..