https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1. Logic 4등분을 해서 모든 칸이 일치하면 해당 칸의 번호를 출력하는 문제이다. 기본적인 분할 정복 문제이지만 출력을 할 때 한번 생각해야 되서 실버 1인듯?하다 기본적인 분할 정복 아이디어를 활용하여 풀이하면 되고, 출력은 분할하는 부분에서 즉 섞여있는 부분을 확인하려고 재귀를 들어갈 때 '('를 출력하고 들어가서 확인하고 나오면서 ')'를 출력해주면 된다. 2. Code #..
알고리즘
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 재귀를 이해하고 있다면 쉽게 풀 수 있는 문제이다. 각 노드의 부모 노드를 순서대로 출력해야 하기 때문에 부모 노드를 저장하는 배열(check)에 저장해줬다. 양방향으로 입력을 받았기 때문에 반복되는 계산을 막아주기 위해 vis배열도 추가해줬다. 수정 > 원래는 vis배열에 넣어줬지만 check배열을 -1로 초기화 시켜준 다음 -1이 아니면 continue하도록 설계해주면 100001개짜리 배열 하나를 덜 써도 된다 2. Code #includ..
https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. Logic 조건 그대로 구현하면 된다. 구현이 약간 까다롭지만 계란의 수 N의 크기가 8로 엄청 작기 때문에 브루트포스로 풀이할 수 있다는 것을 유추할 수 있다. 구조체를 사용하지 않고 내구도와 무게를 따로 저장하는 배열을 선언하여 풀이했다. 2. Code #include #include using namespace std; int n; int dura[10]; int weig..
https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 재귀로 들어가서 0이 되면 경우의 수 1을 count해준다. 다만 숫자가 크기 때문에 타입을 long long 으로 해줬다. 2. Code #include #include using namespace std; long long dp[1000001]; long long solve(long long n) { if(n == 0) return 1; else if(n < 0) return 0; long long &ret = dp[n]; if..
https://www.acmicpc.net/problem/11653 1. Code #include using namespace std; int main() { int n; cin >> n; if (n == 1) return 0; for (int i = 2; i
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1. Logic dp배열이 의미하는 것은 배열에 해당하는 카드를 구매할때의 최댓값이다. dp[구매하는 카드 갯수] = 최댓값. 최댓값을 구하는 방법은 1개짜리 팩 + 카드 3개를 구매하는데 필요한 최댓값 2개짜리 팩 + 카드 2개를 구매하는데 필요한 최댓값 3개짜리 팩 + 카드 1개를 구매하는데 필요한 최댓값 4개짜리 팩 이렇게 경우의 수를 나눠볼 수 있다. 2. Code #include #include..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1. Logic 전체 인원의 반을 나눠서 팀을 구성하기 때문에 기저조건을 N/2로 설정한 후 DFS를 진행한다. N/2까지 갔을 때 전체인원의 반은 check배열에 true로 표시되어있고 반은 false로 표시되어 있을 것이다. true로 선택된 번호는 스타트 팀에 배정을 하고 false인 인원은 링크 팀에 배정을 하여 DFS를 돌며 최소값을 구한다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. Logic 부분문제를 3가지로 나눌 수 있다. 포도주를 안마시는 경우 포도주를 1잔 연속해서 마시느 경우 포도주를 2잔 연속해서 마시는 경우 그래서 DP테이블을 정할 때 DP[현재 인덱스][선택 여부] 로 정의했다. 선택 여부 별 의미하는 바는 > 0:이전에 포도주 안마심, 1:이전에 한잔만 마심, 2:이전에 두잔 연속해서 마심 입력으로 받은 첫번째 수에서 선택할지 말지여부를 처리하는 것은, ..
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1. Logic 단순 다익스트라에 간단한 후처리를 요구하는 문제이다. 다익스트라로 첫 해킹을 당한 컴퓨터부터 시작해서 감염을 시키고 다익스트라 이후 dist배열 전체를 순회하여 INF가 아닌 배열들의 갯수를 세주면 감염되는 컴퓨터 수를 구할 수 있고 걸리는 시간은 전체 배열을 순회하며 가장 큰 배열의 값을 구하면 된다. 2. Code #include using namespace std; const i..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 1. Logic 불의 위치를 담은 queue fire과 지훈이의 위치를 담은 jihun queue 두개를 가지고 풀이했다. 불이 위치한 곳은 애초에 지훈이가 가지 못하고 지훈이가 움직이더라도 불이 오면 안되기 때문에 불을 먼저 BFS를 돌려 움직여줬다. 이후 불이 없는곳에 지훈이를 BFS를 돌려 움직여주면 불이 있는곳을 제외하고 대피할 수 있다. 처음에는 queue 4개를 사용하여..
