문제 문제 링크 : 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 # ..

이진 탐색 (Binary Search) 데이터가 정렬되어 있어야만 사용할 수 있으며, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하며 원하는 데이터를 찾는 과정 Steps : 정렬된 10개의 데이터 중 값이 4인 원소 이진 탐색 시간 복잡도 - 시간 복잡도 : O(logN) - 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점 - 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘아가면 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다 - 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자 Code with Python 1. 재귀 함수로 구현한 ..

정렬(Sorting) 이란? 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬 (Selection Sort) 가장 작은 데이터를 선택하여 맨 앞 데이터와 바꾸고, 그 다음 작은 데이터를 선택하여 앞에서 두 번째 데이터와 바꾸는 것을 반복하여 수행하는 정렬 > Steps > Code with Python array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[..

DFS, BFS를 설명하기 전에, 그래프 표현의 2가지 방식은 인접 행렬과 인접 리스트에 대해 알아봅니다! 인접 행렬 (Adjacency Matrix) - 2차원 배열에 각 노드가 연결된 형태를 기록 - 연결되지 않은 노드의 비용은 무한으로 작성한다 INF = int(1e9) graph = [ [0, 1, 1, 1], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0] ] 인접 리스트 (Adjacency List) - 모든 노드에 대해 연결된 노드에 대한 정보를 연결하여 저장 adj = [[] for _ in range(4)] adj[1].append(2) adj[1].append(3) adj[1].append(4) adj[3].append(3) adj[4].append(3) - 가..