한다 공부

탐욕 알고리즘이라고 불리는 그리디 알고리즘이란 무엇일까? 그리디 알고리즘이란, 지금 상황에서의 최선의 선택이 곧 정답이라는 알고리즘이다. 시간적으로 효율적이지만, 매번 그리디로 푼 풀이가 정답이 아닐 수도 있다!! 그리디 알고리즘을 사용하려면 현재 최선의 선택이 전체 문제의 정답이어야한다. 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이 되면 작은 값인 ..

10814번: 나이순 정렬 (acmicpc.net) 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두가지 값을 저장하는 것이므로 pair를 이용하면 된다. 단, 첫 번째 값인 나이순으로 정렬하되 두 번째 값인 이름은 입력 순서를 유지해야한다. #include 안에 있는 sort 함수를 써서 정렬을 했다 계속 틀렸습니다가 떠서 당황했는데, 알아본 결과 sort의 경우 비교하는 값이 같을 경우에 원래 순서를 유지한다는 보장이 없다고 한다. 다시 말해 sort로 정렬하면 나이가 같은 사람들은 정렬 순서가 원래와 다르게 ..

10816번: 숫자 카드 2 (acmicpc.net) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net (이분 탐색) 지난 포스팅 을 통해 이분 탐색을 공부했다. 이번엔 직접 구현을 해보았다. 우선 해당 문제는 내가 원하는 카드가 몇 장 있는지 탐색해야하는 문제인데, 어떻게 구할까? 이 문제에서는 upperBound 와 lowerBound 에 대해 알아야한다. [ 1 2 2 2 3 ] 라는 배열이 있다고 했을 때, 2를 찾는다고 가정해보자. lowerBound는 내가 찾는 카드의..

1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다. 이러한 이분 탐색은 실생활에서도 많이 쓰인다. 최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다. 1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다. 이 방법이 이분 탐색이다. C++에서는 #include을 통해..

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

12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 문제를 풀어보았다. 이 문제에서는, 들 수 있는 배낭의 최대 무게가 주어진다. 그리고 물건의 무게와 물건의 최대 가치가 주어지는데, 배낭에 넣을 수 있는 물건의 최대 가치값을 구하는 문제이다. 동적 계획법을 이용해 냅색 문제를 해결해보자. 우선 dp의 인덱스를 무게로 나타내자 예를 들어 배낭에 넣을 수 있는 최대 무게가 7Kg 이라고 하자. ..