프로그래밍나무

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방법 해당 문제는 그리디 알고리즘을 이용해 풀 수 있습니다. 보석의 최대 가격을 구하기 위해서는 각각의 가방에 넣을 수 있는 보석 중 최대 가격을 가진 보석을 넣어야 합니다. 결국, 각 가방에 담을 수 있는 최대 무게보다 작은 보석 중에서 제일 큰 가격을 가지고 있는 보석을 선택하면 됩니다. 하지만 보석을 넣을 때는 최대 무게가 작..

www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 접근방법 여러 가지 방법 중에 제일 쉬운 방법은 x좌표와 y좌표를 분리해서 생각하는 것이다. x좌표와 y좌표는 증가하다가 경계면에 부딪히면 감소하고, 감소하다가 경계면에 부딪히면 증가한다. 증감을 반복하는 것을 어떻게 구현해야 할까? 먼저 시작좌표 p에서 t를 더하게 되면 경계면이 없을 때 개미가 총 움직인 거리가 나온다. testcase같이 p가 4이고 t가 8일 때 경계면이 없다면 개미의 ..

접근방법 기본적인 접근방법 Prim 알고리즘을 이용한 인접 행렬 각 노드로 연결되는 최소 거리를 minEdge 배열로 생성한 후 값을 무한대로 초기화한다. 0번 노드에서 시작해서 연결할 수 있는 모든 노드들의 거리를 계산해서 minEdge를 갱신한다. 갱신한 값 중에서 제일 작은 노드를 고른 다음 반복한다. 이런 순서로 알고리즘이 진행되게 된다. 이 방법의 경우 시간 복잡도는 V^2이 된다. 추가적인 접근방법 Prim 알고리즘을 이용한 인접 행렬 + PriorityQueue PriorityQueue를 쓰지 않은 방법과 다른 것은 minEdge를 갱신할 때 PriorityQueue의 offer( ) 하는 것과 제일 작은 노드를 구할 때는 PriorityQueue의 poll( )을 한다는 것이다. 이 방법의..

접근방법 기본적인 접근방법 큐를 사용한다. 추가적인 접근방법 규칙을 찾는다. 기본적인 접근방식도 있지만 이 문제의 규칙을 찾아서 연산 횟수를 줄이는 방식을 쓴다. 모든 감소시키는 수는 1, 2, 3, 4, 5를 반복하게 된다. 그리고 암호는 8개의 숫자로 이루어져 있다. 첫 번째 수 두 번째 수 세 번째 수 네 번째 수 다섯 번째 수 여섯 번째 수 일곱 번째 수 여덟 번째 수 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 -1 -2 -3 -4 -5 ... 이해를 돕기 위해서 수를 맨 뒤로 보내지 않고 감소시키는 수를 계속 적어보았다. 표를..

접근방법 동전을 전부 배열에 넣어놓고 하나씩 꺼내면서 전체 배열을 갱신한다. 배열을 갱신할 때 해당 동전의 크기만큼의 앞의 원소를 해당 원소에 더한다. 예를 들어, 동전의 크기가 2일 때 a[i]=a[i]+a[i-2] 왜냐하면 동전의 크기가 2이면 i=2일 때는 동전 하나로 나타낼 수 있지만 i=4일 때는 동전 두 개로 나타내야 하기 때문이다. 코드 #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n, k; int coin[101], arr[10001] = { 0, }; cin >> n >> k; for (int i = 0; i > coin[i]; for ..

www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 접근방법 백트래킹 문제이다. 다른 백트래킹 문제와 조금 다르게 하나의 답만 요구하므로 전체를 다 탐색할 필요가 없다. 또한 전체를 탐색하면서 값을 계속 변경할 경우 잘못된 값이 답에 들어갈 수 있다. 그러므로 빈 공간을 다 채워주는 해를 발견할 경우 바로 출력해야 한다. 코드 #include #include #include using namespace std; void DFS(int num); void Prom..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 접근방법 최빈값 같은 경우 정수의 절댓값이 4000을 넘지 않으므로 8001개의 원소를 가지는 배열을 생성 각 숫자가 나올때 +1을 해주었다. 나중에 배열을 검사하면서 제일 큰 원소를 찾고, 지금 있는 최댓값과 같은 원소가 있다면 두 번째까지만 인덱스를 저장한다. 정렬을 직접 구현하였는데 퀵소트로 구현할 경우 제출 시 46~50% 정도에서 많은 시간이 걸리는 것을 확인할 수 있다. 그래서 합병 정렬을 사용해 풀었다.