알고리즘

#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구성된 그래프에서 최단 경로 혹은 특정 조건을 만족하는(최소 신장 트리, etc) 경로를 찾는 데 사용됩니다. 다양한 종류의 길 찾기 알고리즘이 있으며, 알고리즘의 선택은 그래프의 크기, 가중치의 종류, 실행 시간 제약 등을 고려합니다. 따라서, 알고리즘의 특징과 제약 사항 등을 이해해야 주어진 문제에 가장 적합한 알고리즘을 선택할 수 있습니다.[종류]1. "단일 출발(single-source)" :  주어진 단일 노드 v로부터 다른 모든 노드 사이의 최단 경로를 찾는 문제 2. "단일 쌍(single-pair)" :..

[기술 질문] #18_알고리즘 복잡도 알고리즘의 복잡도에 대해 알아보겠습니다. Overview 개념 시간 복잡도 공간 복잡도 #0. 개념 1. 복잡도 알고리즘의 복잡도는 알고리즘의 입력 크기와 연산 횟수 사이의 관계를 나타내는 함수입니다. 보통 시간 복잡도와 공간 복잡도로 나누어져 있습니다. #1. 시간 복잡도 1. 개념 시간 복잡도는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수를 입력 크기와 연관시켜 분석하는 것입니다. 결과적으로, 입력 크기에 따라서 알고리즘의 실행 시간이 어떻게 변화하는지 나타내며, 알고리즘의 효율성과 성능을 평가하는 중요한 지표 중 하나입니다. Big-O 표기법은 알고리즘의 시간 복잡도를 점근적으로 표기하는 방법입니다. 즉, 알고리즘의 입력의 크기가 충분히 커질 때, 알고..

[알고리즘, GFG]#1_Binary Search, 이진 탐색 geeksforgeeks 연습 문제 중 BInary Search(이진 탐색) 문제입니다. Overview 문제 개념 풀이 문제 풀이 1. 개념 이진 탐색 알고리즘은 "정렬된 상태"의 데이터 목록에서 특정한 값의 위치를 찾는 알고리즘입니다. 기본적으로, 이진 탐색 알고리즘은 배열의 왼쪽 끝(Left), 오른쪽 끝(Right), 그리고 가운데(Mid) Index를 활용합니다. 글로 쓰는 것보다 코드를 보는 것이 훨씬 이해하기 쉽기 때문에 자세한 내용은 아래 코드에서 설명하겠습니다. 이진 탐색 알고리즘의 시간 복잡도는 O(log n)으로, 선형 탐색보다 빠릅니다. 다만, 오직 "정렬된" 상태의 데이터 목록에서만 활용할 수 있습니다. 결과 코드 //..

[BOJ알고리즘, C++]#1676_팩토리얼의 0의 개수, 소인수분해 BOJ 알고리즘 문제 풀이, 1676_팩토리얼의 0의 개수 소인수분해의 성질을 이용해 N! 의 뒷자리 0의 개수를 구합니다. 문제 풀이 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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9..

[BOJ 알고리즘, C++] #10815_숫자 카드, 이진 탐색, Binary Search BOJ 알고리즘 문제 풀이, 10815_숫자 카드 이분 탐색을 통해 주어진 숫자 카드가 존재하는지 탐색합니다. Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 이진 탐색(Binary Search) Details [정의] : 정렬된 원소 목록을 반으로 나누어 찾고자 하는 원소와 중심이 되는 원소를 비교하고, 작다면 왼쪽으로 크다면 오른쪽으로 중심 원소를 옮겨서 반복적으로 비교 작업을 수행합니다. 시간 복잡도는 O(log n)으로 선형 탐색보다 뛰어난 성능을 보여줍니다! 다만 몇 가지 단점들이 물론 존재합니다! [특징] : 정렬 상태의 자료구조에서만 가능합니다. 그리고, 연결 리스트에서 사용이 힘듭니다...

[BOJ 알고리즘, C++] #11050_이항 계수 1, 이항 계수 공식, 재귀 문 활용 BOJ 알고리즘 문제 풀이, 11050_이항 게수 1 이항 계수 공식을 재귀문을 구현하는 문제 문제 풀이 1. 이항 계수 공식 ( N ) ( K ) = N! / ( K! (N - k)! ) 2. 팩토리얼 재귀문 int Factorial( int num ) { if(n == 0 || n == 1) return 1; else return num * Factorial(num - 1); } 결과 코드 #include using namespace std; int N, K; // 재귀문을 활용한 Factorial 구현 int Factorial(int num) { if(num == 0 || num == 1) return 1; e..

[BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법 BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 공배수를 구하는 문제   문제 풀이 1. 유클리드 호제법A = 106, B = 161.C = A % B = 106 % 16 = 10A 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다.A와 B를 나눈 나머지 값을 R이라고 한다면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다!이 성질을 이용하여, B(혹은 Determinant)를 이전의 나머지 값으로 나누는 작업을 반복합니다.최종적으로, 나머지 값이 0이 되었을 때, "마지막 B" 값이 A와 B의 최대 공약수..

[BOJ 알고리즘, C++] #11660_구간 합 구하기 5 BOJ 알고리즘 문제 풀이, 11660_구간 합 구하기 5 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 1. 먼저, 2차원 배열의 누적합을 "열" 순으로 누적 합을 계산하는 것이 아니라, "행" 순으로 계산해야 합니다. 2. 누적 합을 계산하는 방법은 아래와 같이 "[i-1][j] + [i][j-1] - [i-1][j-1]"입니다. prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] "행"을 기준으로 누적 합을 계산하다 보면 "중복"으로 누적된 값이 존재합니다! 위 그림을 살펴보면, prefixSum[4]를 위해 prefixSum[2]와..

[Programmers 알고리즘, C++]#Level 1_키패드 누르기 Programmers 알고리즘 문제 풀이, Level1_키패드 누르기 STL 컨테이너 활용과 규칙을 찾아 풀이하는 문제입니다. 문제 풀이 먼저, "1 - 4 - 7"은 "L", 그리고 "3 - 6 - 9"는 "R"이 확정입니다. 따라서, C++가 제공하는 STL 컨테이너 중 "map"을 활용해봤습니다. key 는 키패드의 숫자로 설정하고, 미리 확정된 손을 value로 하였습니다. 예를 들면, {1, "L"}, {3, "R"}, ... etc 물론, "2 - 5 - 8 - 0"은 정해진 손이 없기 때문에 "U(Undefined)"로 value를 저장합니다. 더불어, '*', '0', 그리고 '#'은 편의상 각각 10, 11, 그리고 ..

[Programmers 알고리즘, C++]#Level1_크레인 인형 뽑기, 2차원 배열, stack, STL 컨테이너, adjacent_find() Programmers 알고리즘 문제 풀이, Level1_크레인 인형뽑기 2차원 배열의 개념과 STL 컨테이너 활용 문제 문제 풀이 문제는 스택 자료구조에대한 이해와 2차원 배열의 활용을 요구합니다. 먼저, 주어진 2차원 배열에서 탐색을 진행하고, 스택에 차례대로 "push_back" 합니다. 간단하게 stack(바구니)에 저장된 이전 항목과 현재 저장할 항목을 비교할 수 있지만, STL 알고리즘을 활용해보고자 "adjacent_find"를 사용해보겠습니다! 굉장히 간단합니다. 바로 코드를 살펴보겠습니다. * 주의할 점은 "N x N" 격자 밑에 있는 숫자는 ..