코딩테스트 준비 (32) 썸네일형 리스트형 [백준 11401][C++] 이항 계수 3 문제 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 이 문제는 중요 포인트가 두 가지 있었다. (1) 분할 정복으로 연산 시간 감소 POW연산을 수행할 때 지수가 최대 4000000까지 입력이 가능하다. 따라서 일반적인 연산으로는 시간 초과가 발생한다. 이를 두배로 적용시켜 분할 정복하는 power 함수를 만들어 해결한다. 2^22 = 4194304의 값을 가진다. 하나씩 곱셈하는 식으로 power 연산을 구현하면 최대 4000000번 수행해야 하는 연산.. [백준 12865][C++] 평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 과정 이 문제는 다이나믹 프로그래밍하면 가장 대표적인 가방에 무게와 가치가 있는 물건을 최대 가치가 되도록 담는 문제이다. 다이나믹 프로그래밍의 핵심이라고 한다면 이전의 계산을 통해 중복되는 계산을 피하는 것에 있다. 이는 분할 정복과 느낌이 비슷하다. N개의 입력에 의해 발생할 수 있는 가짓수는 2^N 가지이다. DP는.. [백준 23291][C++] 어항 정리 문제 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 과정 해당 문제는 풀이에 실패했다. 따라서 해당 문제에 대한 다른 사람들의 코드를 둘러보게 되었다. 그중 정말 깔끔하고 잘 구현되었다고 생각되는 포스팅의 코드를 살펴보는 식으로 글을 진행할 것이다. https://kimjingo.tistory.com/111 [백준 23291번] 어항 정리(C++ 풀이) https://www.acmicpc.net/problem/23291 23291번: 어.. [백준 23290][C++] 마법사 상어와 복제 문제 https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 과정 1. 현재 저장되어 있는 물고기들의 상태를 복사한다. (이후 모든 과정을 수행 후 fish_map에 추가) 2. 물고기들을 조건에 맞게 이동시킨다. 3. 상어의 이동할 경로를 DFS를 통해 찾은 후, 이동시킨 상태를 fish_map에 반영한다. 4. 물고기를 먹은 흔적인 냄새를 감소시킨다. 5. 복사했던 물고기들을 fish_map에 추가한다. 6... [백준 21611][C++] 마법사 상어와 블리자드 문제 https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 과정 1. 중간을 기준으로 달팽이 모양으로 좌표를 미리 벡터에 저장해놓는다. 이후의 탐색은 해당 벡터를 이용한다. 2. d와 s를 이용하여 블리자드를 통해 구슬을 파괴한다. 3. 칸에 빈칸이 존재하면 앞으로 당겨온다. 4. 같은 칸이 4칸 이상 지속되면 폭발시킨다. (폭발 후 빈칸이 발생하면 3번 함수를 이용한다) 5. 더 이상의 폭발이 없다면 달팽이 모양으로 탐색하며.. [백준 21610][C++] 마법사 상어와 비바라기 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 풀이 과정 1. 구름을 이동시키는 함수 구현 (이동 후 좌표 설정 방법은 마법사 상어와 파이어볼 문제와 동일 [문제] [풀이 및 소스코드]) 2. 구름 위치에 물의 양을 늘리는 함수 구현 (이후 구름이 사라진다고 했지만, 구름 위치 정보 보존해야 한다) 3. 물의 양이 증가한 각 칸에 대해서 대각선을 탐색하고 그 수만큼 칸의 물을 증가시키는 함수 구현 4. 새로운 구름을 만드는 함수 .. [백준 21609][C++] 상어 중학교 문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 과정 1. 회전 함수 구현 2. 중력 함수 구현 3. 탐색을 통해 가장 큰 블록을 찾는 함수 구현 블록 수 같은 경우 무지개 블록 확인 무지개 블록 수 같으면 기준 블록 확인 4. 블록 찾아서 제거, 중력, 회전, 중력 순으로 수행되는 하나의 사이클 생성 5. 만약 찾은 최대 블록의 수가 1개 이하라면 그룹이 없는 것이므로 종료하며 현재까지 점수의 합 출력 세부 풀이 (1) rota.. [백준 21608][C++] 상어 초등학교 문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 과정 1. 주변을 탐색해서 인접한 칸의 좋아하는 학생의 수를 반환하는 함수 구현 2. 주변을 탐색해서 인접한 칸의 빈칸의 수를 반환하는 함수 구현 3. 1을 이용하여 좋아하는 학생의 수가 같은 경우가 여러 개 있다면 2를 수행하여 학생의 위치를 정한다. 4. 위의 함수를 이용하여 학생들의 자리를 모두 배치한다. 5. 배치가 완료된 상태에서의 각 학생들의 만족도를 구하여 출력한.. 이전 1 2 3 4 다음
