이름 못 정한 블로그

설명을 읽다 보면 또리디인가 하는 생각이 들었다. 하지만 제한사항을 보는 순간 아 이건 무조건 선형 아니면 로그 복잡도를 가진 문제라는 게 보인다. 입국 심사를 기다리는 사람이 최대 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를 사용했기 때문에 상당히 쉽게 구현할 수 있었다.

문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다..

문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 방금 푼 백준 문..