문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 어떻게 풀 것인가? 오랜만에 알고리즘 포스팅을 하는 것 같다. 코테 실패 이후 다시금 알고리즘 공부를 빡세게 해야할 것 같다. 이번에는 로또문제이다. 다만 문제를 읽어보자. 1 ~ 49개의 숫자중에 K개의 수를 뽑아서 이중에서 또 6개의 숫자를 골라야한다. 즉, 조합 문제이다. 이 문제의 경우 백트레킹이나 재귀를 이용한 조합 알고리즘을 이용한다면 쉽게 풀 수 있다. static v..
문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽어보면 그래프DFS 관련된 문제라는 것을 알 수 있다. 다만, 문제의 경우 문제 요구 사항을 보면 그리디를 요구한다. 가스관과 빵집을 연결하는 파이프라인의 최대 개수로 나올 수 있는 방법은 무엇일까에 대해서 고민을 많이했다. 그래서 열을 이용한다는 것에 착안하였다. 결국엔 위에서부터 차근차근 되는 것부터 게산하면 된다. (이것이 그리디인가 싶다.) 배열 한 곳에서 오른쪽 위, 오..
문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽으면서 방향성 자체는 DP로 잡았다. DP에서 중요한 것은 점화식이다. 그래서 우선적으로 그냥 바텀업 방식과 메모제이션으로 문제를 풀었다. 메모이제이션 (Memoization) 이란? DP를 구현하는 방법 중 한 종류이다. 한 번 구한 결과를 메모리 공간에 메모해두고 --> 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. (값을 기록해 놓는다..
문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 어떻게 풀 것인가? 문제를 읽었을 때 2차원 배열이 보이고 탈출 구멍에 따라 빨간 구슬이 먼저 와야하며, 최소한적으로 판을 흔들어야한다고 했을때는 BFS 문제이구나 싶었지만, 구현이 가미된 BFS였다. 구현은 어렵다. 단순 정답이 정해진 것이 아니라 정말 생각한 것을 프로그래밍으로 구현할 수 있냐? 라는 것을 묻기에 더 그런 것 같다. 처음에..
문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 어떻게 풀 것인가? 문제를 천천히 읽어보자. 두 전봇대 사이 A와 B에서 교차를 하면 안된다. 여기서 단순 구현이라기엔 시간제한 1초이며, 주어진 데이터(전깃줄의 개수)는 100,000 이하의 자연수이다. 브루트포스로 푼다면 1초를 훌쩍 넘긴다. 문제에서 주어진 두 전봇대에 주어진 숫자를 하나의 기준으로 정렬을 해본다면, 인덱스와 값이 보인다. 즉, 가장 긴 오름차순 수열이 아닌 것들을 ..
문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽어보자. ", 두 사람의 친구 네트워크에 몇 명이 있는지 구하는" 이라는 어절을 읽었을 때, 집합에 대한 개념과 이를 이용한 유니온-파인드 알고리즘을 떠올려서 문제를 풀었다. 하지만 시간초과가 발생했다. 왜 일까? 단순 유니온 - 파인드 알고리즘만을 이용한다면, 공통된 친구를 찾는 부분에서 시간초과가 발생했다. 그래서 HashMap을 이용하여 시간복잡도..
문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 어떻게 풀 것인가? 2개의 우선순위큐를 이용한다. 각각을 minHeap 그리고 maxHeap으로 선언하고 작은 값을 우선순위로 가지는 큐는 Compartor인터페이스를 사용하여 메소드를 오버라이딩한다. 두개의 우선순위 큐의 크기가 같은 경우는 maxHeap에 입력된 값을 추가하고, 입력한 값이 minHeap의 최솟값보다 크다면 둘을 swap한다. 두개의 크기가 다른 경우 mi..
문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 어떻게 풀 것인가? 최소 스패닝 트리(MST) 와 그로 인한 크루스칼 알고리즘을 이용하여 문제를 해결하였다. 아래 코드를 참고해보면 알겠지만 언뜻보면 유니온-파인드 알고리즘 처럼 보일 수 있겠으나 편의를 위해서 함수명을 그렇게 작성을 하였다. 사실 이 문제의 경우 "최소 스패닝 트리와 크루스칼 알고리즘을 알고있어?" 라는 것을 물어보는 것 같았다. 특수한 스킬이나 응용이 필요한 것은 없었다. 물론 최소 스패닝 트리와 크루스칼 알고리즘은 어렵다... 풀면서 놓쳤던점 X 이 문제를 통..
