'파이썬' 태그의 글 목록

6. Union Find(합집합 찾기) : MST - 1

2021.05.30

Union Find (합집합 찾기) MST - 1 정말 오랜만에 포스팅이다. MST 알고리즘 문제를 풀던 도중 생각나서 포스팅 하게 됐다. 매주 주말마다 알고리즘 개념 정리를 하려고 하는데 계속 실패하는 것 같다... ㅎㅎ;; 오늘 다뤄볼 주제는 MST, 최소 신장 트리 문제를 해결하기 위한 기본 베이스인 Union Find이다. 최소 신장 트리 문제를 해결하기 위한 방법에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 존재한다. Union FInd는 크루스칼 알고리즘의 핵심이라고 말할 수 있다. 그럼 Union Find가 무엇인지 알아보자. Union Find는 말 그대로 Union, 집합을 찾는 알고리즘이다. 그래프 정보가 주어졌을 때 이들 간의 관계를 알아볼 수 있다. 바로 예시..

✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 1260. DFS와 BFS

2021.04.18

본 게시글은 PC버전에 최적화 되어있습니다. www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를..

✍️ 코테 준비/Shortest Path

[최단 경로] [Python] 10217. KCM Travel - GOLD Ⅰ

2021.04.17

본 게시글은 PC버전에 최적화 되어있습니다. 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 입력 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착..

✍️ 코테 준비/Shortest Path

[최단 경로] [Python / C++] 1956. 운동 - GOLD Ⅳ

2021.04.16

본 게시글은 PC버전에 최적화 되어있습니다. 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 입력 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다. 출력 첫째 줄에 최소..

✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 1707. 이분 그래프

2021.04.14

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데..

✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.

2021.04.13

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테..

⛹️ 라이프/코딩 테스트

[스코페 2021] Startup Coding Festival 2021 - 1차 예선 결과

2021.03.23

동아리 톡방에 관련 공지가 올라와서 백준도 어느정도 풀어봤겠다 싶어서 실력을 테스트할 겸, 카카오 코테 준비하는 겸 해서 스코페에 참가하게 됐다! 스코페 2021, SCOFE 2021 스타트업 기업들이 주최하는 코딩테스트였다! 왓챠, 쏘카, 오늘의 집, 마켓컬리, 브랜디, 번개장터 다들 한번씩은 들어본 이름이라고 생각한다! 문제마다 특정 기업이 들어가있었던거보면 기업별로 1문제씩 출제한 것으로 보인다. 언어는 내가 제일 좋아하는 파이썬으로 진행했다. 총 문제 6문제. 배점은 20 / 20 / 20 / 20 / 30 / 30 으로 총점 140점이였다. 내가 획득한 점수는 대략 110점 정도 되는 것 같다. 문제별로 테스트 케이스를 모두 통과하면 "맞았습니다" 가 출력된다. 문제당 확인할 수 있는 테스트 케..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 1904번. 01타일

2021.01.12

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 입력 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 출력 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 해결 방법 언뜻보면 어려워 보일 수 있다. 하지만 타일의 경우의 수에는 규칙이 있다. N 1 2 3 4 5 6 7 2진 수열의 경우의 수 1 2 3 5 8 13 21 피보나치와 같은 점화식을 가진다. f(n) = f(n-..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 9184번. 신나는 함수 실행

2021.01.12

www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 입력 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. 출력 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다. 해결 방법 dp를 활용한다. 해결 과정 [0][0][0] ~ [20][20][20]의 3차원 배열을 생성하고 각 조건별로 나눈다. 특정 범위 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [Python] 1003번. 피보나치 함수

2021.01.12

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 해결 방법 피보나치 재귀 함수에 관한 문제다. 0과 1이 호출되는 횟수 자체도 규칙이 있음을 알 수 있다. 0 1 2 3 4 5 6 7 0 1 0 1 1 2 3 5 8 1 0 1 1 2 3 5 8 13 위와 같이 호출되는 횟수도 (n-2) + (n-1..

티스토리툴바