Python/Algorithm

그래프와 그래프 탐색

그래프 (Graph) 노드와 그 노드를 연결하는 간선의 집합으로, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트 2가지 방법이 있다. 인접 행렬 이차원 배열로 그래프의 연결 관계를 표현하는 방식으로, 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비가 심하다. 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 알 수 있으므로 효율성이 떨어진다. 인접 리스트 리스트로 그래프의 연결 관계를 표현하는 방식으로, 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다. 인접 행렬에 비해 특정한 두 노드의 연결 정보를 얻는 속도가 느리다. n, m = map(int,input().split()) # 인접 행렬..

해시 테이블

해시 테이블 Key-Value로 데이터를 저장하는 자료구조 중 하나로, 해싱을 통해 정보를 빠르게 저장하고 검색할 수 있다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다. 먼저 각각의 키에 해시 함수를 적용해 해시 코드를 계산하고, 계산한 해시 코드를 이용해 배열의 고유한 인덱스를 계산한다. 계산한 인덱스를 통해 값을 저장하거나 검색하며, 실제 값이 저장되는 장소를 버킷이라고 한다. 해시 함수 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수로, 충돌이 발생할 확률을 최대한 줄이는 것이 중요하다. 충돌은 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 것을 말하며, 충돌이 자주 발..

스택과 큐

스택 (Stack) 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 구조로, 가장 최근에 스택에 추가한 항목이 가장 먼저 나오는 후입선출 방식 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어두고 재귀함수를 빠져나와 백트랙할 때는 스택에 넣어 두었던 임시 데이터를 빼내야 하는데, 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다. 구현 (JAVA) import java.util.ArrayList; import java.util.EmptyStackException; public class Stack extends ArrayList { public Stack() { super(); } public Stack(int capacity) { super(capacity); } public E pus..

배열과 연결리스트

배열 자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉘는데, 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. C 언어를 기준으로 배열은 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말하며, 크기가 고정되어 있어서 한 번 생성한 배열은 크기를 변경하는 것이 불가능하다. 배열의 가장 큰 장점은 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 원하는 요소의 인덱스 값을 알고 있으면 항상 O(1)에 해당 원소에 접근 가능하다는 점 예를 들어 int 배열에서 4번째 값에 접근하고 싶다면 (배열의 시작 주소 + (4 - 1) * 4)로 주소를 계산해 한번에 접근 가능하다. 단, 삭제 또는 삽입의 경우 원소들의 인덱스를 sh..