산 넘어 산 개발일지

풀이 키워드 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자..

풀이 키워드 Stack 스택은 처음 사용해보았다. 스택이라는 개념은 알고 있었지만, 알고리즘에 사용해본 경우는 처음이였다. 스택을 사용하지 않고 재귀를 이용해 풀었을 때는 틀리는 케이스들도 있었고 무엇보다 효율성을 통과하지 못했다. 스택을 사용한 경우, 일단 무엇보다 코드가 간결해졌다. 뭔가 재귀로 풀어야 할 문제들을 만났을 때, 재귀로 풀기 전 스택을 한번 고려해보면 좋을 것 같다고 느꼈다. 우선 원리는 간단하다. 입력받은 문자열 s를 한 문자씩 탐색해나간다. 그리고 조건에 따라 문자를 스택에 넣거나(push()) 스택에서 문자 하나를 빼낸다(pop()). push() 조건 Stack이 비어있거나 || 스택의 윗부분이 현재 문자와 다를 경우 pop() 조건 Stack이 비어있지 않을 경우 && 스택의 ..

풀이 키워드 다익스트라(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..

풀이 키워드 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 이를 맨 뒤 숫자만 제외하고, 될 수..