https://www.acmicpc.net/problem/23059 23059번: 리그 오브 레게노 첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구 www.acmicpc.net 1. 아이템의 일부 구매 순서로 전체 구매 순서를 찾는다 => 위상정렬 2. 이때, 구매 과정이 현재 구매가능한 아이템을 모두 "찾기만 하고" 그 결과를 이름 순대로 구매한다. 이 점만 주의하면 된다. 나는 아이템은 맵으로 관리하고 우선순위큐와 위상정렬을 섞어서 풀었다. 맵에 저장한 아이템에 대해 위상정렬 한다. 현재 살 수 있는 아이템 리스트를 만든다. 만들면..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션, 구현, 브루트포스 유형의 문제이다. 생각보다 구현이 빡빡하다. (체감 난이도 골드4) 이 문제를 풀 때 내가 실수했던 부분은 하나였다. 감시구역이 겹치는 점을 고려하지 못한 것이다. 그래서 백트래킹으로 감시구역을 바꿀때, 다른 CCTV에 의해서도 감시되는 구역에 대해 감시를 풀어버린 것 때문에 틀렸었다. 그래서 숫자를 이용해 감시 카운트를 세도록 했다. 감시가 생길때마다 숫..
https://www.acmicpc.net/problem/15778 15778번: Yut Nori 윷놀이는 한국의 전통놀이중 하나로 윷가락을 가지고 진행하는 놀이이다. 윷놀이는 윷가락 4개와, 내 말 4개, 상대편의 말 4개로 총 말 8개 그리고 윷판 하나를 가지고 진행한다. 윷판은 다음과 www.acmicpc.net 진짜 디버깅.. 너무 힘들었다. 내가 스스로 고안한 풀이 방법으로 풀 땐 죽어도 안풀리다가,,,, 다른 사람이 사용한 구현 아이디어를 활용하여 구현하니까 한번 틀렸는데, 다행히 틀린 부분이 예제 입력 2번으로 디버깅이 되서 바로 통과됐다. (그래서 자존심에 매우 큰 스크래치를 입은 상태이다..ㅡㅡ) https://swoon1.tistory.com/4?category=804646 [파이썬] ..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 간만에 만난 진짜 너무 이해하기 어려웠던 문제이다. 이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..) 이 문제의 핵심은 3가지다. 1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다. 2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다. 3. 최소를 구할 때도 0을 조심하자. 1. 최적해는 결국 사이클..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 사이클에 속하지 않는 노드의 개수를 세는 문제이다. 생각보다 최적화를 깐깐하게 요구했던 문제이다. 하지만 덕분에 내가 놓치고 있던 부분을 확실하게 바로잡을 수 있었다. 살면서 처음으로..!! python 그룹 언어에서 제일 빠르게 푼 사람이 되보았다 ㅋㅋㅋ (21.12.17 오전 10시 30분 기준) 물론 저 32ms 차이는 크게 의미있는 차이는 아니지만.. 기분이 좋다 ㅎㅎ 이 문제의 알고리즘 분류는..
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제를 읽어보면 그냥 MST의 정의를 적은 것과 같다. 다만 다른 MST 기본 문제와 다르게 간선 정보를 직접 계산해야한다. 물론 별이 최대 100개까지라서 모든 별 사이의 간선을 다 구해놓고 시작하면 된다. 처음에는 소수점 계산하다가 문제가 생길 것 같아서 Decimal 라이브러리를 이용했는데, 혹시 몰라서 그냥 내장 float 자료형을 써보니 풀렸다. 그리고 시간차이는 내장 자료형을 쓰는 편이 ..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 난이도에 비해 티어가 높게 책정되었다고 생각하는 문제이다. (그리고 나와 똑같이 생각한 사람이 꽤 되는 것 같다.) 펠린드롬 문자열의 성질을 이용하면 아주 간단하게 풀 수 있다. 어떤 문자열이 펠린드롬이면, 그 문자열의 양끝 문자를 제외한 문자도 펠린드롬이다. 따라서 dp[s][e] 를 s 부터 e 까지의 문자열의 펠린드롬 길이라고 한다면 dp[s][e] = dp[s+1][e-1] + 2 이다. 단, 위 점화식의 조건은 dp[s+1][..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net BFS를 응용한 단순 구현문제이다. 내가 푼 알고리즘은 다음과 같다. 1. 외곽을 모두 돌면서 빈공간의 위치를 덱에 넣고, 열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 덱에 넣고, 문은 맵에 문 위치를 저장한다. (이때 같은 문이 여러개 있을 수 있으니, 맵에 리스트를 저장한다.) (열쇠는 같은 열쇠가 여러개 있을 수 있으니 집합에 저장한다.) 2. 현재 갖고 있는 열쇠로 열 수 있는 문을 모두 연다. 문을 열..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 오늘 백준을 들어가보니 AC Rating이 갑자기 50정도 늘어나있었다. 아무 문제도 푼게 없는데 무슨 일인가 싶다...ㅋㅋㅋ 얼떨떨한 기분으로 푼 문제, '도시분할계획'이다. 이 문제는 MST 응용문제인데, 두 MST의 합을 최소로 해야한다는 점이 조금 까다롭게 느껴졌다. 처음에는 두 MST에 속할 노드를 백트레킹이나 조합으로 골라서 매번 MST를 구해야하나..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 단순 BFS 문제를 구현하기 어렵게 내면 이렇게 나올 수 있다는 걸 보여준 문제이다.. 2048과 비슷하게 그냥 상하좌우 이동을 구현하고, 모든 경우의 수를 세면 된다. 각 이동마다 가능한 경우의 수가 상하좌우 4방향 이고, 10번을 넘는 이동은 의미가 없으므로 진짜 의미로 모든 경우의 수는 4^10 = 약 100만 의 경우의 수겠지만, 이 경우의..
