서랑의 개발 블로그

✅ 동적계획법(Dynamic Programming) 동적계획법(Dynamic Programin)이란 큰 문제를 작은 문제로 나누어 해결 한 뒤 그 해를 활용하여 큰 문제를 해결해 나가서 결국 최종 문제를 해결하는 알고리즘이다. Memoization(메모이제이션)기법 : 해결한 문제의 해를 저장해 둔 뒤, 똑같은 문제가 발생하였을 때 저장해 놓은 해를 사용함으로써 중복 연산을 하지 않고 빠르게 해결하는 기법이다. ✔ 동적 계획법 예시 피보나치수열 점화식 f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) 피보나치수열의 점화식을 그림으로 표현해보면 위 그림과 같다. 위 그림을 보면 동일하게 중복돼서 사용되는 함수가 있다. f(0), f(1), f(2)가 반복되어서 사용되고 아마 숫자가 ..

✅ 이분 탐색(Binary Search) 이진 탐색이라고도 불리며 이미 정렬된 데이터에서 특정 값을 찾을 때 절반 씩 나눠가며 찾는 알고리즘이다. 분할 정복 알고리즘 (Divide and Conquer) Divide(분할) : 문제를 하나 또는 둘 이상으로 나눈다. Conquer(정복) : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고 아니면 또 나눈다. 이분 탐색(Binary Search) Divide(분할) : 정렬된 데이터를 절반으로 나눈다. Conquer(정복) 검색할 값(Search) > 중간값이면 오른쪽에서 다시 데이터를 찾는다. 검색할 값(Search) < 중간값이면 왼쪽에서 다시 데이터를 찾는다. 출처 - https://blog.penjee.com/binary-vs-linear-s..

✅ BFS 대표적인 그래프 탐색 알고리즘으로 너비 우선 탐색으로 BFS(Breadth First Search)라고 부른다. 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 알고리즘이다. 큐(Queue)를 사용하여 구현하고 최소 비용을 구할 때 적합하다. 만약 이런 모양의 그래프가 있다고 하자. 이 그래프를 BFS로 탐색을 하면 1-2-3-4-5-6-7 순서대로 탐색을 하게 된다. ✔ 코드 #include #include using namespace std; int ch[8] = {0,}; // 노드를 방문했는데 체크하는 함수 int arr[8][8] = { {0,},{0,0,1,1,0,0,0,0}, {0,1,0,0,1,1,0,0}, {0,1,0,0,0,0,1,1}, {0,0,1,0,0,0..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17680 = cacheSize) cache.pop_front(); cache.push_back(s); answer += 5; } } 그러고 나서 for문을 cities의 size만큼 돌아주었다. transform(s.begin(), s.end(), s.begin(), ::tolower); deque ::iterator it = find(cache.begin(), cache.end(), s); 코드를 하나씩 뜯어보자면 제일 처음에 한 일은 똑같은 지역이라도 소문자로 올 수도 대문자로 올 수도 있으므로 일단 통일해주기 위해 다 소문자로 바꿔주었다. 그러고 나서 find함수로 cache에 해당 지역이 있..

✅퀵 정렬(Quick sort) 퀵 정렬(Quick sort)은 Divide and Conquer(분할 정복) 전략을 활용하여 정렬을 해주는 알고리즘이다. 기준점(pivot)을 정해서 기준점보다 작으면 왼쪽, 크면 오른쪽 정렬하고 또 재귀를 통해 오른쪽, 왼쪽 배열을 동일한 방법으로 계속해서 정렬해 주면 된다. 출처 - https://en.wikipedia.org/wiki/Quicksort 이렇게 pivot을 하나 정해 정렬하면 pivot은 제대로 된 위치를 찾은 것이고 그럼 pivot을 제외하고 양쪽 배열의 pivot을 정해 계속 정렬해 나가는 알고리즘이다. ✔ 코드 #include void Quick(int *arr, int start, int end){ if(start>=end){ return; }..

✅정렬 알고리즘 정렬은 어떤 데이터들이 주어졌을 때 정해진 순서대로 데이터들을 나열하는 것으로 프로그램 작성 시 빈번하게 필요하다. 선택 정렬, 버블 정렬, 삽입 정렬은 쉽지만 비효율적인 정렬 알고리즘이다. ✔선택 정렬(selection sort) 선택 정렬(selection sort)은 index 0번 데이터부터 시작하여 0번을 제외한 나머지 정렬되지 않은 데이터들 중 가장 작은(내림차순이라면 큰) 데이터를 찾아 바꾸고, 그다음 index를 1 증가시켜 동일한 방법으로 정렬하는 알고리즘이다. 그러므로 선택 정렬은 앞에서부터 정렬이 이루어진다. 출처 - https://en.wikipedia.org/wiki/Selection_sort 이렇게 index가 0인 맨 첫번째 데이터부터 시작하여 뒤에 남은 나머지..

문제 링크 :https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 https://cocoon1787.tistory.com/292 [C/C++] 백준 1300번 - K번째 수 (이분 탐색) #include #include #include using namespace std; long long N, K; long long Low, High, Mid; long long cnt; long long count(long lo..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 풀이 점수를 어떻게 저장해 놓을지 고민하다 점수는 숫자와 SDT에 의해만 결정이 되고 *, #의 의해서는 원래 점수에 추가적으로 부여되는 것이므로 크기가 3인 배열로 저장해 놓았다. int score[3]; // 점수를 저장할 배열 int n = 0; // index값 char c = ' '; // 옵션(*,#)을 저장할 변수 변수는 이렇게 선언을 하고 바로 for 문으로 dartResult를 하나씩 다 돌아주었다. 숫자 다음은 무조건 SDT중에 하나 이기 때문에 조건문은 옵션(*,#)과 숫자 일 경우로 나눠주었다. i..