본문 바로가기

Computer Science/Algorithm15

맨땅에 헤딩하면서 배운 배낭문제(Knapsack) 유형과 접근법 정리 배낭문제란? 배낭문제는 최대 k 무게를 싣을 수 있는 배낭에 n개의 아이템 을 넣어서 최대의 가치(아이템마다 가치가 다름) 를 만들어내는 문제입니다. 이 문제는 크게 두 가지 유형으로 나눠집니다. 1. 분할 가능한 문제 (Fractional) 대표적인 문제로는 오천원권 만원권 오만원권이 있을 때 목표 금액을 만들기 위해 최소의 수의 지폐를 사용하는 문제가 있습니다. 각 지폐는 더 작은 가치의 지폐로 나눠질 수 있습니다. 이 문제는 그리디 알고리즘 을 사용합니다. 2. 분할 불가능한 문제 (0/1) 이번 포스트에서 살펴볼 내용은 불할 불가능한 문제입니다. 현재 한국에서 사용하는 화폐 단위가 아니라 랜덤한 가치의 화폐가 주어지는 경우입니다. 예를들어 3만원권 7만원권 13만원권이 주어진다면 이는 분할 불가능.. 2023. 4. 23.
Linked List 개념을 활용한 문제 풀이 (프로그래머스, 2021 카카오 인턴십 표 편집) 아래의 문제를 LinkedList를 활용해서 풀다가 시간 초과가 발생하며 배운 점을 간단하게 기록하고자합니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 상황에는 List 내의 삽입과 제거가 빈번하게 발생하기 때문에, 당연히 LinkedList 를 활용해야겠다고 생각했지만 시간초과가 발생했습니다. 그 이유는 Java의 LinkedList 자료구조에서 삽입과 제거가 O(1)의 시간복잡도로 수행할 수 있는 것은 맞지만, 해당 위치로 이동하는데에 O(n)의 시간이 소요되기 때문입니다. 예를 들면 add(index, 추가할 자료), remove(inde.. 2023. 3. 22.
이진 트리 표현하는 방법 이진 트리를 표현하는 방법은 크게 두 가지가 있습니다. 1. 배열을 통해서 표현하는 방법 2. 포인터를 통해서 표현하는 방법 배열을 통해서 표현하기 이 방법으로 트리를 표현하게 되면, 특정 위치의 트리 값을 찾을 때 0(1)의 빠른 속도로 가능하나는 장점이 있지만, 편향된 트리 구조에서는 낭비되는 공간이 많다는 단점이 있습니다. 따라서 포화 이진 트리인 경우에는 이 방법을 활용하는 것이 좋겠습니다. 구현하는 아이디어는 간단합니다. 아래 그림처럼 루트 노드부터 한 depth씩 내려오면서 배열에 하나씩 기록하는 것입니다. 그리고 아래의 몇 가지 규칙을 기억하면 좋습니다. level별 노드의 개수 = 2^level ex) depth가 2인 level의 노드의 개수 = 2^2 = 4 만들어야할 배열의 크기 = .. 2023. 3. 18.
[알고리즘] 비트마스킹 비트마스킹이란? 비트 즉, 2진수를 가지고 자료구조를 표현해서 더 빠르고 효율적으로 연산을 수행할 수 있습니다. 특히 집합 표현을 간결하고 빠르게 할 수 있습니다. 예를 들어 1101 이라는 이진수가 있다면, 각 자리수가 1이라면 그 자리수에 해당하는 것이 존재하는 것이고, 0이면 존재하지 않는다는 식입니다. 이것을 가지고 여러 연산을 수행할 수 있습니다. 비트 연산 우선 기본적인 비트 연산을 자바 기준으로 살펴보겠습니다. 모든 연산은 이진수의 각자리를 비교합니다. 연산자 뜻 & AND (둘다 1이면 1, 아니면 0) | OR (둘 중에 하나 이상이 1이면 1, 둘 다 0이면 0) ^ XOR (둘 이 서로 다르면 1, 같으면 0) ~ 1항 연산자로서 1이면 0으로 0이면 1로 바꿈 A > k 위와 같고,.. 2023. 1. 26.
[알고리즘] 플로이드-워셜 (Floyd-Washall) 플로이드 워셜이란? 모든 노드 사이의 최단 거리를 구하는 알고리즘이며, 음의 가중치에도 사용할 수 있습니다. 시간 복잡도는 O(V^3)으로 그래프의 크기가 작을 때만 사용할 수 있습니다. 어떻게 동작하나? 어떤 임의의 두 노드를 연결하기 위해, 중간 노드를 하나씩 포함시킨 거리와 비교하여 업데이트를 하는 방식입니다. 임의 두 노드(s, e) 사이의 최단거리를 d[s][e]라고 하고, 중간 노드를 m이라고 한다면, 아래와 같은 식을 모든 노드 조합에 반복하는 것입니다. d[s][e] = min(d[s][e], d[s][m] + d[m][e]) 수도 코드로 표현하면 다음과 같습니다. d = 인접행렬로 그래프 표현 for (중간 노드 m in Nodes) for (출발 노드 s in Nodes) for (도착.. 2023. 1. 20.
[알고리즘] Disjoint Set. aka, 서로소 집합. aka, Union - Find Disjoint Set이란? Disjoint Set을 번역하면 서로소 집합입니다. 이는 공통된 원소를 가지고 있지 않는 집합들을 표현하는 자료 구조 입니다. 즉, 교집합이 공집합이고, 상호배타적입니다. https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9 서로소 집합 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 집합론에서 서로소 집합(-素集合, 영어: disjoint sets)는 공통 원소가 없는 두 집합이다.[1] 예를 들어서 {1, 2, 3}과 {4, 5, 6}은 서로소이며 {1, 2, 3}과 {3, 4, 5}는 아니다. ko.wikipedia.org 어떻게 표현하나? 기본적인 원리는, 각 집.. 2023. 1. 17.
[알고리즘] Kruskal 알고리즘 (feat. Union-Find) Kruskal 알고리즘이란? MST(최소신장트리)를 찾는 알고리즘 중 하나입니다. MST란 모든 노드를 사이클 없이 연결하는 신장 트리 중, 비용을 최소로 하는 트리입니다. MST를 찾는 알고리즘은 Kruskal과 Prim 알고리즘이 있으며, dense graphs인 경우에는 Prim이, 그렇지 않은 경우에는 Kruskal이 빠르다고 하니, 상황에 맞게 선택하면 될 것 같습니다. 참고 : https://www.geeksforgeeks.org/difference-between-prims-and-kruskals-algorithm-for-mst/ Difference between Prim's and Kruskal's algorithm for MST - GeeksforGeeks A Computer Science.. 2023. 1. 16.
[알고리즘] 위상 정렬 위상 정렬이란? 그래프를 정렬하는 것입니다. 다시 말해, 방향이 있는 그래프에서 노드 전체를 탐색하는 순서를 1차원으로 나열한 것입니다. 위상 정렬을 수행하기 위해서 두 가지 제약 조건이 존재합니다. 첫째는 언급한 것처럼 방향을 가진 그래프여야하고, 둘째는 그래프에 사이클이 없어야합니다. 당연히 사이클이 있다면 그래프의 시작 지점을 특정할 수가 없습니다. 위상 정렬 방법 진입 차수를 기준으로 위상정렬을 수행할 수 있습니다. 진입 차수[In-Degree]란, 한 노드로 들어오는 간선의 수입니다. 아래의 그래프를 보시죠. [A] → [B] → [D] ↘︎ [C] ↗︎ 위에 A부터 순서대로 진입 차수는 [0, 1, 1, 2] 입니다. 여기서 진입 차수 0의 의미는 가장 먼저 시작하는 노드가 됩니다. 또한, 아.. 2023. 1. 15.
[알고리즘] 누적합 (Prefix Sum) 누적합은 구간의 합을 빠르게 구하는 방법입니다. 1차원 배열에서의 누적합 아래와 같은 1차원 배열이 있습니다. A = [4, -2, 1, 5, -3] 위의 배열에서 인덱스 1번부터 3번까지의 합을 구하고자 합니다. 그럼 -2 + 1 + 5 = 4를 계산해야하니 시간복잡도는 O(N)입니다. 그런데 배열이 크고, 구간합을 자주 계산하게 된다면 시간이 오래 걸리기 때문에, 이럴 때 사용하는 것이 누적합니다. 누적합은 말그대로 누적해서 더하는 것입니다. 아래처럼요. S[n+1] = sum(0, n) 인덱스 0번부터 n번의 합 ( 계산의 편의를 위해 s[0]번은 비워둠 ) S = [0, 4, 2, 3, 8, 5] 일단 누적합을 계산해두고나면, 구간합을 아주 빠르게 구할 수 있습니다. 위의 예시처럼 인덱스 1번부터.. 2023. 1. 13.

티스토리툴바