https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 문제를 풀고 싶어서, solved.ac의 그래프 태그 문제를 찾아보다가 발견한 문제이다. 스타크래프트를 연상시키는 문제인데, 그래프에 DP를 섞은 재미있는 문제였다. 우선 이 문제는 문제에서 주어진대로 시작하는 건물부터 차근 차근 건물을 지어나가다가 마지막에 원하는 건물을 짓게되면 멈추는 풀이로는 접근이 쉽지가 않다. 그래서 거꾸로 원하는 건물을 짓기 위해 지어야 하는 건물들을 역탐색..
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 설명을 간단하게 하면, 내 오른쪽에 있는 숫자들 중, 나보다 큰 첫번째 숫자를 찾는 문제이다. 5 2 3 8 이면, 5 입장에서 오른쪽에서 가장 처음만나는 자기보다 큰 숫자는 8, 2 입장에서도 8 3 입장에서도 8이다. https://www.acmicpc.net/problem/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000..
www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net 학교에서 분리집합 스터디 이후 연습문제로 풀게된 문제이다. 난이도는 solved.ac 기준 플레티넘3 이다. 분리집합이라는 아이디어를 갖고 시작할 수 있다면 난이도는 골드 수준으로 내려갔을 것 같다. 문제 설명을 읽어보면 복잡하다. 술을 서랍에 정리하는 순서가 다음처럼 나와있다. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보..
www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 응용문제로 풀게된 문제이다. solved.ac 기준 플래티넘 5의 난이도를 가진 문제이다. 정말 플레티넘답게 쉽게 안풀리는 문제였다. 질문게시판의 반례와 대회 테스트케이스를 활용해가며 4시간만에 풀었다.. 내가 문제에 접근한 방법, 문제를 푼 아이디어를 기록하고자한다. 이 문제를 푸는 큰 흐름은 다음과 같다. 다익스트라(최단거리 계산) -> 최단 경로들 삭제 -> 삭제한..
www.acmicpc.net/problem/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 문제를 보자마자 DP로 풀면 되겠다는 생각을 떠올리는 것은 어렵지 않았다. DP 점화식을 떠올리는 과정이 익숙하지가 않아서 (특히 2차원 이상으로 갈 경우..) 점화식을 고민하고 구현하는데 시간을 많이 쏟았다. 문제를 풀고나니 알고리즘 분류에 냅색문제로 되어있는 것을 보았는데, 생각해보니 냅색문제와 점화식을 도출한 과정이 비슷했다. 문제를 풀기위해 사고한 과정을 정리하고자 한다. 맨 처음엔 모든 경우의 수를 다 체크해보..
www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 그리디 알고리즘 연습문제로 풀게된 '이사' 문제이다. 고민끝에 다른 분의 풀이를 봤다. burningjeong.tistory.com/293 17371 이사 이런 문제가 기하인가? 원 공식이랑 비슷하니 원을 사용하나? 고민 많이 했는데 그리디 문제였다. 길이의 평균을 구하는 거라 집이 편의점 위에 가도 값의 차이는 없다. ..
대표적인 스택 활용 문제이다. 두시간을 왜 틀렸는지도 모른채 끙끙 앓았다. 결국 대회 테스트 케이스까지 가져다가 일일히 대입해서 반례를 찾기는 했는데, 결과값이 워낙 길다보니 텍스트 비교 사이트를 활용해가며 고민한 결과 문제점을 결국 알아냈다.. 내가 떠올린 풀이법의 큰 틀은 다음과 같다. 1. 폭탄문자열의 각 문자와 그 문자의 인덱스를 맵으로 저장한다. 2. 주어진 문자열에서 한문자씩 반복하여 체크한다. 3-1. 그 문자가 폭탄문자열에 속해있지 않으면 정답 큐에 해당 문자를 넣는다. 3-2. 그 문자가 폭탄문자열에 속해있다면 그 문자의 인덱스를 가져온다. 4-1. 가져온 인덱스가 0이면 묻지도 따지지도 않고 count 스택에 넣는다. 4-2. 가져온 인덱스가 스택 상단의 인덱스보다 1크다면 스택 상단의..
BFS 연습문제로 풀게된 '루머' 문제이다. https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 복잡한 문제지만, 보자마자 BFS를 떠올리는 것은 어렵지 않았다. BFS의 연습문제인 바이러스, 연구소 문제와 닮았다. 중간에 체크해야 하는 조건 하나가 추가되어서 귀찮은 것이 이 문제가 골드인 이유일 것이다. 내가 떠올린 아이디어는 러프하게 이 문제의 풀이과정을 그대로 따라가는 것이었다. 나는 파이썬에서 덱으로 ..
https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 초급 알고리즘 DP 강의를 수강 후 연습문제로 풀게된 문제이다. 문제는 간단하다 1과 5로 이루어진 N자리 수 중 15의 배수를 구하는 문제이다. 어떻게하면 이 문제를 DP를 활용하여 구할 수 있을까? 아무런 아이디어가 떠오르지 않았다. 그래서 그냥 무작정 써봤다. 1자리수 1, 5 0개 2자리수 11, 15, 51, 55 1개 3자리수 111, 115, 151, 155, 511, 515, 551, 555 근데 3자리수를 쓰고보니 15의 배수가 한눈에 안보인다. 일일히 나눠보는 생각을 했지만..
중급 알고리즘 - 그리디 수강 후 연습 문제로 풀게된 문제이다. https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 www.acmicpc.net 친구들에게 사탕을 나눠줘야하는데 사탕은 반드시 모자라다. 내가 원하는 사탕이 10개인데, 사탕을 5개만 받았다면 그 친구는 못받은 사탕개수의 제곱만큼 분노하게 된다. (분노치 5*5 = 25) 각 친구들의 분노치 합을 최소로 만드는 문제이다. 이제부터 내가 이 문제를 풀기까지 사고한 과정을 정리하고자 한다..
