연의 기록 🪁

이 글은 플로이드 알고리즘을 학습하며 이렇게 짜면 왜 안될까?를 고민한 과정을 작성한 글입니다. 플로이드 알고리즘 자체가 처음이라면 아래 링크에서 플로이드 알고리즘에 대한 개념을 익힌 후 글을 읽으시는 것을 추천합니다.https://blog.encrypted.gg/1035 [실전 알고리즘] 0x1C강 - 플로이드 알고리즘안녕하세요, 이번에는 플로이드 알고리즘을 다루겠습니다. 이제 최단경로 알고리즘인 플로이드, 다익스트라 알고리즘만 다루고 나면 나름 길었던 그래프 파트가 끝납니다. 목차는 눈으로 한 번blog.encrypted.gg 최단거리플로이드 알고리즘은 그래프의 모든 정점간의 최단거리를 구하는 알고리즘이다. 구현하는 방법은 간단한 편이다.NxN크기의 배열을 큰 값(INF)으로 초기화한다.각 정점간의 ..

개요LCS(Longest Common Subsequence)는 최장 공통 부분 수열로, 두 문자열 사이 공통되는 부분을 말한다. 즉 문자열의 상대적인 순서만 같으면 된다.예를들어 아래와 같이 2개의 문자열이 있을 때LCS는 ABCCE이다. 이런 LCS는 DP를 활용해서 구한다.과정먼저 AABCCDE와 A의 공통부분을 구한다고 가정해보자. 표에는 현재까지 가장 긴 공통부분의 길이를 저장할 것이다. 그러면 표는 아래와 같이 된다. (A는 길이가 1이니 최대 공통부분의 길이는 1이다.)이제 AABCCDE와 AB의 최장공통부분수열의 길이를 구해보도록 하자. 그러면 아래와 같이 될 것이다.여기서 주목해야 하는 부분은 공통되는 부분인 B가 나왔을 때이다. 저곳은 AAB와 AB의 LCS의 길이를 기록한 부분인데 AB..

dfs를 응용하여 무향그래프에서의 사이클을 판단할 수 있는 코드이다.  간단하게 설명하자면 점을 하나씩 순회하며 사이클이 존재하는지 판별하는 코드이다. 예를 들어 아래와 같은 그래프가 있다고 하자. 눈으로 봐서는 2 3 5 사이클이 존재함을 알 수 있다. 아래 코드에서는 1에서부터 dfs를 하며 바로 사이클을 찾게 된다.dfs 가장 아래 path.pop_back()은 4와 같이 사이클에 포함되지 않는 노드를 제거하는 코드이다. 인접한 노드가 전에 방문한 노드밖에 없을 때의 경우이다.#include #include #include using namespace std;vector> graph; // 그래프 인접 리스트vector> edges; // 간선 정보vector visited;vector path;b..

퀵정렬은 숫자 하나(pivot)를 골라서 올바른 자리에 넣어가며 정렬을 진행한다. 이때 배열을 쪼개가며 재귀적으로 정렬을 하기 때문에 최종적인 시간 복잡도는 O(nlogn)이다. 동작 과정이론적인 내용에 들어가기 앞서 어떤식으로 동작하는지 확인해보도록 하자. 아래와 같이 {5, 4, 1, 7, 6, 2} 배열이 있다고 했을 때 맨 왼쪽을 피봇으로 잡고 left와 right를 아래와 같이 각각 지정한다.여기서의 left는 pivot보다 작아야하고, right는 pivot보다 커야한다. 이제 left를 하나씩 옮기며 5보다 큰 수가 처음으로 나오는 지점을 찾으면 아래와 같은 상태가 된다.right는 pivot보다 커야한다고 했는데 이미 pivot보다 작다. 그러니 여기서 멈춰준다.이제 left와 right가..

1. 벡터 내에 존재하는지 여부 탐색 (binary_search) 이 경우에는 이진탐색을 사용하는것이 빠르다. 단 이진탐색을 사용하려면 정렬이 되어있어야 한다. 에 정의되어있다. 아래와 같이 사용한다. binary_search(시작범위, 끝범위, 찾을 값); 예제 코드 #include #include #include using namespace std; int main() { int num; cin >> num; vector vec = { 1,3,5,7,9 }; //존재시 1, 그렇지 않으면 0 리턴 if (binary_search(vec.begin(), vec.end(), num)) { cout num; vector vec = { 1,3,5,7,9 }; int idx = find(vec.begin(),..

19-> 1+ 9 = 10 이런식으로 자릿수를 구해주는 코드이다. #include using namespace std; int seperateAndPlus(int x) { int res = 0; while (x != 0) { res = res + x % 10; x /= 10; } return res; } int main() { int num; cin >> num; cout

개념 분할정복 알고리즘은 주어진 문제를 둘 이상의 부분문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘이다. 종만북의 표현을 빌리자면 각개 격파 라고 간단히 설명할 수 있다. 바로 예제를 보도록 하자. 예제 1 : 수열의 합 1부터 N까지의 값을 구해야 한다고 가정하자. 이를 단순 재귀함수로 구현하면 아래와 같을 것이다. #include using namespace std; int recursiveSum(int N) { if (N == 1) { return N; } else { return recursiveSum(N - 1) + N; } } int main() { int A; cin >> A; cout > A; cout

개념 그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 실제 그리디 알고리즘을 검색하면 아래와 같이 나온다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 일반적으로 생각했을 때 눈앞의 이익만을 쫓는 것이 최적의 선택이라고는 할 수 없다. 가령 아래와 같은 상황이 있다고 생각해보자. 예제 1 각 그림의 적힌 숫자는 문제를 푸는데 걸리는 시간이고 우리는 가장 빠른 시간안에 level1, level2, level3문제를 하나씩 해결하려 한다. 이때 문제를 푸는 시간을 최소화 하려면 어떻게 해야 ..

개념 동적계획법의 정의는 아래와 같다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식. 정의만 가지고는 이해하기 쉽지 않다. 뒤에서 설명하겠지만, 결론적으로 말하자면 배열을 만들어 값들을 저장하고, 후에 그것들을 가지고 답을 구하는 방법이다. 동적 계획법을 이용해 문제를 풀려고 한다면 먼저 점화식을 세워야 한다. 점화식이라는 것은 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식이다. 고등학교 때 배웠던 수열의 일반항을 구하듯이 n번째 항을 구하는 방법을 식으로 나타낸다고 생각하면 쉽다. 예를 들어 흔히들 아는 피보나치 수열의 점화식은 아래와 같다. 이제 이 식을 가지고 코드로 작성을 해 보도록 하자. 일반적으로 재귀함수를..

구현 내용 at(𝒊) : 배열 Arr의 인덱스 i에 저장된 값을 출력한다.(단, 0 ≤ 𝑖 ≤ 𝑁 − 1) add(𝒊, 𝒗𝒂𝒍𝒖𝒆) : 배열 𝐴𝑟𝑟의 인덱스 𝑖에서 𝑁 − 2의 값을 오른쪽으로 한 칸씩 이동한다. 그리고 배열 𝐴𝑟𝑟의 인덱스 𝑖번째에 𝑣𝑎𝑙𝑢𝑒를 삽입한다. (단, 0 ≤ 𝑖 ≤ 𝑁 − 1) remove(𝒊): 배열 𝐴𝑟𝑟의 인덱스 𝑖 + 1에서 𝑁 − 1까지의 값을, 왼쪽으로 한 칸씩 이동시킨다. 그리고 배열 𝐴𝑟𝑟의 𝑁 − 1번째 인덱스의 값을 0으로 할당한다. (단, 0 ≤ 𝑖 ≤ 𝑁 − 1) set(𝒊, 𝒗𝒂𝒍𝒖𝒆): 배열 𝐴𝑟𝑟의 인덱스 𝑖번째에 𝑣𝑎𝑙𝑢𝑒를 할당하고 𝑣𝑎𝑙𝑢𝑒를 출력한다. (단, 0 ≤ 𝑖 ≤ 𝑁 −1) print(): 배열 𝐴𝑟𝑟의 모든 값을 공백으로 구분지어 ..

https://thewayaboutme.tistory.com/91 c++ singly linked list 단일 링크드 리스트 구현 * 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 1. 문자열 리스트를 가 thewayaboutme.tistory.com 이 글은 위 블로그 글을 참고하여 작성되었습니다. 연결 리스트를 사용하는 이유 여러가지 값들을 저장하고 처리하는 방법 중 가장 대표적인 것은 아마 배열(Array)일 것이다. 그런데 배열의 경우 중간에 있는 원소를 삭제하거나, 값을 삽입할 때 굉장히 비효율적이다. 만약 아래와 같은 배열이 있다고 가정해보자. 여기서 22를 삭제하려 한..