아롱이의 PS하는 블로그

DFS. 참 유용하고도 많이 쓰이는 고마운 그래프 순회 알고리즘이다. 딱 하나 아쉬운 것이 있다면 재귀함수를 이용하기 때문에 파이썬에서 쓸 때는 좀 불편하다.파이썬 유저들은 대부분 아래 상황을 겪어본 적이 있을 것이다. 1. DFS 코드 짜고, 제출 -> RecursionError2. sys.setrecursionlimit 늘리기2-1: AC(아주 낮은 확률, 그리고 시간을 간당간당하게 넘김)2-2: PyPy일 경우, MLE2-3: Python3일 경우, TLE 그래서 코드포스, 그리고 과거에 백준을 풀 때 이 문제때문에 골치가 아팠던 적이 있다.이번 글에서는 DFS를 좀 더 빨리 돌려서 이 골치아픈 문제를 해결하는 방법을 3가지 알아보고자 한다. 1. C++ 배우기파이썬은 아무래도 쉬운 대신 느린 ..

대학교에 입학하고 SCSC에 들어가고, 살면서 처음으로 오프라인 대회를 나가보았다.내 실력으로 Div.3을 쳐야하는거 아닌가 생각이 들긴 했지만 정수론 알고리즘으로 고등학교 때 솔브닥을 다이아까지 올린 과거의 나 때문에 Div.2로 납치되었다. 고등학교때 솔브닥에서 만난 내적 친밀감이 가득한 사람들을 만날 생각에 기대가 부풀었지만 한편으로는 문제를 많이 못풀지 않을까 걱정이 많이 되었다. 이번 SCPC에서는 SCSC 부원으로서 나도 스태프를 신청해보았다. 별일은 아니고, 짐을 좀 옮기고 대회 접수를 맡는 대신에 핑크색 스태프 티셔츠를 얻을 수 있었다. (따로 사진은 없다) 원래 핑크색 티셔츠를 입고 대회 접수를 받았어야 하는데 급하게 오느라 티셔츠를 안받고 나와서 그냥 내 곰돌이 줄무늬 티셔츠에 선글라스..

2026년 4월 28일, 백준 서버가 종료되었다.2023년 고등학교에서 정보 심화 수업을 들으며 친구들과 함께 백준 첫 문제를 풀었던 기억이 생생하다. 그리고 3년동안 열심히 공부하고 발전하여 D3의 레이팅으로 나의 백준 여정은 막을 내렸다. 조금 더 공부하고 싶었는데..그동안 정보올림피아드 2차 대회도 나가보고, NYPC 본선도 나가보고, 학교 대회에서 출제도 해보고, 코포에서 블루도 찍어보았다(이건 꽤 최근의 일이다) 솔직히 대학교에서도 계속 PS만 하며 살 줄 알았는데. 앞으로의 계획은 크게 다음의 4가지 중 한가지일 것 같다. 1. 개편된 NYPC를 준비하며 인공지능을 공부하자.2. CP를 놓지 않고, 코드포스를 열심히 하여 레이팅을 올리고 ICPC를 준비하자.3. PS를 놓을 수 없다. QOJ로..

https://www.acmicpc.net/problem/10754랜마에 뜬 거의 아무도 안 푼 문제인데 풀고나니 재미있었다.풀이입력으로는 =(무게가 같다)와 무게가 큰 관계들을 토대로 위상정렬틱하게 순서들을 정리해보아야 할 것 같다.그 전에, = 쿼리를 먼저 처리해주어서 무게가 같은 동전들은 분리 집합 자료구조를 이용해 미리 같은 그룹으로 묶어놓도록 하자. 다음으로 한꺼번에 이제 우리는 이 DAG에서 '가장 긴 경로'의 길이가 N과 같을 때, 그 경로에 포함된 모든 노드들은 동전의 종류가 확정된다는 것을 알 수 있다. (그 외의 동전들은 전부 ?(미정)이다.)그러니까 결국에는 DAG에서 가장 긴 경로와, 그 경로에 포함된 노드들을 효율적으로 구하는 것이 이 문제의 핵심이 될 것이다. 여기서 좀 애를 먹..

https://www.acmicpc.net/problem/1014풀이맨 윗줄부터 아래로 내려가면서 dp할 것이다.가로 길이가 최대 10밖에 안되므로 비트마스킹을 해서, 현재 행에 배치할 수 있는 학생 조합 마스크들을 구해놓자.dp 정의는 dp[행번호][마스크] = (현재행번호까지 봤을 때 최대학생수)이다.i번째 행을 살펴볼 때 가능한 마스크에 대해서 i-1번째 마스크들과 직접 비교해주며 가능한 경우 최댓값을 갱신해주면 된다. import sysinput = sys.stdin.readlineC = int(input())for t in range(C): N, M = map(int, input().split()) graph = [] for i in range(N): s = inpu..

https://www.acmicpc.net/problem/13141풀이불을 N번 정점에서 붙인다고 하자.불길이 어떤 정점에 도달하는 시간은 최단거리 알고리즘을 이용하면 구할 수 있다.A, B를 잇는 길이 L인 간선이 다 타는데 걸리는 시간은 (dist[N][A] + dist[N][B] + L)/2 이다.N과 M이 충분히 작으므로 플로이드-워셜 알고리즘과 브루트포스 알고리즘을 이용하면 답을 구할 수 있다.시간복잡도는 O(N^3 + MN)이다. import sysinput = sys.stdin.readlineINF = 9_999_999N, M = map(int, input().split())dist = [[INF]*(N+1) for _ in range(N+1)]lines = []for i in range(M..

https://www.acmicpc.net/problem/32374 들어가기에 앞서...이제는 대학생이 되었다.고등학교때 디코에서만 보던 멋진 분들을 어느새 내 카톡 친구창에서 보게되었다.이제 진짜 열심히 할 때가 되었다.풀이문제를 잘 읽어보면 선물 상자에 모든 선물을 담을 수 없는 경우는 입력으로 주어지지 않는다고 하였다.그말인즉슨 선물 상자에 반드시 모든 선물을 다 담을 수 있다. 그러니까 선물들과 선물상자를 크기순으로 쭉 정렬해보면$a_i$ 선물은 반드시 $b_i$ 안에 들어갈 수 있다. 문제에서 주어진 예제를 예시로 들면 아래 그림과 같다. 선물의 크기가 상자의 크기 이하여서 상자에 들어갈 수 있는 경우를 파란색 화살표로 표현하였다. 만약 파란색 화살표가 아래 그림과 같이 오른쪽으로 기울어져있다면..

"파이썬으로 구현하는"시리즈 7강한 결합 요소(SCC) 어떤 방향 그래프에서, 모든 노드에서 다른 모든 노드로 가는 경로가 존재할 경우 이 그래프를 강결합 그래프(Strongly Connected Graph)라고 부른다. 모든 방향 그래프는 강결합 컴포넌트로 나눌 수 있다. 여기서 강결합 컴포넌트는, 모든 노드에서 다른 모든 노드로 가는 경로가 있는 최대 노드 집합을 의미한다. 이를 SCC라고 부른다. 참고: 알고리즘 트레이닝 2판, 안티 라크소넨 어떤 방향 그래프가 주어졌을 때, 이 그래프를 SCC들로 나누는 알고리즘은 2가지가 유명하다.바로 코사라주 알고리즘과, 타잔 알고리즘이다. 코사라주 알고리즘코사라주 알고리즘의 장점은, 이해가 쉬우며 알고리즘이 간단하다.다만 DFS를 2번 돌려야해서 코드의 길이..

https://www.acmicpc.net/problem/18790풀이1번째 시도(시간초과/메모리초과)일단, 주어진 리스트에서 각 수가 몇 번 등장하는지를 센다.가장 먼저 떠오른 건 DP. 대충 N의 범위가 500이니까 인자를 3개 잡는 재귀함수 형식으로 짜자.인자는 다음과 같다. dp[현재 처리하는 수][현재까지 쓴 수의 개수][현재 나머지] 마지막에 dp[N-1][N][0]을 불러서, 정답에 도달할 수 있는지 본다. dp 함수의 리턴값은 [현재 처리하는 수]가 몇 개 쓰였는지이다.이 값을 이용해서 역추적할 수 있다. 랜덤하게 생성해낸 데이터에 대해서 잘 돌아가였고, 자신만만하게 제출하였으나,,,, 2번째 시도(시간초과/메모리초과)dp 인자를 바꿔볼까?주어진 리스트에서 각 수의 등장 횟수를 카운트하는..

먼저 아래 문제를 보자. https://www.acmicpc.net/problem/22935 문제를 읽어보면 N이 주어질 때 N번째 외치는 수는 과연 무엇이 되어야 하는가를 구하는게 일단 어렵다. 그래서 표를 한 번 그려보았다.주기는 (15 - 1) * 2 = 28이다. 그런데 28로 나눈 나머지 안에서도 절반은 증가하고 절반은 감소하기 때문에14로 나눈 몫이 홀수인지 짝수인지에 따라 경우를 나눴다. 지금까지는. 이렇게 탄생한 지금까지의 나의 코드는 대충 아래와 같이 복잡하다. 매번 절편을 계산해줘야하고 보정해야해서 표를 맨날 그리기때문에 머리아프고 손아프며 시간이 걸린다. 그러나 아래와 같은 아주 간단한 방법이 있음을 깨달았다. 이렇게 28개씩 묶으면 사이클이 생긴다.그래서 미리 다음과 같은 리스..