문제 노트/정올 (49) 썸네일형 리스트형 막대기( BOJ 17608 ) 문제 : https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 문제 파악하기 막대기를 일렬로 세운 후 오른쪽에서 바라보았을 때, 보이는 막대기의 개수를 출력하는 문제입니다. 오른쪽에서 보인다는 의미는 막대기의 높이가 오른쪽부터 순차적으로 증가해야 한다는 걸 말하며, 보이는 막대기의 총 개수를 구하기 위해서는 오른쪽부터 탐색을 시작하면 됩니다. 문제 해결하기 막대기가 보인다는 건 기존 가장 높았던 막대기보다 좀 더 크다는 의미입니다. 따라서, 지금까지 가장.. 369( BOJ 17614 ) 문제 : https://www.acmicpc.net/problem/17614 17614번: 369 민수는 같은 반 친구들과 369게임을 하고 있다. 369게임은 여러 명이 원형으로 둘러 앉아 시작 위치의 사람이 1을 외치며 시작된다. 이후 시계방향으로 돌아가며 2, 3, 4와 같이 1씩 증가된 수가 자 www.acmicpc.net 문제 파악하기 1부터 시작해서 N까지 369 게임이 진행되었을 때, 나오는 모든 박수의 수를 구하는 전형적인 문제입니다. N의 범위가 최대 106이기 때문에 단순히 반복문을 사용하면 문제를 해결할 수 있습니다. 문제 해결하기 369 게임은 숫자에 3, 6, 9가 포함된 개수만큼 박수를 쳐야 하는 게임입니다. 따라서, 1부터 N까지 숫자를 모두 확인하면서 범위 내 숫자 i에 3,.. 회문( BOJ 17609 ) 문제 : https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 파악하기 주어진 문자열이 회문인지, 아니면 유사회문인지, 아니면 일반 문자열인지 확인하는 문제입니다. 해당 문자가 회문인 판단은 반복문으로 간단하게 할 수 있지만, 유사회문인지 확인하기 위해서는 별도의 알고리즘이 필요합니다. 저는 여기서 브루트포스 알고리즘을 활용했습니다. 문제 해결하기 우선 유사회문인지 판단하는 가장 간단한 알고리즘은 문자열 속 문자를 하나씩 제거하고 확인하는 방법이 있습니다. 이 방법은 정확하.. 박 터뜨리기( BOJ 19939 ) 문제 : https://www.acmicpc.net/problem/19939 19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 문제 파악하기 N개의 공을 조건에 맞게 K개의 바구니에 넣었을 때, { 가장 공이 많은 바구니 - 가장 공이 적은 바구니 }의 최솟값을 구하는 문제입니다. 조건은 까다롭지 않습니다. N개의 공이 모두 들어가야하고, K개의 바구니에는 적어도 1개 이상의 공이 들어가야 하며, 어느 바구니에도 동일한 개수의 공이 들어갈 수 없습니다. 3가지 조건을 만족하는 여러 가지 경우 중 공이 가.. 피자 오븐( BOJ 19940 ) 문제 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최 www.acmicpc.net 문제 파악하기 전자 오븐의 버튼을 최소로 누르는 방법을 출력하는 문제입니다. 버튼은 총 5개가 있으며, 각각의 경우에 따라 누르는 방법을 달리 해야하기 때문에 최적의 조건을 떠올려야 하는 문제입니다. 문제 해결하기 전자 오븐의 버튼은 총 5개 있습니다. 그 중에서 가장 무식하게 사용하기 쉬은 버튼은 바로 ADDH(t+60) 입니다. 60분 만큼 증가시키는 방법은.. 수 고르기( BOJ 20186 ) 문제 : https://www.acmicpc.net/problem/20186 20186번: 수 고르기 첫 번째 줄에 주어진 N개의 수 중 K개의 수를 고를 때, 전체점수의 최댓값을 출력한다. www.acmicpc.net 문제 파악하기 적절하게 K개의 숫자를 선택하여 얻을 수 있는 점수의 최댓값을 구하는 문제입니다. 점수는 선택한 K개의 숫자에서 얻을 수 있으며, 현재 숫자를 기준으로 왼쪽에 있는 숫자 중 선택된 수의 개수를 현재 숫자에서 뺀 값을 의미합니다. 어떻게 하면 점수를 최대로 만들 수 있을까요? 확인하는 방법은 여러가지 있습니다. 문제 해결하기 가장 떠올리기 쉬운 방법은 모든 경우의 수를 찾아보는 것입니다. 문제를 함수를 사용하여 상태로 추상화하면 우리는 무식하지만 확실하게 모든 경우의 수를 확.. 종이접기( BOJ 20187 ) 문제 : https://www.acmicpc.net/problem/20187 20187번: 종이접기 접힌 종이를 접은 순서의 역순으로 펼친 후 정사각형에 뚫린 구멍의 위치를 번호로 출력한다. 출력은 총 2k줄로 이루어지며 i (1 ≤ i ≤ 2k)번째 줄에는 격자의 i번 행에 뚫린 구멍의 번호를 왼쪽 www.acmicpc.net 문제 파악하기 2N*2N 크기의 종이를 접은 다음 모서리 부근에 구멍을 하나 뚫었을 때, 구멍이 뚫리는 모든 위치를 출력하는 문제입니다. 항상 가로, 세로 각각 K번씩 접는다고 명시했기 때문에 종료 조건을 따로 설정할 필요가 없으며, 예외 사항을 생각하지 않아도 됩니다. 이 문제는 현재 종이의 모습을 적절하게 추상화한 다음, 종이가 접힌 역순으로 시뮬레이션하면 문제를 해결할 수 .. 금광( BOJ 10167 ) 문제 : https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 문제 파악하기 x축과 y축에 평행한 직사각형 모양의 땅(R)에서 얻을 수 있는 최대 개발 이익을 구하는 문제입니다. R의 크기는 원하는 만큼 조정할 수 있으며, R의 범위 안에 있는 금광의 이익/손해를 모두 더한 값인 개발 이익이 될 수 있는 최댓값을 구해야 합니다. 금광의 위치가 1차원으로 이루어진 경우에는 1차원 배열을 이용한 연속된 구간의 최대합을 .. 이전 1 2 3 4 5 6 7 다음
