문제 parameter talking : parrot이 말하는지 hour : 현재 시간 description We have a loud talking parrot. The "hour" parameter is the current hour time in the range 0..23. We are in trouble if the parrot is talking and the hour is before 7 or after 20. Return true if we are in trouble. parrotTrouble(true, 6) → true parrotTrouble(true, 7) → false parrotTrouble(false, 6) → false parrot이 말을 하고, 시간이 7시 전 or 20시 후..
Network Flow 물이 사작점에서 끝점으로 흐를 때, 최대 얼마나 많은 물이 흐를 수 있는지 구하는 경우에 사용 물 대신 데이터, 물건 등으로 바꾸어 나오는 문제도 있음 왼쪽 그래프에서 S가 시작점이며 T가 끝점 엣지에서의 숫자는 용량 제한(capacity)를 의미한다. S에서 A로 갈 때는 최대 3의 물이 흐를 수 있고, F에서 T로는 최대 4의 물이 흐를 수 있다. 오른쪽의 그래프는 실제로 물이 흐르고 있는 그림이다. '/' 앞의 숫자가 실제로 흐르는 물의 양을 의미한다. 1/3은 3의 용량 제한 중에 1만큼 물이 흐르고 있다는 뜻이고, 그냥 3은 0/3을 의미한다. 네트워크 플로우가 성립하기 위해서는 3가지 조건을 만족해야만 하는데, * c(u,v) : capacity의 약자, u에서 v로 가..
[REFERENCE] https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html 1. DFS (깊이 우선 탐색) 루트 노드에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법 ex) 미로 탐색 : 한 방향으로 갈 수 있을 떄까지 계속 가다가 길이 막히면, 가장 가까운 갈림길로 돌아와서 다시 다른 방향을 탐색 모든 노드를 방문하고자 하는 경우 DFS를 사용하여 해결한다. 넓게 탐색하기(BFS) 전에, 깊게 탐색하는 방법 검색속도는 BFS보다 느리지만, 좀 더 간단하다. 2. DFS 특징 - 자기 자신을 호출하는 순환 알고리즘의 형태 - 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다 - 알고리즘을 구현할 때 가장 큰..
1. 해시 함수 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 해시 함수에 의해 얻어지는 값은 해시값, 해시 코드, 또는 간단하게 해시라고 한다 매우 빠른 데이터 검색을 위해 널리 사용되고, 암호학에서도 사용될 수 있다 데이터의 값을 이용해 저장하고, 찾을 수 있다 2. Direct Addressing Table Direct Addressing Table은 key-value쌍의 데이터를 배열에 저장할, key값을 직접적으로 배열의 인덱스로 사용하는 방법 (ex. 키 값이 100인 데이터가 있다면, 이는 배열 인덱스가 100인 위치에 key값을 저장하고 뒤에 데이터를 연결) 찾고자 하는 데이터의 key만 알고있으면 즉시 위치를 찾는 것이 가능하므로 탐색, 저장, 삭제 모두 선형시간 3. Ha..
1. 정의 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다 2. 원리 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 각 하위 문제를 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단히 해결 ->계산 횟수 감소 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아냄 3. 예시1 : 피보나치 수열 1 2 3 4 5 6 int fibo(int n){ if(n
아니, 추석인데 과제있는거 진짜냐고.... 아오 ------------------------------------------------------- 1. 재귀 recursion : 자기 자신을 재참조하는 것 2. 여러가지 예제들 : 항상 탈출 조건이 있어야하며, 그렇지 않으면 무한 루프를 돌게 된다. 동적계획법에도 사용할 수 있다. (동적계획법은 다음 포스팅) -factorial 1 2 3 4 5 6 7 unsigned int factorial(unsigned int n) { if (n 3을 입력), n 출력 : n번째 숫자 *재귀는 항상 너무 복잡하게 생각하지 말 것 *물론 복잡하게 생각해야 할 때도 있지만, 결국은 컴퓨터에서 알아서 계산을 해 줄 것이기에, 탈출조건과 식만 생각하자 탈출조건 : 입력이..
