목록전체 글 (222)
꺼내먹는지식 준
문제를 봐도 도저히 효율적으로 풀 방법이 떠오르지 않아 결국 비효율적으로 해결했다. 문제는 답안을 살펴봐도 알고리즘이 동작할 것이라는 건 확인할 수 있었지만, 왜 어떻게 동작할 수 있는지에 대해 파악하는 것이 어려웠다. 관련하여 나와 동일한 고민을 하고 내용을 정리해놓은 글을 아래 링크로 걸고, 글을 읽으며 든 생각을 정리한다. https://kk-programming.tistory.com/11 [이코테-그리디] 기출 - 04. 만들 수 없는 금액 [문제] 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N=5 이고 kk-programming.tistory.com 동전 [1, ..
그간 몇가지 기본 알고리즘을 살펴보았다. 마지막으로 다양한 그래프 알고리즘을 살펴보고자 한다. 먼저 다룬 DFS/BFS, 최단 경로 알고리즘도 그래프의 일종이다. 출제 비중은 비교적 낮은 편이다. 그래프와 트리의 차이 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 서로소 집합(union-find 자료구조) 수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1,2} 와 집합 {3,4} 는 서로소 관계이지만, {1,2}와 {2,3}은 서로소 관계가 아니다. 서로소 집합 자료구조는 몇몇 ..
다익스트라 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 플로이드 워셜 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 정의에서 살펴볼 수 있듯이 한 지점이 아닌 '모든 지점' 에서 다른 모든 지점까지의 최단 경로를 모두 구하는 것이 플로이드 워셜 알고리즘이다. 다익스트라가 1차원 배열에 최단 거리를 저장했다면, 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장해야 한다. (다익스트라는 특정 점부터의 거리만 저장하면 되었지만 플로이드 워셜은 각 노드에서 각 노드로 가는 거리를 인접 행렬에 작성해야 한다.) 각 단계에서 해당 노드를 거쳐가는 경우를 고려 1번 노드에 대해서 확인할 경우: 1번 노드를 중간에 거쳐 지나가는 모든 경우 고려 A $..
개요 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 다양한 유형 및 상황에 적절한 효율적인 알고리즘이 이미 정립되어 있다. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우 최단 경로 문제는 보통 그래프로 표현 각 지점: 노드 지점간 연결된 도로: 간선 보통 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하는 유형이 빈번하게 등장 보통 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 등장하는데, 이 중 벨만 포드는 자주 등장하지 않아 해당 글에서 다루지 않는다. 다익스트라 여러개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 다만 최단 경로 알고리..
다이나믹 프로그래밍 컴퓨터로 해결하기 어려운 문제는 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제들이 해당된다. 특정 문제들을 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적 방법이 바로 다이다믹 프로그래밍이다. (동적 할당이란 '프로그램이 실행되는 도중'에 필요한 메모리를 할당하는 기법이다. 하지만 다이나믹 프로그래밍의 다이나믹은 이 정의에 해당되지 않는다.) 다이나믹 프로그램의 대표적 예시 피보나치 수열 점화식은 수열의 항이 이어지는 형태를 간결하게 표현한다. 피보나치 수열의 점화식은 다음과 같다. $$a_{n+2} = f(a_{a+1}, a_n) = a_{n+1} + a_n$$ $$a_1 = 1, \, a_2 =..
이진 탐색을 이해하기 위해서는 순차 탐색을 먼저 살펴볼 필요가 있다. N 개의 데이터가 있을 때 데이터를 차례대로 하나씩 확인하는 그 자체가 바로 순차 탐색이다. 순차탐색 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. import sys input = sys.stdin.readline array = [1,2,3,4,5,1,2,3,1,2,1,2,3,45,56,1,32,4,14,21,41,5,14,124,12341,1,1,213,1,2,3,4,1,2,3,1,1,1,2,3,1,2,3] N = int(input()) cnt = 0 for i in array: if i == N: cnt += 1 print(cnt) 주어진 array ..
정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 이진탐색을 위해서는 정렬 알고리즘으로 데이터를 정렬하는 것이 선 과정이다. 다음의 알고리즘을 알아보자. 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 1) 선택정렬 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. 매번 가장 작은 것을 '선택'하므로 선택 정렬 알고리즘이라 한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def swap(x,y): tmp = x x = y y = tmp return x, y for i in range(len(array)): minimum = 1e9 for j ..
탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 그래프, 트리 등의 자료구조 안에서 탐색 하는 문제를 주로 다룬다. 대표적으로 DFS, BFS 를 꼽고, 이 두 알고리즘은 원리를 완벽하게 이해해야 문제 해결이 가능하다. 두 알고리즘의 원리가 되는 Stack, Queue 를 간단하게 살펴보자. STACK 스택은 박스쌓기를 기억하면 잊지 않을 수 있다 . 다음과 같이 박스를 쌓으면 맨 하단의 박스가 당연히 가장 먼저 내려놓은 박스이다. 그러나 우리가 다시 박스를 들어올릴 때는 최 상단의 박스부터 들어올리게 된다. 즉, 처음에 넣은 것이 (First in) 가장 마지막에 나오게 된다(Last out). QUEUE 큐는 버스를 생각하면 잊지 않을 수 있다. 버스는 한쪽 입구로 타서 안쪽 출구로 내린..
구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다. 즉, 1) 문제를 보고 2) 풀이를 떠올리고, 3) 소스코드로 옮겨야 한다. 즉, 마치 게임에서 손 빠른 사람을 '피지컬'이 좋다고 하듯이, 구현 유형 문제는 소스 코드로 구현을 하는 코딩 '피지컬'을 요구한다고 볼 수 도 있다. 소스코드로 옮기는 과정이 원할하기 위해서는 기본적으로 다음의 능력이 필요하다. 1) 충분한 라이브러리 사용 경험 2) 충분한 문법 숙지 완전 탐색과 시뮬레이션은 구현에 포함한다고 가정하였다. 때로 기업 공채에서는 웹 서버나 데이터 분석 기초 지식이 필요하기도 하다. 몇개의 구현 알고리즘을 풀어보자. 1) 상하좌우 N X N 정사각형의 한 블럭(1 X 1)위에 여행가가 서 있다. 가장 왼쪽 (1,1) 가장 오른쪽..
Scipy Sparse Matrix, Dense Matrix Sparse Matrix 의 경우 메모리를 적게 소비하기 위하여 생략하여 표기를 하는 경우가 많다. 여러 기법이 있지만, 그 중 3가지를 정리해본다. 참고글 https://stackoverflow.com/questions/32743584/python-lil-matrix-vs-csr-matrix-in-extremely-large-sparse-matrices Python: lil_matrix vs csr_matrix in extremely large sparse matrices I want to build an extremely large sparse matrix incrementally. The problem is that lil_matrix i..