Study with book/Algorithms
[백준]동전 0
백준저지 [동전 0]https://www.acmicpc.net/problem/11047 • 그리디 알고리즘을 요구하는 문제 • 핵심은 큰 금액부터 작은 금액으로 내려가면서 동전의 개수를 구해야 한다. • 푸는데 걸린 시간은 약 10분 정도 걸렸다. #include <iostream> using namespace std; int val[11]; int main(void) { int N, K, ans = 0, sum = 0; cin >> N >> K; for (int i = 1; i > val[i]; for (int i = N; i >= 1; i--) { if (val[i] < K) { while (sum
[백준]피보나치 함수
백준저지 [피보나치 함수]https://www.acmicpc.net/problem/1003 • 5분만에 푼문제이다. 왜 정답률이 39%인지 모르겠다. • 그냥 주어진 문제를 그대로 코딩하면 끝... #include using namespace std; int ansZ, ansO; int fib(int n) { if (n == 0) { ansZ++; return 0; } else if (n == 1) { ansO++; return 0; } else return fib(n - 1) + fib(n - 2); } int main(void) { int cnt; cin >> cnt; for (int i = 0; i > in; fib(in); cout
[백준]K번째 수
백준저지 [K번째 수]https://www.acmicpc.net/problem/11004 • C++의 algorithm STL에 있는 nth_element()함수를 이용해서 문제를 풀었다. • nth_element()는 k번째 수까지 정렬을 하는 좋은 함수이다. • 시간도 메모리도 상대적으로 많이 썼다. • 시간이 되면 nth_element함수를 구현해 볼 생각이다. #include #include #include using namespace std; int main(void) { int N, K; scanf("%d%d", &N, &K); vector vecArr(N, 0); for (int i = 0; i < N; i++) { long long int in; scanf("%lld", &in); vecA..
[백준]이진탐색트리
백준저지 [이진탐색트리]https://www.acmicpc.net/problem/2957 • 필자에 너무 어려웠던 문제이다. 이 문제를 풀기위해 3주를 고민했다. • 어렵게 풀었던 만큼 이진탐색트리의 삽입, 삭제, 탐색은 확실하게 이해도가 많이 올라간 것 같아 기분이 좋다. • 추가적으로 Map이란 STL사용법도 확실히 많이 익숙해진 듯하다. [풀이] • 기본적으로 이진탐색트리의 삽입의 성질과 위 문제의 의도를 정확하게 이해해야 풀 수 있는 문제이다. → root의 값보다 크면 오른쪽, root의 값보다 작으면 왼쪽 • 아마 처음 접근은 위 문제에서 수도코드로 짜여있는 예시대로 구현을 했을 것이다. • 필자도 저 예시대로 재귀로 구현해도 해보고 반복으로 구현도 해보고 배열을 30만개 만들어서도 해보고....
[백준]트리
백준저지 [트리]https://www.acmicpc.net/problem/1068 • 문제를 푸는데 30분정도 걸렸다. • 두 번 실패를 하였다. → 원인은 노드의 삭제가 재귀적인 성향을 가지고 있다는 것을 늦게 발견하였음 → 즉, 삭제하려고 하는 노드를 포함한 자손까지 전부 삭제를 해주어야 됨 → 일차원적으로 삭제하려고 하는 노드의 자식만 삭제하여 계속 실패를 하였음 [풀이] • 삭제에 유용한 list STL을 사용하여 트리를 구성하였음(리스트 배열 51개를 생성) • 입력 값들 중 두 번째 줄에서 부모 노드가 없는 경우는 루트 노드이기 때문에 따로 –1처리를 해주지 않았음 • 두 번째 줄에서 부모 노드를 입력 받기 때문에 listArr[51]의 인덱스를 노드의 번호로 간주, 인덱스르 이용해서 트리 그..
[백준]힙 정렬
백준저지[힙 정렬]https://www.acmicpc.net/problem/2220 • 힙 자료구조 삭제에 대한 이해도를 가지고• 백준에서 제시된 예시 (5, 4, 3, 2, 1)과 (6, 5, 3, 2, 4, 1)에 대해 삭제를 펜으로 몇 번 해보았는데• 규칙이 금방 발견되었다.• 동적 알고리즘의 냄새가 물씬 나서 혹시나 하는 생각에 (2 ~ 1)과 (3 ~ 1)부터 (6 ~ 1)까지 힙을 그려 봤는데 동적 알고리즘이었다. [구현]• 먼저 첫 번째 규칙은 최댓값을 삭제 했을 때, 무조건 전 값의 힙 모양이 나온다는 것이었다.• 예를 들어 (6, 5, 3, 2, 4, 1)에서 6을 삭제하게 되면 무조건 5일 때 최대로 swap이 되는 모양의 힙이 나온다는 것이다. 즉, (5, 4, 3, 2, 1)이 된다..
[백준]2xn 타일링2
백준저지 [2xn 타일링2]https://www.acmicpc.net/problem/11727 • 이전 2xn타일링 포스팅과 마찬가지로 DP문제이다. • 개인적으로 이번 문제는 점화식이 제대로 안나와서 다소 많은 시간을 투자했다. • 이번 문제를 통해 DP를 빠르게 풀기 위해서는 눈썰미가 좋거나... • 많은 경험과 공부를 하거나... • 필자는 본 문제를 노가다(?)를 통해서 성공 메세지를 노출시키는데 성공했다. • 더 나은 방법이 있다면 댓글로 알려줬으면 한다. • 추가적으로 DP에 대해 더 심도있게 공부를 해보고 다른 방법이 있다면 본 포스팅에 추가해서 • 해결방법을 포스팅하도록 하겠다. (cf. 고등학교때 수학좀 열심히 할껄...) an = an-1 + 2xan-2(a1=1, a2=3) #incl..
[백준]2xn 타일링
백준저지 [2xn 타일링]https://www.acmicpc.net/problem/11726 • 다이나믹 프로그래밍(=동적 계획법, DP)으로 분류되는 문제이다. • DP는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 방법이다. • 위 문제를 필자는 노가다(?)로 작업을 해보았다. 그리고 다음과 같은 규칙을 얻을 수 있었는데 • 바로 피보나치 수열의 점화식을 얻을 수 있었다. an = an-1 + an-2(a1=1, a2=2)• 아래는 구현 코드인데 쉽게 구할 수 있었다. #include <iostream> using namespace std; int main(void) { int result[1001] = { 0, }; int num; cin ..
[백준]순열 사이클
백준저지 [순열 사이클]https://www.acmicpc.net/problem/10451 • 이 문제는 몇 개의 사이클이 존재하는지를 출력해야 한다. • 문제 이해는 쉽게 되었고 시간도 얼마 걸리지 않았다. • 구현 - 먼저 입력 받은 정점의 개수 + 1만큼 int형 vector타입 vec변수와 - 방문 여부를 나타내는 visitArr배열을 선언했다. (index와 값을 맞추기 위함) - j는 index를 나타내고 vec[j]는 정점에 연결된 다른 정점을 뜻함 - 21 line: 정점의 개수만큼 반복한다. - 22 line: 선택된 정점이 방문되지 않았다면, - 23 line: visit 변수를 선택된 정점(j)으로 초기화하고 - 24 line: 아래 내용을 반복하는데, - 25 line: 선택된 정점..
[백준]DFS와 BFS3
백준저지 [DFS와 BFS]https://www.acmicpc.net/problem/1260 전체 코드를 포스팅하려고 한다. 이전 포스팅에서 DSF와 BSF에 대한 코드를 공개했었는데 그래서 사실 이번 포스팅은 필요없는 부분일지도 모르지만... 힘들게 고민해서 짠것이니...!! 삶을 살아가면서 최고의 순간만 쟁취할 수는 없다. 신중하게 결정하고 생각한다고 해도 당신이 고른 영화가 항상 재밌을 거라는 보장은 없다. 평점을 보고 리뷰를 보고 다른 사람들이 별 다섯 개를 던지며 재밌다고 하는 영화가 당신에게는 별 감흥 없는 영상으로 다가올 수도 있으며, 많은 사람들이 볼 가치도 없는 최악이라고 말하는 영화가 당신의 가슴 깊숙한 부분을 울릴 수도 있다. 아무리 당신이 실패를 예방하기 위해 조심스럽게 산다고 해도..