주로 알고리즘 문제 풀 때, 안 쓰면 섭섭한 sys라이브러리 자주 쓰는 기능들을 몇 가지 적어둠. sys.setrecursionlimit() 파이썬에서 재귀를 사용해서 문제를 풀 때 무조건 필요한 함수. 파이썬은 기본적으로 재귀 제한이 매우 적은 편이기에 문제를 풀 때 자주 런타임 에러가 발생한다. 재귀가 막힌다 싶으면 무조건 작성해야 함. import sys sys.setrecursionlimit(10**6) sys.stdin.readline() 주로 입력을 빨리 받고싶을때 input() 대신 사용한다. 반복문으로 입력을 많이 받을때 sys.stdin.readline()을 사용해주면 시간을 단축시킬 수 있다. import sys arr = [] arr.append(sys.stdin.readline())..

알고리즘 문제를 풀고 정답을 출력할때 자주 사용하는 join함수. 알아두면 유용하다. arr1 = ['a', 'b', 'c', 'd'] print(', '.join(arr1)) 출력 결과: a, b, c, d join은 기본적으로 '구분자'.join(리스트) 형태를 가지고 있다. str1 = ''.join(arr1) print(str1) 출력결과: abcd join함수는 문자열을 반환해준다. a = ['is', 'you', 'down'] print('_'.join(a)) print(' '.join(a)) 출력결과: is_you_down is you down 이런식으로 사용 가능 arr2 = [1, 2, 3 ,4] print(', '.join(map(str,arr2))) 출력결과: 1, 2, 3, 4 jo..

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 난이도에 비해 매우 간결한 문제다. 대신 크루스칼 알고리즘과 유니온 파인드에 대해 알고 있어야 한다. 아이디어 1. 마을을 두 개로 분리하는 방법 크루스칼 알고리즘에 대해 잘 기억하고 있다면 쉽게 떠올릴 수 있다. 크루스칼 알고리즘으로 최소 스패닝 트리를 만들고 여기서 비용이 가장 큰 간선을 잘라주면 된다. 최소 스패닝 트리에서는 사이클이 존재하지 않는다. 그..

흐름 제어할때 자주 사용하는 구문들이다. break 반복문을 중단하고 싶을때 사용한다. 반복문 하나만 빠져나온다. 다중 반복문의 경우 전부다 나오는게 아닌 가까운 반복문 에서만 나옴. for i in range(1,6): if i == 3: break print(i) 출력 1 2 continue 해당 반복은 종료하고 다음 반복을 실행한다. 아래와 같이 i가 3인 경우 해당 루프를 종료하고 i = 4로 넘어간다. for i in range(1,6): if i == 3: continue print(i) 출력 1 2 4 5 pass 반복문, 함수, if문에서 비워두고 싶을때 사용한다. if문이나 함수등에 아무것도 작성이 안되어있으면 에러가 발생하므로 pass를 사용한다. 나중에 구현할때 그냥 넘어가는 용도로 ..

파이썬에서 대표적인 자료구조로 list, set, tuple, dictionary가 존재한다. ps에 초점을 맞춰 정리하는 느낌으로 작성했다. list (리스트) 변경 가능(mutable) 순서 존재(iterable) 리스트안에 객체들 중복 가능 arr = [] #리스트 선언 arr2 = list() #리스트 선언2 arr.append(1) # 1 값 추가 가장 오른쪽에 넣는거임 arr.insert(2, 2) # index 2에 2 값 추가 arr.remove(1) # 값이 1인거 삭제 del arr[1] # index 1에 있는 값 삭제 arr.pop() # 가장 왼쪽에 있는 값 삭제 및 return arr.extend(arr2) # 리스트와 리스트 합치기 arr += arr2 # 리스트와 리스트 합치..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 저번에 푼 부분합 문제의 소수 버전. 비슷한 문제여서 금방 해결 가능했다. 아이디어 1. 소수 찾기 시간 복잡도가 빠른 에라토스테네스의 체 방법으로 소수를 찾았다. 2. 소수의 연속합 부분합 문제와 유사하게 투 포인터를 사용해서 경우의 수를 찾았다. 전체 코드 import math n = int(input()) if n == 1: print(0) exit(0) arr = [True] * (n + 1) arr[0] = False arr[1] = False for i in range(2, int(math.sqrt(n)+..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간제한 3초로 매우 길지만 너무 복잡하지 않은 문제. 아마 테스트 케이스가 여러 개라서 시간제한을 널널하게 둔 거 같다. 아이디어 1. 그래프 일단 보자마자 그래프를 써야 한다고 생각했다. 문제 조건에서 팀이 되려면 서로가 꼬리를 물듯 사이클이 생겨야 한다. 그럼 이 문제는 그래프에서 '사이클을 어떻게 찾고 판별하냐'에 대해서 생각하면 된다. 2. dfs 방문 유무를 통해 사이클이 생겼는지 안 생겼는..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 아이디어 1. 부분합 사용 부분합에 대해 간단히 얘기해보면 0 ~ N까지의 합을 미리 구해두고 합의 차((0 ~ b까지 합) - (0 ~ a까지 합))를 통해 a부터 b까지 수의 합을 빠르게 구하는 방법이다. 그래서 for문을 사용해서 길이가 1일 때, 2일 때... N일 때 부분합의 값을 구해보며 S값이 넘는 순간 프로그램을 종료하도록 코드를 짰다. 당연하게도 시간 초과가 떴다. ..