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) 각 친구들의 분노치 합을 최소로 만드는 문제이다. 이제부터 내가 이 문제를 풀기까지 사고한 과정을 정리하고자 한다..

https://www.acmicpc.net/problem/5520 5520번: The Clocks Read nine numbers from the standard input. These numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. The example in figure 1 gives the following input data file: www.acmicpc.net 백준 5520 The Clocks 문제이다. Figure 1과 같이 3x3 배열로 시계들이 있다. 우리의 목표는 모든 시계를 12시 정각을 가리키도록 최소한의 횟수로 돌리는 것이다. 시계를 돌리는 방법은 Fig..

냅색 문제를 공부하고나서 도전했던 문제이다. 스스로 아이디어를 찾는데에 실패해서 결국 검색을 통해 해결했지만, 이 문제를 통해 얻어갈 수 있는 부분이 있었기에 정리하고자 한다. 어떤 앱을 실행시키기 위해서 추가로 M의 메모리를 확보해야 하는 상황이다. 따라서 이 메모리를 확보하기 위해 기존에 실행 중이었던 앱을 끄고자 한다. 실행 중인 앱을 한번 끄면 다시 키는데 드는 시간 등 추가 비용이 발생하게 된다. 이 비용을 수치화 할 수 있다고 가정하면 실행 중이던 어떤 앱을 껐을 때 얻을 수 있는 메모리가 m, 발생하는 비용이 c로 정해진다. 이제 N개의 앱이 주어진다. 각각의 앱마다 m, c 의 값을 갖는다. 이 문제는 M이상의 메모리를 확보하기 위해 필요한 최소 비용을 구하는 것이다. 아직 냅색문제가 익숙..

동아리에서 DP를 배우면서 과제로 푼 '이진수 찾기'의 풀이 과정을 정리하고자한다. 처음에 문제를 딱 읽었을 때는 무슨 말인지 긴가민가 했다. 직접 써보면 간단하다. 만약 3자리 이진수 중, 2개 이하의 비트만 1인 것을 크기순으로 나열하면 다음과 같다. 000 001 010 011 100 101 110 이제 주어진 조건하에서 주어진 숫자 번째의 이진수를 찾아야한다. 처음에는 어떻게 풀어야할지 감이 안왔다. 그래서 예제 입력 1번 5 3 19 크기순으로 직접 나열해봤다. 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 10000 . . . 근데 여기까지 쓰고보니 뭔가 규칙이 보인다. 위 사진처..