한다 공부

이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다. 이러한 이분 탐색은 실생활에서도 많이 쓰인다. 최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다. 1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다. 이 방법이 이분 탐색이다. C++에서는 #include을 통해 binary_search라는 함수를 사용할 수 있다. 이 경우 원하는 요소가 있으면 1을 반환, 없으면 0을 반환한다. 그런데 보통의 알고리즘 문제에서는 1, 0을 반환하는 것 뿐만 아니라 해당 요소의 인덱스 (위치) 등을 물어볼 수도 있기 때문에 이를 구현할 줄 알아야한다. 함수를 이용해서 풀 수도 있다. 주의해야할 점은, 이분 탐색에서..

탐욕 알고리즘이라고 불리는 그리디 알고리즘이란 무엇일까? 그리디 알고리즘이란, 지금 상황에서의 최선의 선택이 곧 정답이라는 알고리즘이다. 시간적으로 효율적이지만, 매번 그리디로 푼 풀이가 정답이 아닐 수도 있다!! 그리디 알고리즘을 사용하려면 현재 최선의 선택이 전체 문제의 정답이어야한다. O(N) 시간복잡도를 가지고, 백만 이상의 입력도 받을 수 있다. 주로 정렬과 우선순위 큐를 함께 이용한다. 그리디임을 확인하기 위해서는 많은 수학적 증명이 필요하다고 한다. 그러므로 보통의 경우, 직관적으로 판단하여 그리디를 사용한다고 한다. [C++] 백준 알고리즘 1931 회의실 배정 (그리디) (tistory.com) [C++] 백준 알고리즘 1931 회의실 배정 (그리디) 1931번: 회의실 배정 (acmic..

동적 계획법 (dynamic programming) 이란 무엇일까? 바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다. 예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자. 왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다. 출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 있다. 그리고 출발지에서 오른쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 4의 비용으로 오른쪽 노드까지 갈 수 있다. 그리고 왼쪽 노드의 dp 값 + 왼쪽 노드에서 도착지까지 올 때의 비용 = 3 + 10 = 13 , 오른쪽 노드의 dp + 오른쪽 노드에..

백트래킹이란? 브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다. 백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다. 백트래킹은 주로 N의 값이 20보다 작을 때 이용한다. 백트래킹을 정리하자면 1. 종료 조건을 잘 설정하자 2. 입력 범위가 작을 때 (N

에라토스테네스의 체란 무엇일까? 소수를 판단할 때 유용하게 쓰인다. 소수란 1과 자기자신으로만 나누어지는 수이다. 2 3 5 7... 등이 있다. 2부터 생각을 해보자. 2는 소수이다. 2*n배는 소수가 아니다. 그렇다면 2*2, 2*3, 2*4.... 2*(n) 은 모두 소수가 아니므로 제거한다. (코드에서는 bool형 배열을 false함으로써 제거) 그리고 3도 같은 방법으로 3의 배수들을 false한다. 4의 경우 이미 2*2에서 false되었으므로 5를 확인한다. 이런식으로 계산을하면 소수 2 3 5 7..은 남아있고, 소수가 아닌 어떤 수들의 배수들인 4 5 8 9 10... 은 false처리되며 제거된다. 이 방법으로 소수 판정을 하면 O(nlog(log n))만에 가능하다. false로 바꿔..

문제풀이랑 개념을 같이 적어두니 헷갈려서 개념만 적어두는 게시글을 새로 만들었다 GCD(Greatest Common Divisor) GCD란 최대공약수를 의미한다. 최대공약수를 구할 땐 유클리드 호제법을 이용하는게 편하다. 유클리드 호제법이란, a b의 최대공약수가 a%b(나머지) b의 최대공약수가 같다는 것을 이용하는 것이다. 예를 들어 15와 10이 있다고 해보자. a=15, b=10이라고 하면 a%b=5, b=10이 된다. 이 a%b값을 a에 대입하자. x%y를 할 때에는 x>y여야하므로 둘의 자리를 바꿔줘야한다 그러면 a=10, b=5가 된다. 나머지가 0이 될 때까지 해보자. a%b=5, b=5가 된다. a%b를 a에 대입하면 a=5, b=5가 되고 a%b = 0이 된다. 0이 되면 작은 값인 ..

우선순위 큐란, 우선순위의 개념을 큐에 도입한 자료구조이다. 선입선출 FIFO(First In First Out)인 큐와 달리 우선순위 큐는 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐는 배열, 연결리스트를 이용할 수도 있지만 히프라는 자료구조로 구현하려고 한다. Heap heap heap 히프는 우선순위 큐를 위해 만들어진 자료구조이다 배열로 구현한 히프는 삭제시 O(n)의 복잡도를 가지고 연결리스트 히프는 삭제시 O(n)의 복잡도를 가진다 하지만 히프의 경우 어느정도 정렬이 된 상태기 때문에 O(log n)의 복잡도를 가진다 데이터가 많아질수록 n과 log n의 경우 차이가 크기 때문에 히프를 사용하는 것이 효율성이 높다 히프는 부모 노드의 키 값이, 자식 노드의 키 값보다 항상 큰 이진트리이..

binary search tree 이진 탐색 트리 : 이진 트리 기반의 탐색을 위한 자료구조이다. 이진 탐색 트리의 정의는 다음과 같다. 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리의 키들은 루트의 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 쉽게 말하자면 루트를 기준으로 작은 수는 왼쪽 노드에, 큰 수는 오른쪽 노드에 붙이면 된다. 18 26 7 12 3 31 27 이 랜덤하게 주어졌다고 하자. 그럼 우선 첫 번째 주어진 18을 루트로 잡는다. 그리고 두 번째 주어진 26은 18보다 크므로 오른쪽 자식노드로, 세 번째 주어진 7은 18보다 작으므로 왼쪽 자식노드로 넘긴다 그리고 네 번째 주어진 12는 18보다 작으므로 왼쪽 자식노..

앞에서 본 이진트리는 순회하는 것 말고도 다양한 연산들이 있다. 이번 포스팅에서는 트리의 전체 노드 개수 세기 단말 노드의 개수 구하기 트리의 높이 구하기 를 알아보고자 한다. 앞에서 사용한 이 트리를 이용해보자 트리를 보면 알 수 있듯이 전체 노드는 7개이다. 단말 노드는 3개이다. (22 35 95) 트리의 높이는 4이다. #include #include typedef struct TreeNode { struct TreeNode* left; int data; struct TreeNode* right; }TreeNode; TreeNode n7 = { NULL,22,NULL }; TreeNode n6 = { NULL,95,NULL }; TreeNode n5 = { &n7,35,NULL }; TreeNod..

아까 이진트리를 구현할 때 10 / \ 20 30 위와 같은 트리를 어떻게 순회해야 잘 순회했다고 소문이 날까? 여기엔 크게 3가지 순회가 있다. 전위 순회란 루트를 방문하고 왼쪽 서브트리, 오른쪽 서브트리를 방문하는 순회이다. 위의 트리를 예시로 들면 10 -> 20 -> 30 순으로 순회하는 것이다. 아래 코드에서 preorder이라는 함수를 통해 구현을 할 것이다. 중위 순회란 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 순회이다. 위 트리를 예시로 들면 20 -> 10 -> 30 순으로 순회한다. 아래 코드에서 inorder이라는 함수를 통해 구현을 할 것이다. 후위 순회란 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문하는 순회이다. 위 트리에서 20 -> 30 ->..