Algorithm/개념 정리

Gyoogle (규글)
다익스트라(Dijkstra) 알고리즘
·Algorithm/개념 정리
다익스트라(Dijkstra) 알고리즘 DP를 활용한 최단 경로 탐색 알고리즘 다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다. 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다. 다익스트라를 구현하기 위해 두 가지를 저장해야 한다. 해당 정점까지의 최단 거리를 저장 정점을 방문했는 지 저장 시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다. 다익스트라의 알고리즘 순서는 아래와 같다. 최단 거리 값은 무한대 값으로 초기화한다. for(int i = 1; i
[알고리즘] 비트마스크(BitMask)
·Algorithm/개념 정리
비트마스크(BitMask) - 집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉 왜 비트마스크를 사용하는가? - DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제 - 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함) - 집합을 배열의 인덱스로 표현할 수 있음 - 코드가 간결해짐 비트(Bit)란? 컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1) 2진법을 생각하면 편하다. 우리가 흔히 사용하는 10진수를 2진수로 바꾸면? 9(10진수) → 1001(2진수) 비트마스킹 활용해보기 - 0과 1로, flag 활용하기 [1, 2, 3, 4 ,5] 라는 집합이 있다고 가정해보자. 여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의..
[알고리즘] 퀵소트(QuickSort) 구현 (C)
·Algorithm/개념 정리
수, 문자열 등 정렬이 필요한 상황에 퀵소트를 라이브러리 없이 구현하기 위함 정렬 조건 자체가 많더라도, while문 안에서 모두 해결이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include int arr[] = { 1, 10, 6, 9, 8, 2 }; void quickSort(int *, int start, int end); int main(void) { int size = sizeof(arr) / 4; printf("Before : "); for (i..
[알고리즘] LCA(Lowest Common Ancestor)
·Algorithm/개념 정리
[알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상을 찾는 알고리즘 → 두 정점이 만나는 최초 부모 정점을 찾는 것! 트리 형식이 아래와 같이 주어졌다고 하자 4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2' 4와 6의 LCA는? → 첫 부모 정점은 root인 '1' 어떻게 찾죠? 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다. [depth : 정점] 0 → 1(root 정점) 1 → 2, 3 2 → 4, 5, 6, 7 parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다. // 1 ~ 7번 정점 (root는 부모가 없기 때문에 0) int parent..
[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기
·Algorithm/개념 정리
[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기 사이클을 찾기 위해서는 DFS를 활용한다. (정점 : v, 간선 : e) - visited[] : 점들의 방문여부가 저장된 배열 - recur[] : v가 지금까지 방문한 점이 저장된 배열 for(v 수 만큼) { dfs(v, visited, recur) } DFS 수도코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 boolean dfs(v(a), visited, recur) { visited[v(a)] = true recur[v(a)] = true for(v(a)와 연결된 점의 수만큼) { b = 연결된 점 if(!visited[b] && dfs(v(b), visited, recur){ // b가 방문상태..
[알고리즘] XOR 비트 연산을 활용하기
·Algorithm/개념 정리
[알고리즘] XOR 비트 연산을 활용하기 비트 연산을 활용해서 문제에 적용하면 상당히 효율적으로 코딩이 가능한 경우가 있다. 특히 코딩테스트와 같이 문제를 풀 때 비트 연산을 활용하면 좋다. 이번에 살펴볼 예시는 보통 네이버나 카카오 등 프로그래머스를 이용해 코딩테스트를 보게 되는데, 테스트 환경에서 연습해보는 1번 문제로 등장하는 유형이다. 직사각형의 3개 점이 주어진다. 나머지 하나의 점의 좌표를 구하라. (직사각형은 항상 평행한 상태) ex) (2, 0) (6, 0) (6, 6) 정답 : (2, 6) 다양한 방법을 이용해 푸는 것이 가능하지만, 가장 신박했던 방법은 비트연산을 활용해 푸는 것이었다. XOR은 입력 값 중 하나만 true일 때 true를 리턴해준다. 따라서 주어진 3점의 x좌표와 y좌..
[자료구조/Java] 이진탐색트리 (Binary Search Tree)
·Algorithm/개념 정리
[자료구조/Java] 이진탐색트리 (Binary Search Tree) - 각 노드의 자식이 2개 이하인 트리 - 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 노드 삽입 시간 균등 트리 : 노드 개수 N개일 때 O(logN) 편향 트리 : 노드 개수 N개일 때 O(N) 삽입,검색,삭제의 시간복잡도는 트리 높이에 비례함 삭제가 조금 까다로움 (3가지 case) 1. 자식이 없는 leaf 노드면? → 그냥 지우면 끝 2. 자식이 1개인 노드면? → 지워진 노드에 자식을 올리면 끝 3. 자식이 2개인 노드면? - 자식 노드 중에서 삭제할 노드보다 크면서 가장 작은 값 - 자식 노드 중에서 삭제할 노드보다 작으면서 가장 큰 값 편향된 트리(ex. 정렬된 상태인 값을 트리로 만들면 한쪽으로 뻗는다)에서..
[자료구조/Java] 힙(Heap) 구현
·Algorithm/개념 정리
시간이 지나면 자꾸 까먹는다.. 그래서 다시 정리해봐야겠다 자료구조의 핵심 중 하나인 힙(Heap)에 대해 알아보자 힙(Heap) 완전 이진트리의 일종이다. 반정렬 상태(완전히 정렬된 상태가 아님)이며, 완전 이진트리와는 다르게 중복값이 허용된다. 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이기 때문이다. 힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가 가장 작은 것이다. 이를 통해 여러 값 중에서 최소 값이나 최대 값을 빨리 찾을 때 유용하게 이용할 수 있다. 힙 자료구조는 보통 배열을 이용하며, 0번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다. 1번째 인..
[Java] HashSet을 ArrayList로 변환하기
·Algorithm/개념 정리
[Java] HashSet을 ArrayList로 변환하기 HashSet set = new HashSet(); for (int i = 0; i < T; i++) { set.add(br.readLine()); } ArrayList list = new ArrayList(set); 중복되는 값을 제외하고 저장하고 싶은 경우가 존재한다. 이때 HashSet을 통해 저장한 뒤 ArrayList로 변환해주면 값을 뽑을 때 매우 유용하다
[Java] String 문자열 reverse하기
·Algorithm/개념 정리
[Java] String 문자열 reverse하기 엄청 간단한 문제다. 근데 reverse를 함수로 구현하지 않고, StringBuilder를 사용하면 빠르게 찾을 수 있다는 것을 알게 된 문제 String 값이 주어져 있으면, 아래와 같이 써주면 된다. new StringBuilder("스트링 변수이름").reverse().toString(); 123456789101112131415161718192021222324import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main_2908_상수 { public static void main(String[] args) ..
[알고리즘] 서로소 집합(Disjoint-sets) - Java
·Algorithm/개념 정리
서로소 집합(Disjoint-sets) [알고리즘] 서로소 집합(Disjoint-sets) 서로소 or 상호배타 집합서로 중복 포함된 원소가 없는 집합(= 즉, 교집합이 없는 것) 대표자(representative)집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분 상호배타 집합 표현 방법연결 리스트트리 상호배타 집합 연산Make-Set(x), Find-Set(x), Union(x,y) 트리를 이용해 상호배타 집합 표현된 모습부모는 해당 노드의 Find-Set 값 연산Make_Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산Find_Set(x) : x를 포함하는 집합을 찾는 연산(해당 노드의 부모 정보 갱신)Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산 M..
[알고리즘] 트라이(Trie) - Java
·Algorithm/개념 정리
[알고리즘] 트라이(Trie) 트라이(TRIE) 트라이(TRIE)retrieval 문자열의 집합을 표현하는 트리를 말한다모든 문자열은 다른 문자열의 접두어가 아니라고 가정 부분 문자열 검사ba가 abac의 부분 문자열인가?두개 접두사의 최장 공통 접두어 찾기abac와 ac의 최장 공통 접두어는?사전적 순서로 정렬된 k번째 접미사 찾기abac의 3번째 접미사는? : abac, ac, bac, c (정답 : bac) 각 간선은 하나의 문자에 대응한다같은 노드에 나오는 간선들은 같은 레벨을 갖지 않음각 문자열은 단말 노드에 대응한다 Compressed Trie노드들과 간선들을 부분 문자열로 압축(= 접미어 트리(Suffix Tree)) 문자열 S = {xabxac}에 대한 접미어 트리 발생하는 문제점 해결책하..
[알고리즘] 다익스트라(Dijkstra) - Java
·Algorithm/개념 정리
[알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 경로를 찾을 때 가중치가 있으면 사용하자 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.Arrays; /** * Dijkstra : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 * * Greedy 방식, 음이 아닌 가중치일 경우만 사용가능 * 음의 가중치가 있는 경우 => 벨만포드 알고리즘을 통해서 구해야 한다 * 시간복잡도 O[n^2] */ public cl..
[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization)
·Algorithm/개념 정리
[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization) 동적 계획법이란? 주어진 문제를 세분화시키고, 최적의 해법을 찾아내기 위한 방법 DP를 이용하면 중복된 부분을 제거하여 다시 계산하지 않아도 되는 장점이 있다. 이는 연산의 효율을 높여주는데 큰 역할을 한다. 이를 알아보기 위해서는 '피보나치 수열'로 알아보기 쉽다 피보나치 수열은 위와 같은 구조로 '재귀 함수'를 통해 구현된다. 즉, index 0과 1을 제외하고 f(n) = f(n-1) + f(n-2)로 정의가 가능하다. 하지만, index의 값이 커질수록 호출되는 재귀함수가 무궁무진하게 커지는 문제가 발생한다. 지금처럼 빨간 원으로 묶인 부분은, 완전히 똑같은 부분을 다시 불러오는 모습을 볼 수 있..
[알고리즘] 백트래킹(Backtracking)
·Algorithm/개념 정리
[알고리즘] 백트래킹(Backtracking) [알고리즘] 백트래킹(Backtracking) 백트래킹이란?모든 경우의 수를 검색하는 알고리즘'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘 후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!후보해 : 정답이 될 가능성이 있는 모든 조합최적해 : 문제의 답으로 기준을 만족하는 해 DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음 DFS와 백트래킹의 차이점은 '가지치기'가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님! 가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자 백트래킹 대표 문제..
[알고리즘] 백트래킹을 활용한 부분 집합 & 순열
·Algorithm/개념 정리
[알고리즘] 백트래킹을 활용한 부분 집합 & 순열 백트래킹 부분 집합 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364/** * * powerset 구하기 * */ public class powerset_backtrack { static int[] arr = {3, 5, 8}; // arr 배열의 모든 부분집합을 구해보자 public static void main(String[] args) { boolean[] a = new boolean[arr.length]; // 부분집합에서 원소를 사용할 지 여부를 체크할 배열 backtrack(a, 0..
[알고리즘] Queue
·Algorithm/개념 정리
[알고리즘] Queue Queue 1234567891011121314151617181920212223242526272829303132333435363738394041424344public class Queue { public static int front = -1; public static int rear = -1; public static int[] q = new int[5]; public static boolean isFull() { return rear == q.length -1; } public static boolean isEmpty() { return front == rear; } public static void enQueue(int item) { if(isFull()) { System.ou..
[알고리즘] 순열 & 조합
·Algorithm/개념 정리
[알고리즘] 순열 & 조합 조합 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; /** * * 조합 4 2 (4C2) 0 1 0 2 0 3 1 2 1 3 2 3 * */ public class comb { public static void comb(int[] set, int size, int n, int k, int index){ if(k==0) { for (int i = 0; i
[알고리즘] 후위표기법
·Algorithm/개념 정리
[알고리즘] 후위표기법 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677import java.util.ArrayList;import java.util.Scanner;import java.util.Stack; public class 후위표기법 { public static int priority(char ch) { switch (ch) { case '*': case '/': return 2; case '+': case '-': return 1; case '(': case ')': return 0; }..
[C++] 배열 사이즈 구하기
·Algorithm/개념 정리
배열의 사이즈를 구할 때는 sizeof를 사용하자. 이때 배열의 sizeof에 첫번째 인덱스 sizeof를 나눠줘야 원하는 사이즈가 나오는 것을 기억할 것 #include using namespace std; int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout
[알고리즘] 이분 탐색(Binary Search)
·Algorithm/개념 정리
[알고리즘] 이분 탐색(Binary Search) 정렬되어있는 리스트가 있을 때, 가운데 값과 비교해나가면서 가능한 정답의 범위를 절반으로 줄여나가며 어떤 수가 존재하는 지, 존재하지 않는 지 찾는 알고리즘 언제 이용?정답을 구하는 문제A에서 B까지 가는 가장 빠른 시간을 구하는 것 - 최적화가능여부를 판별하는 문제로 바꾸기 가능가능한지 살펴보는 문제A에서 B까지 X라는 시간으로 이동할 수 있을까? - YES/NO ex. A에서 B까지 가는 가장 빠른 시간이 M인 경우M보다 빠른 시간 - 모두 불가능M보다 큰 시간 - 모두 가능 문제에 주어지는 기준 점(X)를 통해 가능성 여부를 따져서 정답을 찾아낸다. 이분 탐색에 해당하는 문제 랜선 자르기 : https://www.acmicpc.net/problem/..
[알고리즘] 그리디 알고리즘
·Algorithm/개념 정리
그리디 알고리즘만약 문제 중에 그리디 알고리즘이 나오면? -> 가장 나중에 풀자! 생각보다 까다로울 수 있는 문제일 수 있기 때문에 마지막에 시간을 많이 갖고 풀어야 함 결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘그때 그때는 최적일지도 모르지만, 최종적으로는 답이 최적이 아닐 수도 있는 가능성 존재 그리디 알고리즘은 언제 써야하나?지금 이 순간, 가장 좋은 경우를 선택하는 것이 항상 최적인 경우 그냥 생각하면 쉬워보이지만, 왜 최적인지 증명을 해야하기 때문에 그리디 알고리즘은 상당히 어려운 영역임
[알고리즘] 다이나믹 프로그래밍
·Algorithm/개념 정리
[알고리즘] 다이나믹 프로그래밍큰 문제를 작은 문제로 나눠서 푸는 알고리즘 Overlapping Subproblem겹치는 부분 문제Optimal Substructure문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 Overlapping Subproblem큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.문제를 작은 문제로 쪼갤 수 있다.ex. 피보나치 수 Optimal Substructure문제의 정답을 작은 문제의 정답에서 구할 수 있다.ex. 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다. 이 두 가지를 활용하는 것이 다이나믹 프로그래밍!다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 함Optimal Subst..
[알고리즘] 자료구조 (스택, 큐, 덱, 문자열)
·Algorithm/개념 정리
[알고리즘] 자료구조 (스택, 큐, 덱, 문자열) 스택 (Stack)한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조마지막에 넣은 것이 가장 먼저 나오는 LIFO 구조push : 스택에 자료 넣음pop : 스택에서 자료 뺌top : 스택의 가장 위에 있는 자료empty : 스택이 비어있는지 아닌지 확인size : 스택에 저장된 자료의 개수 확인 사용방법C++STL의 stack 이용Javajava.util.Stack - push stack[size] = v; size += 1; ​ - pop stack[size-1] = 0; size -= 1; 스택 활용 문제괄호 : https://www.acmicpc.net/problem/9012쇠막대기 : https://www.acmicpc.net/problem/1079..
Gyoogle
'Algorithm/개념 정리' 카테고리의 글 목록
상단으로

티스토리툴바