산 넘어 산 개발일지

풀이 키워드 DP 이분 탐색 LIS LIS(최장 증가 부분 수열) 이분탐색에서 주로 나오는 LIS문제였다. DP랑 같이 합해져서 나오는 문제 중 자주 나오는 유형인 것 같다. 이런 LIS의 경우 방식은 다음과 같다. 1. List를 만들고 첫 번째 원소를 넣는다. 2. 다음 원소(Next)부터는 list의 맨 마지막 원소(Last)와 비교하며 조건마다 특정한 작업을 수행한다. (조건 1) Last = Next list 원소 중 Next와 같거나 Next보다 작으면서 가장 비슷한 원소의 바로 다음 원소를 삭제하고 그 자리에 Next를 넣는다. (가령, Last = 3 이고 List = [1, 2, 4]였다면 4자..

풀이 키워드 다익스트라 다익스트라로 푸는 것을 안다면 그렇게 어려운 문제는 아니였다. 그러나 다익스트라로 풀어야 한다는 것을 눈치채는 것이 문제라면 문제인 그런 유형이였다. 우선 그래프 탐색에는 유명한 3가지 DFS, BFS, Dijkstra가 있다. 우선 대부분의 문제에서 2차원 형식의 지도(?)처럼 주어지면 대개 DFS/BFS로 푸는 경우가 많다. 반대로, Dijkstra의 경우 대부분 이렇게 2차원 지도로 주어지지 않고 각 노드간의 연결 정보와 그 가중치가 주어진다. 이렇게 주어지는 이유는, DFS/BFS와 Dijkstra의 가장 큰 차이점은 노드간 가중치가 같은지 여부이기 때문이다. DFS/BFS의 경우 모든 노드간의 가중치가 같고, 우리가 찾아내야 하는 정답의 기준은 "얼마나 적은 수의 노드를 ..

풀이 키워드 에라토스테네스의 체 이번 문제는 척 보면 알 수 있듯이 소수를 사용하는 문제이다. 소수하면 바로 에라토스테네스의 체가 떠오른다. 에라토스테네스의 체는 범위 내의 숫자들이 소수인지 아닌지를 미리 판별해내는 계산이다. 간단히 설명하자면, 미리 1~N까지의 배열(boolean)을 만들어 놓는다. 그리고 처음에는 2부터 시작을 한다. 2를 제외한 2의 배수들은 소수가 아니므로 소수가 아니라고 마킹(false)한다. 그리고 다음 숫자 3으로 넘어간다. 3은 소수가 아니라 마킹이 안되었으므로 앞 과정과 동일하게 3을 제외한 나머지 배수들을 소수가 아니라고 마킹한다. 다음 4는 2에 의해 마킹되었으므로 넘어간다. 다음 5는 마킹이 안되었으므로 앞 3과 동일한 작업을 수행한다. 이런 과정을 N까지 반복하면..

풀이 키워드 브루트포스 정해진 규칙이 딱히 없으니, 브루트포스로 일일이 다 해봐야 한다는 것을 알 수 있다. 그런데 이 때 어떤 것을 일일이 다 해볼지가 문제이다. 브루토프스의 경우, 가장 큰 틀에서 경우의 수를 일일이 해보는 것부터 생각을 해봐야 한다. 이번 문제의 경우, N의 채널은 0 ~ 500,000까지 존재하므로 만약 모든 채널을 일일이 다 해본다면 50만 번의 시도가 필요하다. 즉 나쁘지 않은 시도횟수이므로 이것을 기준으로 브투르포스를 진행하면 되는 것이다. 다만, 채널을 돌릴 때, 아래에서 N까지 시도해볼 수도 있고, 위에서 N까지 시도해볼 수도 있다. 예를 들어, N = 500000 일 경우 480000부터 시도해볼 수도 있지만, 520000부터 시도해볼 수도 있는 것이다. 어느 쪽에서 시..

풀이 키워드 다익스트라(Dijkstra) 일반적인 다익스트라 알고리즘으로 풀리는 문제이다. 한 노드에서 각 노드까지 갈 수 있는 최단거리를 구해야 하며, 각 노드마다 가중치가 각각 다르므로 DFS, BFS로는 풀 수 없고 다익스트라로 풀어야 한다는 것을 알 수 있다. 우선순위 큐(PriorityQueue)를 사용해서 풀면 훨씬 빠르고 편리하다. 우선순위 큐를 사용하면 현재 큐를 최적의 방법으로 정렬하여 가장 거리가 짧은 노드부터 검사할 수 있게 해주며, 이 때문에 각 노드의 방문여부를 체크할 필요가 사라진다. 푸는 방식을 간단하게 소개하면 다음과 같다. 도시들의 그래프인 arr[]이 있고, 시작점에서 각 도시까지의 거리를 나타낸 dist[]가 있다. dist[]는 시작점은 0으로, 나머지는 Inf 값으로..

풀이 키워드 그리디 알고리즘 단어의 합의 최댓값을 구하기 위해서는 (1. 가장 많이 나오고) (2. 가장 높은 자리에 위치) 한 순서대로 가장 높은 숫자를 부여하면 된다. 그때 그때 가장 최선의 경우를 구해야 하므로 그리디 알고리즘임을 쉽게 알 수 있다. 따라서 우리는 가장 많이 나오고 가장 높은 자리에 위치한다는 것을 어떻게 정할지만 정하면 된다. 문자를 수로 치환하여 가장 큰 값을 찾아야 하므로, 각 문자마다 위치한 수의 자리에 따라 가중치를 정해서 더해주면 된다. 예를 들어, AAA, ACDEB 가 있다고 해보자. AAA A는 100의 자리, 10의 자리, 1의 자리에 해당하는 가중치를 가진다. 따라서 A += 100 + 10 + 1 ACDEB ACDEB = 10000 + 1000 + 100 + 1..

풀이 키워드 브루트포스 DFS N과 M의 크기가 크지 않고, 이것 저것 다양하게 시도해보아야 해서 브루트포스로 풀어야 한다는 것을 알 수 있다. 문제에 나온 그대로 푼다면 DFS 함수를 정의하여 각 위치를 입력받은 뒤, 도형 모양대로 값을 계산해보면 된다. 그러나 이렇게 할 경우, 중복되는 경우의 수가 많이 생기고, 코드가 너무 길어질 것 같았다. 그래서 DFS로 한점 한점 탐색하며 탐색한 크기가 4가 되는 경우 현재까지의 값을 max와 비교하여 최대의 크기를 찾는 방법을 사용했다. 다만, 이 경우에도 중복이 생길 수 있으므로 DFS함수 안에서 다음 위치로 뻗어 나갈 때, 위로는 뻗어나가지 않도록 설정했다. 즉 빨간색 점에서 위로는 못 가고, 초록색 부분으로만 뻗어나갈 수 있는 것이다. 이렇게 해도 여전..

풀이 키워드 DP 숫자들을 사용해 나가는 DP 문제는 대부분 이전 숫자들을 이용하는 것이 많다. 즉 dp[i]를 구하기 위해서는 dp[i-1] 이나 dp[i-2] 등을 이용하는 것이다. 이번 문제도 크게 다르지 않았다. 먼저, 이번 문제의 특별한 숫자들로는 1, 2, 3이 있다. 이 숫자들을 사용해 앞으로의 숫자들에 대한 덧셈 식을 구현하는 것이다. 따라서, 먼저 이 숫자들이 몇 개의 덧셈식을 가지고 있는지를 계산해놓자. dp[1] = 1 (1) dp[2] = 2 (1+1, 2) dp[3] = 4 (1+1+1, 1+2, 2+1, 3) 이제 4를 보자. 4는 문제에 나와있듯이 7개의 덧셈식이 존재한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 이를 맨 뒤 숫자만 제외하고, 될 수..