한다 공부

2294번: 동전 2 (acmicpc.net) 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동적 계획법 문제는 어렵다..... 이 문제는 아래와 같이 풀었다 가치가 1 3인 동전이 있다고 하자 1~6 까지의 가치합을 만든다고 하면 가치 1인 동전을 쓰면 동전의 갯수가 1 2 3 4 5 6 일 것이다. 가치 3인 동전을 쓰면 동전의 갯수는 0 0 1 2 3 1 일 것이다. 가치 1, 3 모두 쓰면 동전의 갯수는 1 2 1 2 3 1 일 것이다. 이는 어떻게 구한 것 이냐면 , ..

13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 7%, 90%에서 멈추는 사람 .... 🖐 ^^ 나밖에 없을듯,.. 0-1 BFS 우선 0-1 BFS란? 최단경로 문제이면서 가중치가 0,1 만 존재할 때 덱을 이용하여 푸는 문제이다. 다익스트라를 사용했을 때 보다 빠르다. 가중치가 두 개인 상태에서 최단경로를 구해야하므로 가중치가 낮은걸 push_front를 하고 가중치가 높은걸 push_back하면 우선순위(짧은 경로)에 따..

알아두면 유용할 것 같아서 정리 C++ 에서 pair를 이용하면 두가지 데이터를 하나의 pair에 저장할 수 있다. 문제를 풀 때, 첫번째 요소는 오름차순으로 정렬을 하고 첫번째 요소가 같은 경우에 두번째 요소는 입력한 그대로 = 즉 두번째 요소는 건드리지 않고 정렬을 하라고 했을 때 어떻게 할까? 난 cmp함수를 만들어서 #include안에 있는 sort함수를 써서 첫번째 요소만 정렬을 했다! 그러면 되는줄.. 그런데 정렬하는 함수에는 불안정한 정렬인 sort와 안정한 정렬인 stable_sort가 있었다. 무슨 뜻인고 하니, 불안정한 정렬인 sort는 위의 경우에서 두번째 요소에 대해 언급이 없을 때, 두번째 요소가 변하지 않는다는 보장이 없다! 안정한 정렬인 stable_sort는 두번째 요소를 건..

이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다. 이러한 이분 탐색은 실생활에서도 많이 쓰인다. 최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다. 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이 되면 작은 값인 ..

의문의 시간 초과와의 싸움 1753을 다익스트라로 푸는데 endl 대신 \n도 썼고 ios::sync_with_stdio(false); cin.tie(NULL); 도 사용을 했고 중복을 방지하기 위해 if(w>dist[v]) //중복을 방지하기 위해 (시간 단축) continue; 도 사용을 했다. 이 부분이 헷갈렸는데 4->5->6 으로 가면 5이고 4->6으로 갈 때 7인 구간이 있다고 해보자 그러면 5을 거쳐 가는게 빠른데 계산을 하다가 4->6으로 가는 7인 구간을 또 거쳐가게 될 수도 있다. 그럴 때 중복을 방지하는 것이다. 당연히 5 만큼에 갈 수 있는 거리인걸 아는데 가중치 7을 가진 간선을 통해 가는 경로는 굳이 탐색해보지 않아도 되는것... 이 부분 때문에 시간 초과가 발생하는 다익스트라..