시나위

https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 이진탐색 문제이고 python 함수 bisect를 사용해서 풀었다. # import sys; input = sys.stdin.readline from bisect import bisect_left def index(a, x): i = bisect_left(a, x) if i != len(a) and a[i] == x: return i return -1 def main(): ..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 그리디 문제이다. 문자열이 주어졌을때 뒤집어서 같은 숫자를 만들어야한다. 뒤집는 횟수를 구하기 위해 값이 바뀔때마다 하나씩 체크하고 2로 나누어주면된다. (2로 나눈 이유는 예제 입출력에서 규칙을 찾아내었다.) #include int main() { char s[1000000]; int cnt = 1, i; scanf("%s", s); for (i = 1; s[i] != '\0'; i++) { i..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이전 문제와 같이 벨만포드 알고리즘을 사용한 문제이다. edge를 그대로 넣고 사용할수도 있고 연결 그래프를 만들어서 사용할수도 있다. 뭐가 좋을진 문제마다 다를 것 같지만 이 문제에서는 edge를 사용하는게 조금 더 빠르다. 그래프를 사용하면 필요없는 곳까지 반복해야해서 시간이 더 걸리는 듯하다. 1) edge # import sys; input = sys.stdin.readline..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만 포드 알고리즘을 사용하는 문제이다. 알고리즘에 대한 자세한 내용은 아래 링크로 달아놓겠다. # import sys; input = sys.stdin.readline INF = 20_000_000_000 def bf(start): global dist, N, M, edges dist[start] = 0 for i in range(N)..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 시뮬레이션 문제여서 문제에 나와있는 순서대로 풀었다. 더보기 import sys; input = sys.stdin.readline from heapq import heappop, heappush def main(): N, M, K = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(N)] t..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 백트래킹 문제이다. 한글자, 두글자씩 읽어서 확인하고 마지막까지 순회했을 때 (포커의 스트레이트 같이) 모든 값이 이어지는지 확인한다. # import sys; input = sys.stdin.readline def backtrack(ind, limit): global s, stack if ind == limit: max_v = max(stack) for i in range(1..

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문자열에서 문자 하나씩 확인하면서 교체할수 있는지 확인했고, 사전순이므로 AAAA 한 뒤 BB를 교체했다. #include int check(char* s, int length, int start, int size) { if (start + size > length) return 0; for (int i = 0; i < size; i++) { if (s[start + i] != 'X') return 0; } return 1; } int main() { // 0 initialize int i, j, l..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 백트래킹과 그래프 탐색이 합쳐져 있어서 뭔가 삼성 기출 같은 문제이다. 이 문제는 선거구를 두 지역으로 나누고(조합, backtracking) 선거구끼리 연결되어있는지 확인해서(graph traversal, bfs, dfs) 연결되어있는 경우 최솟값이 되는지 확인하면 된다. # import sys; input = sys.stdin.readline from collections import deque def check(..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 연습을 위한 쉬운 문제 # import sys;input = sys.stdin.readline def backtrack(ind=0, cnt=0): global n, m, nums, ans_set, visit if cnt == m: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in ans_set: ans_..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 알고리즘으로 풀었다. 강의 시간을 정렬한 다음 모든 강의 시간을 순회하면서 힙 answer에 데이터를 추가하거나 수정하는 방식이다. 추가하는 시간은 해당 강의실의 강의가 끝나는 시간을 나타낸다. python의 heap은 최소힙이므로 0번째(top)가 최솟값이 되고 항상 모든 강의실 중 가장 빨리 끝나는 시간을 나타내므로, 강의실을 계속 사용해도 되는지 아니면 하나 더 사용해야하는지 판단할수 있다. import sys; input = sy..