표현 가능한 이진트리
재귀, 구현
문제 링크 해결 전략 문제에 접근법은 처음에 구상한 게 맞았으나, 구현에서 조금 애를 먹었다. 알고리즘 풀 때는 타입스크립트가 아닌 자바스크립트를 사용해서 그런가 자잘한 타이핑 오류가 있었다. 우리에게는 십진수가 주어진다. 완전이진트리를 사용하여 이진법을 제작했을 때, 해당 십진수를 이진법으로 표현할 수 있는지 문제이다. 우리가 해결해야 할 문제는 이진법으로 표현할 수 있는지, 즉 완전이진트리모양을 만족시킬 수 있는지이다. 부모 노드 아래 더…
2023-03-11
미로탈출명령어
그리디
문 제 링크 해결 전략 격자 미로에서 출발지와 도착지를 가는 길 중 문자열이 사전 순서에서 가장 작은 길을 구해야한다. 격자 미로: 격자 미로일 경우 우리는 어느 한 지점에서, 다른 지점까지의 최단 거리를 매우 쉽게 알 수 있다. 예시로 (a1,b1), (a2,b2) 두 좌표일 때 최단 거리는 |a1-a2|+|b1-b2| 이다. 사전 순서에서 가장 작은 길: 방향을 문자열로 치환하였을 때, 사전 순으로 나열하면 d, l, r, u이다. 단어를 …
2023-03-10
이모티콘 할인행사
중복 순열, 완전 탐색
문제 링크 해결 전략 우리는 문제에 주어진 우선순위에 맞게 최대 이모티콘 서비스 가입자수와 판매액을 구해야한다. 이 문제는 완전 탐색으로 해결할 수 있는 문제이다. 우리는 이모티콘별 적정 할인률을 구해야하는데, 이모티콘의 할인률은 10%,20%,30%,40% 중 하나이다. emoticons의 최대 길이는 7로 최대의 시간 복잡도를 계산해보면, 100 * (4 ** 7)로 충분하다. (n=100, emoticons의 길이 7) 완전 탐색 알고리…
2023-02-09
택배 배달과 수거하기
그리디
문제 링크 해결 전략 우리가 구해야 하는 것은 트럭의 최소 이동 거리이다. 트럭이 최소의 거리로 모든 상자를 배달하고 수거하기 위해서는, 출발지로부터 가장 거리가 먼 집부터 처리해야한다. 출발지로부터 가장 거리가 먼 집부터 처리하는 이유는, 짧은 거리는 긴 거리에 포함이 되기 때문에 짧은 거리에 있는 집을 먼저 처리해도 긴 거리에 있는 집을 가기 위해서는 동일한 루트를 반복해서 가야한다. 하지만 긴 거리에 있는 집부터 처리하면 반복해서 가야하…
2023-02-09
부대복귀
다익스트라 알고리즘
문제 링크 해결 전략 위 문제는 한 노드에서 다른 노드의 최단거리 찾기 문제이다. 즉 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다. 다익스트라 알고리즘은 그리디 알고리즘의 일종인데 방문한 노드에서 최단거리를 가지는 노드를 찾는 알고리즘에서 시간 복잡도 차이가 발생한다. 노드의 방문 여부를 통해 최단거리를 찾는 알고리즘의 경우 모든 노드를 순회해야하므로 O(n^2)의 시간 복잡도를 가진다. 하지만 문제의 경우 n이 100,000으로 O…
2022-11-22
스타수열
백트래킹
문제 링크 해결 전략 처음에 이 문제를 완전탐색 형태로 해결하고자 하였다. a의 부분 수열을 모두 만들고, 스타 수열인지 확인하는 방식으로 알고리즘을 짰다. 하지만 이 방식은, a의 길이가 최대 500,000이므로 절대 만족할 수 없다. 조합의 경우 O(2^n)의 시간 복잡도를 가지기 때문이다. 그렇다면 반대로 생각해봐야 한다. 모든 부분 수열을 만들어보고 스타 수열인지 검증하는 대신, 주어진 배열을 활용해서 직접 스타 수열을 만들어보면 된다…
2022-10-13
기지국 설치
투포인터
문제 링크 해결 전략 이 문제는 아이디어로 푸는 문제이다. 우리가 구하고자 하는 값은 추가적으로 설치된 기지국의 개수이다. 즉, 기지국이 어디에 설치되는지는 알 필요가 없다는 의미이다. 작은 예시를 통해서 설치해야 할 기지국 개수를 알아본다. 만일 기지국이 전혀 없는 4개의 아파트가 있다고 가정하고, 전파 도달 거리가 1이라면 몇 개의 기지국 설치가 필요할까? 1개의 기지국이 차지하는 영역은 본인의 자리 + 앞 뒤로 w 만큼이다. 즉 2*w+…
2022-10-12
섬 연결하기
크루스칼 알고리즘
문제 링크 해결 전략 최소의 비용으로 모든 섬이 통행 가능하도록 만들 때, 필요한 최소 비용을 구하라는 문제이다. 모든 섬이 통행 가능하도록 이란 의미는 신장 트리를 만족해야 하고, 최소 비용을 구해야 하기 때문에 최소 신장 트리 구조를 만족해야 한다. 크루스칼 알고리즘은 최소 신장트리를 만족하면서 최소 거리를 구할 수 있는 알고리즘이다. 정답 코드
2022-10-09
여행 경로
DFS/BFS
문제 링크 해결 전략 우리는 주어진 항공권을 모두 이용해야한다. 즉 항공권을 모두 사용하는 케이스를 탐색해야한다. 만일 가능한 경로가 2개 이상 있을 때, 알파벳 순서가 앞서는 경로를 리턴해야 하므로 BFS로 탐색하고 만족하는 값을 찾으면 탐색을 중지하도록 하겠다. 탐색하는 방법은 간단하다. 티켓 중에서 시작점이 마지막에 방문한 도시와 일치하는 티켓들을 찾고 알파벳 순서로 정렬 후 방문한다. 이 과정을 모든 티켓을 사용(방문)할 떄 까지 반복…
2022-10-06
이중우선순위큐
힙, 정렬
문제 링크 해결 전략 이 문제의 operation은 최대 1,000,000이다. 따라서 최댓값, 최솟값을 제거해주기 위해서 굳이 힙을 사용하지 않고도 정렬을 사용해도 좋다. sort 메소드를 사용한다면 O(NlogN)으로 문제를 해결할 수 있다. shift 메소드의 경우 O(N)의 시간이 소모되므로, 매번 정렬을 수행하는 것보다 shift 메소드를 사용하는 것이 더 빠르다. 따라서 작성한 알고리즘은 아래와 같다. 전체 코드 추가 문제의 이름이…
2022-10-06
숫자 게임
그리디
문제 링크 해결 전략 우리는 B의 순서를 조정할 수 있다. 따라서 A의 순서를 바꿔도 상관없다. 순서가 변경된 A에 맞춰서 B의 순서를 변경하면 되기 때문이다. 우리는 근소한 차이로 이길 때, 최대한 많이 이길 수 있다. 예시로 1을 이기는데 9를 낼 필요는 없다는 것이다. 내가 2를 보유하고 있다면 2를 내는 것이 이득이다. 나중에 7과 같은 큰 수를 만나면 그 때 9를 내야한다. 위의 두 생각을 바탕으로 나는 A와 B를 내림차순으로 정렬하…
2022-10-05
야근지수
최대힙
문제 링크 해결 전략 초기에는 완전 탐색으로 접근해보았다. 하지만 n을 works에 분배하는 과정에서 무조건 시간 초과가 발생할 수 밖에 없다. 따라서 문제의 특성을 이용한 다른 접근 방법이 필요하다. 우리는 배열 내 요소의 제곱의 합의 최솟값을 구해야한다. 제곱의 그래프는 우측으로 이동할수록 급격히 증가하는 그래프 형태를 띄게 된다. 반대로 말하자면 좌측으로 이동할수록 급격히 감소한다는 의미이다. 우리는 최솟값을 구해야 하므로 감소하는 폭을…
2022-10-04
스티커 모으기
다이나믹 프로그래밍
문제 링크 다이나믹 프로그래밍인 이유 문제의 해결 전략이 다이나믹 프로그래밍으로 도출되어야 하는 이유는 2가지이다. 시간 복잡도를 줄여야 한다. 작은 문제의 해답이 그것을 포함하는 큰 문제에서도 동일하다. 1. 시간 복잡도 스티커의 최대 길이는 100,000개이다. 만일 완전 탐색으로 어떤 스티커를 뜯었는지, 안뜯었는지 고려하여 구한다면 시간 복잡도는 최대 O(2^50000)으로 불가능하다. 2. 작은 문제의 해답이.. 스티커 전체 배열이 […
2022-09-30