전체 글

1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다. 2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식 공간복잡도: 간선 개수만큼인 O(E) 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다. 2. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합이다. 서..

1. 그래프 자료구조 union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다 1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다. 2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식 공간복잡도: 간선 개수만큼인 O(E) 시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다. 2. 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합이다. 서..

금광 이동방향은 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 이다. 이를 현재 내 위치인 dp[i][j]에서 보면 왼쪽 위, 왼쪽, 왼쪽아래에서 내 위치로 오는 3 가지 경우가 있다는 의미이다 하지만 이렇게 i == 0 인 경우에는 왼쪽위에서 올 수 없으므로 left_top = 0 이다. 그렇지 않은 경우에는 left_top = dp[i-1][j-1] 이다. 다음의 경우는 3가지 방향 모두 유효하니까 경우를 더 나눌 필요 없이, left = dp[i][j-1] i == (n-1) 인 경우에도 왼쪽아래에서 오는 경우는 불가능 하므로 이 경우 left_bottom = 0이라고 처리해 준다. 그렇지 않은 경우는 left_bottom = dp[i+1][j-1] 이다. 그리고 이 값들 중에서 max 값과 dp[i][..

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 이 문제는 이진탐색으로 해결할 수 있다 왜냐면 fro??? 이렇게 접두사가 있으면 단어들 리스트에서 fro 가 처음 나온 인덱스랑, 마지막으로 나온 인덱스를 각각 구해서 차이를 구하면 그것이 바로 fro???에 해당하는 단어들 개수가 된다 !! 단어 탐색의 시작은 a 부터 z까지이다. 숫자 뿐만 아니라 이렇게 단어 탐색도 이진탐색을 사용할 수 있다. 여기서 신선하다고 생각 ㅋㅋ 파이썬에는 bisect이라는 이진탐색을 쉽게 수행할 수 있도록 돕는 라이브러리가 있다 그런데 문제제는 접두사말고도 접미사 부분이 ? 인 경우가 있다 ex) tra?? ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제를 풀 때 핵심적인 아이디어는, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 다이나믹 프로그래밍 알고리즘을 수행해야 한다는 것이다 ! 문제에서 주어진 예시 N = 7 인 경우에는 6일과 7일자의 상담을 수행하면 7을 넘기게 된다. 이와 같은 경우를 고려하기 위해서 뒤에서부터 DP를 수행하여 저장한다. 경우를 나누는 것은 두가지로, i번째 날의 상담을 수행했을 때 n을 넘는다면 이 경우는 불가능하니까 value를 0이라고 생각하여 dp 그래프에 0 값으로 처리를 한다. dp[i] = dp[i+1] # 단, 여기서 dp list의 맨 ..

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 결국 BFS를 이동해서 로봇이 (n,n)에 도달할때까지의 최단거리를 구한다. 1. 벽을 하나 둘러싼 모양으로 확장된 보드를 만들어서 (1,1) ~ (n,n) 이라고 생각하기 쉽게 해준다. 2. 갈수있는 위치를 구하는 함수는 갈수 있는 위치의 리스트를 리턴한다. 3. 갈수 있는 위치는 queue에 넣고, 방문하면 visited에 넣는다. 일반적인 bfs로 , 큐가 빌 때까지 반복한다. 4. 갈..

문제에서 O(logN)으로 알고리즘을 설계하기를 요구했다 -> 선형탐색은 O(N) 이므로 부적합 데이터 셋이 오름차순으로 정렬되어 나오기 때문에 이진탐색을 선택함 mid 를 인덱스로 보고 array[mid] 값과 같으면 고정점이다 -> 이 값을 리턴 그렇지 않은 경우, array[mid] 실제 값이 더 크다면 반으로 뚝 자른 데이터들 중에서 오른쪽의 큰 값들을 탐색하면 된다. 더 작으면 왼쪽의 작은 값들을 탐색한다. 탐색 실패하면 None을 반환한다. n = int(input()) array = list(map(int, input())) def binary(array, start, end): if start > end: return None mid = (start + end) // 2 if array[m..

카드 정렬하기 !! 첫 시도: 가능한 순열 조합을 모두 계산하고 최솟값을 찾으려고 했으나 ㅋㅋㅋ 이 문제는 숨겨진 규칙이 있었으니.. 바로 가장 작은 카드 수 부터 더해가야 한다는 것이다. 그래서 heap 자료 구조를 이용하여 카드 들 중에서 카드 수가 작은 것을 빼내어 더하고, 이 더한값을 다시 heap에 넣어줘서 다시 더해지도록 한다 heapq 라이브러리 오랜만에 쓰는데 이 참에 파이썬 힙 자료구조 라이브러러 쓰는 방법도 확실하게 숙지해야겠따. import heapq n = int(input()) heap = [] for i in range(n): data = int(input()) heapq.heappush(heap,data) result = 0 while len(heap) != 1: one = h..