이름 못 정한 블로그

설명을 읽다 보면 또리디인가 하는 생각이 들었다. 하지만 제한사항을 보는 순간 아 이건 무조건 선형 아니면 로그 복잡도를 가진 문제라는 게 보인다. 입국 심사를 기다리는 사람이 최대 10억 명까지 들어올 수 있기 때문에 복잡도가 제곱만 돼도 많이 어지럽기 때문이다. 백준에서는 제한 시간도 나와있기 때문에 대충 연산량과 시간을 비교해볼 수 있다. 하지만 프로그래머스는 백준과 달리 시간, 메모리 제약이 보이질 않는다. 그래도 어느 정도 합리적인 수준에서 알고리즘의 복잡도를 생각해보면 선형 시간도 어려울 것 같다. 그럼 남는 건 로그 시간이다. 로그 시간을 갖는 가장 대표적인 알고리즘으로는 이분 탐색이 있다. 이분 탐색은 [왼쪽, 오른쪽]의 범위를 정하고 범위의 절반씩 없애는 알고리즘이다. 이분 탐색 알고리즘..

간단한 그래프 선회 문제인 줄 알고 풀다가 주어진 항공권을 모두 사용해야 한다는 제약 조건을 뒤늦게 봐서 풀이 시간이 길어졌다. 무려 첫 번째 문장인 데다가 입출력 예제 #2를 보면 바로 알 수 있는 내용인데 안일했다. 그냥 무식하게 아직 사용하지 않은 ticket을 사용해나가면서 그래프를 돌면 된다. 문제 조건에 모든 도시를 방문할 수 없는 경우는 주어지지 않다고 되어 있어서 백트래킹을 따로 고민하기 싫었다. 하지만 그러면 문제가 풀리지 않는다. 따라서 적절한 백트래킹을 추가해주어야 한다. 딱히 크게 고민할 건 없고 경로에서 마지막으로 방문했던 공항을 빼주기면 한다. 이 문제를 풀면서 가장 헷갈린 부분이 tickets의 최대 크기가 주어지지 않다는 점이였다. 그래서 알고리즘을 설계하는 단계에서 시간 복..

여전히 PS재활훈련 중이다. 최근 계속 그리디만 풀고 있는 것 같다. 이 문제는 제한사항에서 볼 수 있듯이 입력되는 변수들의 크기가 꽤나 크다. 특히 N의 경우는 2억이나 되기 때문에 O(N^2)만 돼도 복잡도가 어마 무시하다. 따라서 못해도 O(N) 혹은 O(logN)에는 해결해야 하는 문제였다. 이게 이 문제에서 가장 큰 힌트였다고 생각한다. O(logN)은 트리나 이분 탐색이 아닌 이상은 구현하기가 쉽지 않다. 따라서 이 문제는 다른 방법들을 모두 제치고 선형 알고리즘일 것이라고 생각할 수 있다. 이 문제에서 얻을 수 있는 또 다른 힌트는 stations가 이미 오름차순으로 정렬되어 있다는 부분이다. 물론 그냥 문제가 친절하기 때문일 수도 있지만, 오름차순으로 정렬되어 있다는 말을 보면 괜히 낮은 ..

이 문제의 핵심은 이길 때는 아슬아슬하게 지고 질 때는 크게 지는 것이다. 정렬을 사용하면 쉽게 풀 수 있다. 물론 문제에서 출전 순서가 정해져 있긴 하지만 B팀 입장에서는 순서를 이미 파악하고 있으므로 순서가 없는 것이나 마찬가지다. 우선 A팀과 B팀의 수를 오름차순으로 정렬한다. 그러면 A팀이 내는 숫자와 가장 가까운 B팀의 사원이 나갈 수 있게 된다. 만약 A팀 사원을 이기지 못할 것 같으면 다음으로 큰 숫자를 가지고 있는 B팀의 사원이 나간다. 어제 비슷한 문제를 풀어서 그런가 문제를 정말 쉽게 풀 수 있었다. 그리디로 풀 수 있는 문제는 냅다 정렬을 해버리면 문제를 쉽게 해결할 수 있다는 사실을 분명히 알고 있었을 텐데 얼마 동안 PS를 하지 않았다고 놓쳐버린 것 같다.

1. 가장 간단한 방법은 [-30,000, 30,000]의 좌표를 갖는 1차원 배열을 0으로 초기화해서 하나 만들고 각 routes의 진입 지점부터 진출 지점까지 +1 한다. 모든 routes에 대해서 이 작업을 수행하면 가장 큰 좌표부터 내림차순으로 차량이 단속용 카메라를 만날 수 있도록 카메라를 설치하는 것이다. 하지만 단순한 방법인만큼 비용이 많이 든다. 최악의 경우엔 크기가 60,000인 배열이 필요하다. 그리고 차량이 최대 10,000대이기 때문에 못해도 6억 번 정도의 연산이 필요하다. 따라서 이 방법은 시간이 많을 때나 도전할 수 있는 방법이다. 2. 그 다음은 routes를 순회하면서 새로운 차량의 동선을 만날 때마다 카메라를 설치하는 것이다. 그리고 카메라의 좌표를 설치 가능한 범위를 기..

단순히 그래프 순회로 풀 수 있는 문제다. 각 단어를 그래프의 노드라고 보고 변환이 가능한 단어를 인접 노드로 생각한다. 그래서 처음에 문제를 시작할 때 인접 행렬을 생성하고 BFS나 DFS로 선회하면 된다.

이전의 코테에서 상당히 비슷한 문제를 풀었던 기억이 있다. 그때는 왜 그랬는지 모르겠지만, 힙을 사용해야겠다는 생각이 떠오르지 않았었다. 그래도 다행히 코테는 통과했었는데, 면접에서 어떤 식으로 더 최적화할 수 있겠냐는 질문이 듣지 마자 힙이 떠올랐었던 기억이 있다. 제곱의 합을 최소로 만들기 위해서는 가장 모난 놈부터 쳐내면 된다. 가장 모난 놈이라는건 여러 개의 숫자 중에서 가장 큰 놈이다. 반대로 최대로 만들기 위해서는 가장 작은놈부터 하면 될 것 같다. 가장 모난 놈을 쉽게 찾기 위해서는 Max Heap을 사용하면 되는데, 이는 C++ priority_queue라는 STL로 구현되어 있다. 우선 주어진 works 배열의 값들을 다 priorty_queue로 옮겨준다. 그 이후에 가장 큰 놈부터 빼..

처음에 문제를 보자마자 생각이 들었던 접근법은 DP나 그리디였다. 하지만 뾰족한 수가 떠오르지 않아서 다른 방법을 찾던 도중 간단한 아이디어가 떠올라서 테스트만 해보려고 했는데 정답을 받아버렸다. 어떤 한정된 수가 있고 그 수를 잘 나눠서 곱이 최대가 되기 위해서는 각 숫자들이 비슷해야 한다. 수학적인 워딩으로 다시 말하면 각 수의 편차가 적어야 한다. 이런 내용에 대한 포멀한 증명을 해본 적은 없지만 살다보니 경험적으로 깨우친 것 같다. 집합의 각 원소는 정수이므로 우선은 s를 n으로 나눴을 때의 몫을 구한다. 그리고 나머지는 원소에 적당히 1씩 배분하는 식으로 문제를 해결했다. vector를 사용했기 때문에 상당히 쉽게 구현할 수 있었다.

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 상당히 문제가 간단하다. 구구절절 상황극이 있지도 않고, 문제에서 주어지는 조건도 심플하기 때문에 문제를 이해하는데에는 시간이 얼마 걸리지 않았다. 하지만 처음 풀 때 두가지 정도의 예외 사항을 놓쳐서 바로 통과를 받지는 못 했다. 첫번째 예외 사항은 지우는 노드가 루트인 경우이다. 간단히 조건문을 사용해서 처리할 수 있었다. 두번째는 루트 노드 바로 밑에 붙어있는 노드를 삭제하는 경우다. 처음 구현에서는 트리 구조에서 따로 노드를 삭제해주지는 않고 BFS..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 간단한 그리디 문제였다. 그리디임을 알고 문제를 시작했기 때문에 완전히 문제에 대한 지식이 없이 풀었다고 하기는 힘들다. 문제의 핵심은 카드 수가 적은 묶음부터 합치는 것이다. 이 아이디어는 쉽게 떠올릴 수 있었는데, 8%대에서 틀렸습니다를 봤다. 그 이유는 새로운 카드 묶음을 다시 큐에 집어넣고 다시 두개를 뽑았어야 했는데, 큐를 새롭게 업데이트해주지 않았기 때문이다.