지나공 : 지식을 나누는 공간

오늘 알아볼 내용은, 순차 탐색 이진 탐색 트리 자료구조 이진 탐색 트리 실전문제 - 부품 찾기 실전문제 - 떡볶이 떡 만들기 순차 탐색 [개념] 가장 기본 탐색 방법으로, 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 탐색 알고리즘이다. 이름처럼, 순차로 데이터를 탐색한다. [사용예] - 배열에 특정 값의 원소가 있는지 체크할 때 - 배열 자료형에서 특정한 값을 가지는 원소의 개수를 셀 때 [코드] #include #include #include using namespace std; int sequantialSearch(int n, string target, vector arr) { //모든 원소 하나씩 확인 for (int i = 0; i < n; i++) {..

정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬이 되면 이진 탐색이 가능해진다. 선택정렬, 삽입정렬, 퀵정렬, 계수 정렬에 대하여 선택 정렬 [소개] 가장 원시적인 방법으로 매번 '가장 작은 것을 '선택'하는 정렬 [방법] 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. [그림] [코드] #include using namespace std; int n = 5; //정렬할 개수 int arr[10] = { 7, 4, 5, 9. 8, 2, 1 }; int main(void) { for (int i = 0; i < n; i++) { int min_ind..

탐색(Search)? DFS/BFS? -> 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이 탐색 -> 탐색의 대표적인 예로 그래프 탐색 알고리즘은 DFS와 BFS가 있다. 이번 포스팅에서 알아볼 것 스택의 자료구조와 구현 큐의 자료구조와 구현 재귀함수(의미, 구현, 팩토리얼 구현으로 알아보는 재귀함수) 유클리드 호제법 with 재귀함수 DFS 동작과 구현 BFS 동작과 구현 스택(Stack) -> 마지막에 들어간 데이터가 먼저 빠져나오는 구조 -> LIFO (Last In First Out) 스택코드 구현 삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제() 큐(Queue) -> 처음에 들어간 데이터가 먼저 빠져나오는 구조 -> FI..

이것이 코딩테스트다. chapter 4 구현 실전 문제 풀이 구현 문제는 어떤 문제? 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정으로, 어떤 문제든 간에 해당이 될 수 있는 매우 넓은 범위의 유형이다. 구현 문제를 풀 때 생각할 점들 - 파이썬 기준 1초에 2000만 번의 연산 수행을 가정할 때 크게 무리가 없음 - 시간제한이 1초이고, 데이터 개수가 100만 개인 문제에서 N= 1,000,000이면 시간복잡도가 NlogN=20,000,000이므로 이정도의 데이터를 혀용한다고 생각하고 문제를 풀면 무리가 없을 것임 이제, 문제를 풀어보자. 1. 상하좌우 문제 문제) 여행가 A는 N*N의 크기의 정사각형 공간 위에 서 있다. 이 공간은 1*1 크기의 정사각형으로 나누어져 있다. 가장 왼 쪽 위 좌표는..

그리디 알고리즘이란? 현재 시점에서의 최적의 선택을 하는 알고리즘입니다. 전체 시점에서는 그게 가장 좋은 답이 아닐 수 있습니다. 매 시점마다 당장 그 시점에서의 최선의 답을 찾는 방식이기 때문입니다. 아래 그림에서 거치는 노드의 숫자 합이 가장 큰 선택을 해야 한다고 합시다. 우리 입장에선 전체 노드가 보이기 때문에 당연히 왼쪽처럼 선택을 해야 숫자 합이 0+3+100 = 103이 되므로 최적의 선택이 된다는 걸 압니다. 하지만 그리디한 선택은 당시에 위치하는 노드에서 바라볼 때 가장 큰 숫자로 가는 것이므로 오른쪽 그림처럼 선택하게 됩니다. 그리디한 선택을 한 결과(0+10+8 = 18)는 실제 최적의 답(103)보다 좋지 않은 답일 수 있습니다. 즉, 그리디 알고리즘에서 모든 선택이 최적의 선택과 ..