본문 바로가기

알고리즘 온라인 저지

 (48)
BOJ 1463 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 과거에 올린 BOJ 1697 숨바꼭질 과 동일한 문제이다. 다만 차이가 있다면 숨바꼭질은 +1, -1, *2 연산을 허용했다면 이번 문제는 -1, /2, /3 연산을 허용한다는 것만 다르다. 그래서 이번에는 숨바꼭질 문제와 반대로 목적지 ( = 1)에서 시작하여 역연산 (*2, *3, +1)을 하여 답을 찾아보기로 한다. 규칙은 아래와 같다. (규칙 A) 현재 도달 가능한 숫자를 큐에 저장한다. (규칙 B) 저장된 숫자를 하나씩 꺼내어 *2 / *3 / +1 연산을 해준다. (규칙 C) 규칙 B에 의해 연산된 결과에 해당하는 숫자가 기존에 탐색되지 않았다면, 해당 숫자에 현재..
BOJ 1339 단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 단어들의 합이 최대가 되어야 한다는 점 때문에 자칫 착각할 수 있지만, 문제 자체는 각 단어들에서 가장 많이 등장한 알파벳부터 9, 8, 7, ... 0 의 가중치를 주기만 하면 되는 간단한 문제이다. 하나의 단어에 대하여 문제를 풀 수 있다면 여러 개의 단어를 대상으로도 같은 해법으로 접근이 가능하다. 위와 같이, 단어 테이블과 알파벳 테이블을 이용하여 단어 한 개에 대하여 문제를 해결한 뒤, 여러 개의 단어에 상황에 적용해보자 아이디어를 간단하게 정리할..
BOJ 2178 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 찾기 문제이지만 최단거리를 구해야 하므로 가장 간단한 BFS를 이용하여 푼 문제이다. 오른쪽과 같이 문제에서 제시된 미로를 이용하며. 큐를 이용한 BFS를 이용하여 간단하게 문제를 풀고자 한다. 이때 일반적인 미로 찾기 입문 문제처럼 스택을 이용하지는 않는다. 그 이유는 스택을 이용할 경우 미로 최단경로를 찾기 위해서는 휴리스틱을 추가로 사용해야 하기 때문에 내용이 많아지기 때문이다. 휴리스틱을 위한 포스팅은 이후에 따로 하도록 하겠다. 위의 미로 지도와, 큐, 들어갈 노드를 이용해서 이..
BOJ 1238 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 특정 노드로 이동했다가 돌아와야 한다는 점을 추가해야 하는 최장/최단 거리 탐색 문제이다. 다익스트라 알고리즘의 동작에 대하여 잘 모른다면 [링크] 를 우선 참조하자 노드 A에서 출발했다 가정했을 때, 이미 방문한 노드 그룹에 대한 처리와, 이후에 필요할 다른 임의의 노드에서 A 노드로 왔다가 임의의 노드로 돌아가는 (= A에서 출발해서 임의의 노드로 이동하는) 값을 이용하기 위하여 아래와 같이 memo 변수를 추가로 이용했다. 그..
BOJ 1202번 보석 도둑 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 정답으로 출력할 값이 int의 영역을 벗어나는 것을 예측 못해서 시간을 조금 소비했던 문제였다. 문제 자체는 그리디 알고리즘의 정석에 가깝다고 생각된다. 문제에서 주어진 예시는 설명에 적합하지 않은 관계로 아래와 같이 임의로 만든 예시를 가지고 설명을 진행한다. 이 문제는 가방 1개당 가져갈 수 있는 보석이 1개로 1 대 1 매칭이 된다. 용량이 20 짜리 가방에 무게가 1짜리 보석을 넣어도 해당 가방..
BOJ 2014 소수의 곱 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제를 어렵게 생각하지 않는 것 이 중요한 문제다. 각 소수마다 계산해야 하는 대상이 달라질 수 있는데, 그 대상을 새롭게 탐색하지 않는 부분에 포인트를 맞추어 구현했다. 최초에 정답 확인용 리스트에 1을 넣은 채로 시작하도록 하자. 파란 사각형은 입력으로 주어진 소수들을 의미하고, 파란 사각형 밑에 붙을 흰색 작은 사각형은 각 소수의 연산 대상이라고 생각하면 된다. 자세한 내용은 아래에 기술한다. 각 소수 별로 다른 우선순위 큐 를 ..
BOJ 1916 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 바로 이전 글인 1753번 문제 최단경로와 동일하게 다익스트라 알고리즘으로 해결 가능한 문제이다. BOJ 1753번 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 dev-game-standalone.tistory.com 동일한 풀이를 갖는..
BOJ 1697번 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 피보나치수열을 구하는 것만큼이나 간단한 동적 계획법 문제이다. 동적 계획법은 상향식 계산과, 하향식 계산으로 구분되는데, 오늘은 1697번 문제를 상향식 구현을 해본다. 수빈이와 동생이 놀고 있는 점들을 아래와 같이 나타냈다. 상향식 동적 계획법 (= tabulation) 이므로 모든 경우의 수를 다 구하며 정답을 향해 갈 것이다. 규칙은 아래와 같다. (규칙 A) 현재 시간에 탐색된 점들을 저장한다. (큐 등을 이용) (규칙 B) 저..

티스토리툴바