공부&일상 기록

그래프에서 간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리를 구하는 일은 생각보다 복잡합니다. 지금부터는 이러한 경우의 최단경로를 구하는 알고리즘에 대해서 소개하겠습니다.1. 다익스트라 (Dijkstra)특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘입니다. 예를 들어 5개의 정점(1 ~ 5번)이 있고 1번 정점에서 출발한다고 가정하면, 1번에서 2 ~ 5번으로 가는 최단거리를 구해줍니다.양의 가중치만 있는 그래프에서만 다익스트라를 이용해 최단거리를 구할 수 있으며, 음의 가중치가 있으면 다시 골라졌던 정점에 도달하는 dist값이 더 작아질 수 있기 때문에 최단거리임을 보장할 수 없게 됩니다. 다익스트라의 아이디어다른 지점까지의 거리는 모르지만, A라는 지점까지 가는 ..

1. 그래프 (Graph)그래프의 정의여러 개의 노드(node)와 이들을 연결하는 간선(edge)으로 이루어진 자료구조로, 관계를 추상적으로 표현한 구조입니다.예를 들어, 정점은 SNS라면 각각의 유저를, 지하철 노선도라면 역을 의미하고, 관계는 SNS라면 팔로우 관계를, 지하철 노선도라면 역과 역을 잇는 길을 의미합니다. 그래프의 분류그래프는 방향성과 가중치 유무 등에 따라 몇 가지 유형으로 나뉩니다.방향성에 따른 분류무방향(Undirected) 그래프 : 간선에 방향이 없는 그래프입니다. 즉, 그래프 내 모든 길을 양방향으로 이동할 수 있음을 의미합니다.방향(Directed) 그래프 : 간선에 방향이 있는 그래프입니다. 즉, 그래프 내 한쪽 방향으로만 갈 수 있는 길이 하나라도 있음을 의미합니다. 차..

1. 동적계획법동적계획법의 정의동적계획법이란 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법을 뜻합니다.점화식(작은 문제와 큰 문제간의 관계식)을 기반으로 하는 방법이며, for문을 이용하여 해결할 수도 있고, 재귀함수를 이용하는 것도 가능합니다.2. Memoization (Top-Down Approach)Memoization의 정의재귀함수를 이용하여 문제를 해결하는 과정에서, 이미 한번 계산한 결과를 기록하여, 동일한 작업의 계산을 반복하지 않는 것입니다. 즉, 각 n에 해당하는 값을 정확히 한 번씩만 계산하게 됩니다. 이런식으로 값을 기록하고, 그 기록한 값을 참조하는 것을 메모이제이션이라고 부릅..

1. 해싱해싱의 정의해시함수는 임의의 데이터를 입력받아, 해당 데이터를 고정된 길이의 특정 값으로 반환하는 함수입니다. 즉, 어떤 값을 넣더라도 특정 범위에 해당하는 값을 반환합니다. 만약, 해시 함수의 반환값을 0부터 시작하는 양의 정수가 되도록 조절한다면, 특정 값을 배열(해시 테이블)에 넣기 위해 해시 함수에 그 값을 넣고, 값에 해당하는 인덱스에 그 값을 넣어주는 방법을 사용할 수 있습니다.function append(key, value) set index = hash_function(key) hash[index] = value function find(key) set index = hash_function(key) if hash[index] != null return hash[in..

1. 트리 (Tree)트리 개념노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프Unrooted tree : 부모 자식 관계가 정의되지 않은 트리 (루트 노드 존재하지 않음) Rooted tree : 부모 자식 관계가 정의되어 있는 트리로, 루트 노드는 단 하나만 존재합니다.Unrooted tree에서 루트 노드는 사람이 정하기 나름입니다. 트리 용어노드(정점) : 각 지점을 의미합니다.간선(에지) : 두 노드를 연결하는 선을 의미합니다.루트 노드: 트리에서 맨 꼭기를 의미합니다.부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부릅니다. 한 노드의 자식노드 개수는 제한이 없지만, 부모 노드는 최대 1개만 존재합..

1. 스택 (Stack)개념후입선출 구조(LIFO; Last In First Out)로, 먼저 들어간 데이터가 나중에 나오는 자료구조입니다.데이터가 들어가는 곳과 나가는 곳이 같습니다.주요 형태와 연산Stack st = new Stack();T는 스택 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)push(E) : E를 스택 맨 위에 추가합니다.size() : 현재 스택에 들어있는 데이터의 개수를 반환합니다.isEmpty() = empty() : 현재 스택 비어있다면 true, 비어있지 않다면 false를 반환합니다.peek() : 스택의 맨 위에 있는 데이터를 반환합니다. 단, 스택에서 그 데이터를 제거하지는 않습니다.pop() : 스택의 맨..

1. 이진탐색기본 아이디어찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복합니다. 이때, 찾는 범위 속 원소의 갯수가 1개로 줄어들면 탐색을 종료합니다.이진탐색을 위해서 배열에 들어있는 값은 반드시 정렬되어 있어야 합니다.  상세 과정left ≤ right를 만족할때까지(원소 수가 1개로 줄어들 때까지), 찾는 숫자인 target과 가운데 위치(mid)에 해당하는 값인 arr[mid]를 비교합니다.target == arr[mid]인 경우 : 해당 위치인 mid를 반환합니다.target target > arr[mid]인 경우 : left를 mid+1로 움직입니다.반복이 끝났는데도 아직 target의 위치가 반환되지 않았다면, 찾는 숫자인 ..

1. 거품 정렬 (Bubble Sort)기본 아이디어첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환해줍니다. 이런 절차를 정렬이 될 때 까지 반복합니다. 시간 복잡도한 바퀴를 돌 때 마다 데이터가 한 개씩 제자리로 가게 되므로, 최악의 경우 N-1바퀴 배열을 순회합니다.따라서, O(N^2)이라는 시간복잡도를 갖게 됩니다. 코드// 일반적인 bubble sortfunction bubble_sort(arr[]) set len = arr.size for i = 0 ... i arr[j + 1] set tmp = arr[j] arr[j] = arr[j + 1] ..

1. 정적 배열연산의 종류시간복잡도최악의 경우 설명삽입O(N)맨 앞에 값을 넣는 경우, 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들이 뒤로 한칸씩 이동함삭제O(N)맨 앞의 값을 삭제하는 경우, 나머지 N-1개의 값들이 모두 이동함탐색어떤 원소를 찾는 경우 : O(N)처음부터 모든 값을 훑어 보며, 맨 끝에 값이 존재하는 경우K번째 원소를 찾는 경우 : O(1)배열은 index 기반으로 이루어져 있으므로, k-1번째 인덱스를 참조 2. 동적 배열 정적배열동적배열주요 형태int[] a = new int[100];ArrayList a = new ArrayList();T는 동적 배열 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)설명배열의 선언..

그래프 문제 특징 => 정점개수, 간선개수 주어짐 정점개수 대비 간선개수가 어느정도인지 가늠 가능 → 입력으로 들어온 간선수(E)가 최대간선수(V*(V-1)/2)보다 어떤지 봄 보통 최대간선수의 절반(1/2)보다 작으면(희소그래프) → 인접리스트가 유리 보통 최대간선수의 절반(1/2)보다 크면(밀집그래프) → 인접행렬이 유리 그래프 문제 풀이 과정 1) 그래프가 무향인지 유향인지 봄 2) 무/유향에 따라 정점수를 보고 → 최대간선수를 생각해봄 3) 가중치 있는지 없는지 봄 최단 경로 정의 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 가중치 여부에 따른 그래프 최단 경로 가중치가 없는 그래프의 최단경로 => 간선수 최소여야!! => 무조건 BFS 거쳐가는 ..