STUDY 526

[백준] 1865 웜홀 python

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..

STUDY/Algorithm 2022.03.11

[백준] 11657 타임머신 python

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)..

STUDY/Algorithm 2022.03.11

[백준] 16235 나무 재테크 python(pypy)

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..

STUDY/Algorithm 2022.03.10

[백준] 10597 순열장난 python, c/c++

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..

STUDY/Algorithm 2022.03.09

[백준] 1343 폴리오미노 C

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..

STUDY/Algorithm 2022.03.08

[백준] 17471 게리맨더링 python

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(..

STUDY/Algorithm 2022.03.07

[백준] 15655 N과 M(6) python

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_..

STUDY/Algorithm 2022.02.28

[백준] 11000 강의실 배정 python

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..

STUDY/Algorithm 2022.02.27

[백준] 14502 연구소 python

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 그래프 탐색 알고리즘을 모두 사용해야하는 문제이다 3개의 벽을 설치할 땐 백트래킹을 설치한 이후 바이러스가 전파되는 것은 그래프 탐색(BFS를 사용했다)을 하면된다. 바이러스 전파가 끝나면 이차원 배열에서 안전한 구역을 찾으면 된다. # import sys; input = sys.stdin.readline from collections import deque def bfs(): global N, M..

STUDY/Algorithm 2022.02.26

[백준] 15664 N과 M(10) python

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이 너무 부족해서 쉬운문제부터 다시 시작... def backtrack(ind, limit, prev): global nums, answer, visit if ind == limit: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in answer: print(*tmp) answer.add(tmp) return ..

STUDY/Algorithm 2022.02.24