한다 공부

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 이라고 하자. ..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 동적 계획법 (dynamic programming) 이란 무엇일까? 바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다. 예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자. 왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다. 출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 ..

15649번: N과 M (1) (acmicpc.net) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이란? 브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다. 백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다. 백트래킹은 주로 N의 값이 20보다 작을 때 이용한다. 위 N과 M (1)의 문제를 예로 들어보자. n=4, m=..

16563번: 어려운 소인수분해 (acmicpc.net) 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 일반 에라토스테네스의 체는 bool 배열을 만들어서 소수면 true, 아니면 false를 저장한다. 그런데 이 문제에서는 소인수들을 찾아야하므로 bool 배열 대신 int 배열을 만들어서, 어떤 수로 인해 소수가 아니게 되었는지를 저장한다. 예를 들어 8의 경우, 8은 2의 곱으로 인해 소수가 아니게 되었다. >> 2 출력 8/prime[k] = 8/2 =4 가 된다. 4는 2의 곱으로 인해 소수가 아니게 되었다..

2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 유클리드 호제법을 이용했다. 최대공약수를 G, 최소공배수 L이라 하자 G*L = A*B 이다. (수학적 공식이라고 한다.) A = G*a, B=G*a이라고 하면 (이때 a, b는 서로소이다. 왜냐하면 최대공약수 G로 공통부분을 끄집어 냈으므로) G*L = G*a*G*b가 되고 약분하면 L/G=a*b가 된다. L G가 주어지니 이를 이용해서 A+B, 즉 a+b가 최소가 되는 a b를 찾고 a b에 G를 구해 최종적으로 ..

5639번: 이진 검색 트리 (acmicpc.net) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 예전에 올린 이진 탐색 트리 코드를 일부 수정했다. c언어로 구현했던 것을 c++로 구현하니 신경써야하는 부분이 있었다. 엔터 입력시 입력을 종료해야하는 부분이 까다로웠다. 그래서 getline을 이용해 문자열로 받은 다음, stoi를 이용해 문자열을 정수로 변환했고 엔터 입력시 반복문을 빠져나오게 했다. 4358번 생태학 문제를 풀 때 비슷한 방법을 이용했다. #include #include #..

https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 삼각형 만들기 삼각형을 만드는 조건 : 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작으면 된다. a < b < c 일 때 c < a+b 이면 성립한다. 최대 길이의 삼각형을 만들면 되므로 가장 큰 길이인 빨대 3개를 골라주면 된다. 삼각형이 만들어지지 않을 수도 있다. 그러면 가장 큰 길이인 빨대를 버리고 나머지 중에 제일 큰 3개의 빨대를 골라서 비교해보면 된다...