문제 문제 링크 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net CODE from collections import deque import sys input = sys.stdin.readline v = int(input()) e = int(input()) edges = [[] for _ in range(v + 1)] for _ in range(e): a, b = map(int, input().split()) edges[a].append(b) ed..

문제 문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net CODE from collections import deque def solve(n, k): time = [0] * (200001) q = deque([n]) time[n] = 0 while q: now = q.popleft() if now == k: print(time[k]) return if abs(k - now) > abs(k - 2 * now)..

문제 문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net CODE from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) miro = [] for i in range(n): miro.append(list(input().rstrip())) visited = [[0] * m for _ in range(n)] dir = [[1, 0], [-1, 0..

문제 문제 링크 : https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net CODE from collections import deque import sys input = sys.stdin.readline dir = [[0, -1], [0, 1], [1, 0], [-1, 0]] def solve(x, y, ground, check): q = deque([[x, y]]) check[y][x] = True cnt = 0 while..

문제 문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net CODE from collections import deque import sys input = sys.stdin.readline def dfs(edges, v, visited): visited[v] = True print(v, end=' ') for e in edges[v]: if not visited[e]: dfs(edges, e, vi..

프로젝트와 깃허브를 연동할 겁니다 Github 계정이 없다면 가입이 먼저 필요합니다 계정이 있다고 생각하고 진행합니다 🏃‍♀️🏃‍♂️ 1. Action 검색창 열어 share project on github을 검색한다 Action 검색창을 여는 단축키는 윈도우에서 [Ctrl + Shift + A] , 맥에서 [Command + Shift + A] share project on github를 검색해서 클릭! 2. Github 로그인하고 깃허브 프로젝트 생성 Add account에서 Log In via Github로 들어가면 깃허브 로그인 화면이 나옵니다 본인 깃허브 계정으로 로그인을 합니다 Repository name을 설정하고 Share 클릭 대부분은 프로젝트 이름과 깃허브 저장소에 같은 이름을 사용한다..

README 란? Github에 프로젝트를 올릴 때, 프로젝트에 대한 설명뿐 아니라 사용 방법, LICENSE 등의 내용을 기술하는 파일이다. README를 작성해야 하는 이유 어떤 프로그램을 사용하거나 오픈소스를 참고하기 위해 G ithub Repository에 들어간다면, 가장 먼저 확인하는 것이 README 파일이다. 다른 사용자들이 내 오픈소스 프로젝트에 대한 정보를 얻기 위해, 해당 프로젝트에 대해 함께 협업하는 동료에게 정보를 주기 위해, 나중에 다시 내가 프로젝트를 다시 열었을 때 떠올리기 용이하기 위해 README를 잘 작성해 둘 필요가 있다. 일반적인 README 구조 1. 프로젝트 Description - 프로젝트 명 - 어떤 프로젝트인지 소개 2. 프로젝트 정보 - 설치(Getting..

서로소 집합 (Disjoint Sets) : 공통 원소가 없는 두 집합 > 서로소 집합 자료구조 (union-find 자료구조) - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 연산 * union 연산 : 2개의 집합을 하나의 집합으로 합치는 연산 * find 연산 : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 트리 자료구조를 이용하여 집합을 표현한다 > 서로소 집합 계산 알고리즘 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 (1) A와 B의 루트 노드 A', B'를 각각 찾는다 (2) A'를 B'의 부모 노드로 설정한다 (B'가 A'를 가리키도록 한다) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반..

다익스트라 알고리즘 (Dijkstra SAlgorithm) - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작한다 - 그리디 알고리즘 - 힙(Heap) 자료구조를 사용하여 구현할 것이다 - 시간 복잡도 : O(ElogV) > 원리 1. 출발 노드 설정 2. 최단 거리 테이블을 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 5. 3, 4번을 반복 > Code with Python import heapq import sys input = sys.stdin.readline INF = i..

다이나믹 프로그래밍 (Dynamic Programming) 큰 문제를 작은 문제로 나누어 해결하는 방법 다음의 조건을 만족할 때 사용할 수 있다 - 큰 문제를 작은 문제로 나눌 수 있다 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 메모이제이션(Memoizations) - 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 - 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 - 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다 Code with Python > 피보나치 함수 : 탑다운 다이나믹 프로그래밍 탑다운(Top-Down) : 큰 문제를 해결하기 위해 작은 문제를 호출, 재귀함수 이용 d = [0] * 100 # ..