문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 이 문제도 비트마스크로 풀었지만 사실 DFS방법의 백트래킹으로도 충분히 시간 내에 해결 가능하다. 또한 본인은 비트마스크와 브루트포스만으로 해결했지만 백트래킹을 같이 활용한다면 훨씬 빠르게 해결이 가능하다. 남극언어의 단어들은 모두 'a', 'c', 'i', 'n', 't' 를 가져야만 한다. 따라서 비트마스크 표현 시 비트들은 모두 해당 ..

문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 solved.ac 난이도: Sliver 3 비트 마스크로 분류되어 풀어보았는데 사실상 메모리 제한이 크기 때문에 다른 기법으로도 충분히 해결 가능했던 문제이다. 본인은 비트마스크로 모든 경우의 수를 살펴보는 브루트포스 알고리즘을 사용했다. 비트 마스크로 사람의 수(player_num)를 반으로 나눈 팀을 형성하기 위해 아래와 같이 1~(1

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 solved.ac 난이도: Silver 3 이분 탐색의 응용인 parametric search를 이용하는 대표적인 문제이다. 이분 탐색(binary search)과 parametric search의 차이점은 라몽님의 게시글을 참조하자. 이진탐색(Binary Search)와 Parametric Search - 라몽의 배움일기 left는 0에서부터 r..

문제 https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 그리디 문제로 분류되었지만 이분 탐색을 응용한, parametric search를 사용해야 했던 문제이다. 이분 탐색(binary search)과 parametric search의 차이점은 라몽님의 게시글을 참조하자. 이진탐색(Binary Search)와 Parametric Search - 라몽의 배움일기 해당 문제의 풀이는 다음과 같다. ..

문제 https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 정렬을 해서 푸는 것까지는 생각해냈지만 0을 지나는 노선의 처리하지 못하여 틀린 그리디 문제. 해당 문제는 0을 지나지 않는 노선(line_v)와 0을 지나는 노선(cross_line_v)로 나누어 해결해야 한다. 1. 0을 지나지 않는 노선(line_v) 해당 노선들은 시작점(start)을 기준으로..

문제 https://www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2second)); else right_v.push_back(make_pair( abs(school_pos - it->first),it->second)); } Colored by Color Scripter cs 그 후 먼 곳부터 정렬되도록 left_v, right_v를 내림차순으로 정렬해준다. 이제 먼 곳부터 방문하면서 정원을 채우는 코드를 구현한다. 1. 남은 자리(left_sit) 보다 해당 위치(apt_idx)에서 태울 학생 수가 적다면 모두 태우고 해당 위치의 학생 수는 0으로,..

문제 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 solved.ac 난이도: Silver 2 간단한 그리디 알고리즘 문제. 주식은 낮을 때 사서 높을 때 팔아야하는 것처럼 해당 문제도 같은 방식으로 풀 수 있다. 주가를 입력받은 stock_value을 역순으로 진행하면서 두가지를 확인하면 쉽게 구할 수 있다. 1. 현재(day)의 주가가 지나온 주가 중에서 최대 주가(max_stock)보다 작다면 해당 주식은 구매해서 ma..

문제 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 탐욕법과 동적계획법을 이용해야하기 때문에 까다로웠던 문제이다. 풀이는 마이구미님의 게시글을 참고하였다. 문제를 풀기 전에, 이전 단계 문제라고 볼 수 있는 백준 - 줄 세우기(2631)을 함께 풀어보면 좋다. 2631번 줄 세우기 문제에 사용되는 동적계획법의 알고리즘은 LIS(최장 증가 부분 수열)이다. 해당 문제는 어느 위치로든 이동시킬 수 있으므로 L..

문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 그리디(탐욕법) 문제이지만 브루트 포스도 이용하여 문제를 해결하였다. 일단 pair의 first에 남은 일자를, second에 점수를 저장하고 남은 일자를 기준으로 내림차순 정렬을 하자. 문제의 예제는 아래와 같이 정렬된다. 6 5 4 60 4 40 4 10 3 30 2 50 1 20 기간이 많이 남을 수록 앞쪽으로 정렬되기 때문에 최대 기한인 6일을 기준으로 day_cnt를 하루하루 줄이면..

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 아이디어는 단순했지만 구현하기가 까다로워서 코드가 엉망 친창이 되어버렸다.. 문제를 파악했다면 높은 자릿수에 자주 나오는 알파벳일 수록 큰 수를 대입해 주면 된다는 것을 알 수 있을 것이다. 예를 들어 아래와 같은 입력이 주어졌다고 생각해보자. ACA BCC 여기서 100의 자리 수는 A와 B 두 가지가 존재한다. 그렇다면 A와 B 중에서 어..