https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 알고리즘 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다. 신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 작성하..
Koala - 9기/코딩테스트 준비 스터디
0. 잡설 오랫동안 고민하던 문제를 풀게되어 글을 작성합니다. 유니온 파인드로 정답을 풀 수 있었습니다. 삽질한 기록까지 적어놓아 생각을 정리하려고 합니다. 1. 삽질 유니온 파인드 알고리즘을 연습하는 중이라 처음에 삽질이 있었습니다. 처음 생각해낸 아이디어는 다음과 같았습니다. 진실을 아는 사람은 parents배열 인덱스를 0으로 지정하고, 파티에서 진실을 아는 사람과 모르는 사람이 있는 경우, 진실을 알게된 사람의 parents배열 인덱스를 0으로 지정하자! 하지만 이렇게 하면, 순서에 따라 답이 다를 수 있었습니다. 예를 들어 다음과 같은 예제가 있겠습니다. 5 4 1 5 2 1 2 2 2 3 2 3 4 2 4 5 잘못된 생각으로 적용된 알고리즘입니다. 순서에 따른 parents 배열 변화를 적어보..
문제 분석 해당 문제를 가장 쉽게 풀려면 모든 경우를 다 확인해 보는 방법이다. 해당 알고리즘의 시간복잡도는 O(N^3)이므로(L 움직임 O(N), R 움직임 O(N), 중복 체크 O(N)) 시간을 초과하게 되어 최적화가 필요하다. 최적화 방법으로는 투포인터와 Count 기록 방법을 활용하겠다. 투포인터를 통해 Left와 Right를 움직이는 시간복잡도를 O(N)으로 줄이고 방문을 기록하여, 중복의 유무를 일일히 체크하는 것이 아닌 배열을 통해 한번에 알 수 있으므로 O(1) 만큼 걸린다. 따라서 이 방법대로 풀이하면 시간복잡도는 O(N)안에 문제를 해결할 수 있어 해당 방법으로 문제를 풀었다. 주의할 점은 Scanner를 사용하면 메모리가 초과된다는 점이다. BufferReader에 비해 시간이 오래걸..
https://www.acmicpc.net/problem/23354 23354번: 군탈체포조 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라 www.acmicpc.net 문제 분석 난이도 골드3 분류 다익스트라, 브루트포스 들어가기 전에 제 1회 KAUPC 출제 문제 문제 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라는 명령이 주어졌는데, 돈을 아껴 봉지라면을 사 먹고 싶은 호열이는 활동비..
문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net Algorithm 다익스트라 문제이다. g와 h의 교차로(gh)를 지난 경로는 최단경로여야 하므로, (출발점에서 목적지에 가는 최단경로의 길이) = (출발점에서 gh를 지나 목적지에 가는 최단경로의 길이) 이어야한다. gh를 지나는 경로의 경우는 다음과같다. (출발점) → g → h → (목적지) (출발점) → h → g → (목적지) 즉, 출발점에서 목적지에 가는 최단경로의 길이..
다익스트라를 사용해 푸는 문제 평범한 골드 5 문제라고 생각했다가 시간 초과 2번 맞고 다익스트라를 잘못 이해하고 있었단 걸 알았다. 시간 초과의 원인 https://www.acmicpc.net/board/view/34516 7번 항목을 고려하지 않고 코드를 작성했기 때문에 시간 초과를 받았다. 평소에는 저 부분을 고려하지 않고 풀어도 잘 통과했다. 하지만, 정점이 10만개가 되니, 불필요하게 탐색되는 정점의 수가 누적돼 시간 초과로 이어졌다. 어떻게 해결했나? 매우 간단하다. 기존 코드에 2줄만 추가하면 됐다. 문제의 코드 while q: hereC, here = heapq.heappop(q) for there, thereC in graph[here]: cost = thereC + hereC if di..
문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다. 입력 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 분석 그림을 2차원 배열에 RGB값을 넣어서 주고, 배열 내에서 상하좌우에 같은 값이 있다면 하나의 구역으로 본다. 적록색약이 아닌 사람이 봤을 때 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 개수를 구하는 문제이다. 코드 #include using namespace std; typedef long long ll; int N; char picture[100][100]; bool ..
문제 https://www.acmicpc.net/problem/9202 Algorithm 보드판의 각 지점에 대하여 DFS를 진행해 문자열을 만들어나간다. 현재까지 만들어진 문자열이 사전에 등재되어 있는 단어라면 최대 점수, 가장 긴 단어, 찾은 단어의 수를 갱신한다. 사전에 등재되어 있는 단어인 것은 어떻게 파악하는가? 사전의 단어들이 정렬되어 있을 필요는 없으므로, unordered_map 자료구조를 활용한다. 탐색 종료 조건은? 문제의 조건에 따라 단어의 길이는 최대 8글자이므로, 만들어진 문자열의 길이가 8을 초과한다면 종료한다. b개의 보드판을 탐색하게 되므로, 초기화에 주의한다. 또한, 이미 발견한 단어에 대해서는 map의 bool 값을 true로 표시한다. Code #include #incl..
문제 분석 해당 문제의 경우, 서로 다른 폰켓몬의 종류가 내가 선택해야 할 폰켓몬 보다 작을 경우에는 폰켓몬의 종류를 모두 고르고 부족한 폰켓몬은 중복된 종류의 폰켓몬을 선택하고, 내가 선택해야 할 폰켓몬 보다 크거나 같은 경우 서로 다른 폰켓몬을 모두 고르면 된다. 집합에 해당 배열의 폰켓몬을 넣어줌으로써 중복을 제거했다. 중복을 제거하면 입력받은 폰켓몬의 종류를 알 수 있다. 시간복잡도의 경우 set에 집어넣는 O(n)이 소요되므로, nums 길이의 최대값인 10,000 들어와도 충분히 시간안에 돈다. 문제 풀이 import java.util.*; class Solution { static Set set; public int solution(int[] nums) { int choiceNumber = ..
완전 탐색 배열을 모두 순회하는데 O(100 * 100) 이 필요하다. 최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다. 차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다. 총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다. 완전 탐색 최적화 배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다. 하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다. 따라서, ..
https://www.acmicpc.net/problem/7117 7117번: Sevens, twos and zeros The number s as described above must be output on the screen. If it is not possible to find the corresponding value of s to the given value of n, output one word "NAV". www.acmicpc.net 문제 분석 난이도 플래티넘5 분류 중간에서 만나기(MITM), 그래프 탐색, 너비우선탐색 들어가기 전에 중간에서 만나기 알고리즘을 알고 있어야 쉽게 풀 수 있는 문제 문제 최대 길이가 20이고 2, 7, 0으로 이루어진 0으로 시작하지 않는 수가 있다. 이 수들..
