🥇 Problem Solving

[Python] BOJ / 2096번/ 내려가기

2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 📝 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. ..

[Python] BOJ / 2812번 / 크게 만들기

2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 📝 풀이 N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램 전체 자릿수에 대해서 아래 과정을 반복한다 스택에 i번째 자릿수 값을 저장 숫자 제거 횟수가 남아 있고(del_cnt > 0) 스택에 저장되어 있는 원소가 있는 경우 스택의 끝 수와 i번째 수를 비교하여 i번째 수보다 작은 스택의 끝 수를 제거하고 숫자 제거 횟수를 갱신시킴 결과를 출력할 때에는 스택에 담겨있는 수를 전체 자릿수에서 제거할 횟수를 뺀 만큼 순서대로 출력 💻 소스코드 import sys input = sys.stdin.rea..

[Python] BOJ / 3020번 / 개똥벌레

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 📝 풀이 장애물(석순과 종유석)로 가득찬 동굴을 개똥벌레가 통과하고자 할 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 총 개수를 구하는 프로그램 이분 탐색 알고리즘을 통해 각각의 장애물(석순과 종유석)과 높이에 따라 파괴해야 하는 장애물의 첫 번째 인덱스를 구한 뒤 해당 인덱스를 통해 파괴해야 하는 장애물의 수를 구할 수 있음 석순(down)을 파괴하는 경우는 개똥벌레가 날아가는 높이(target)를 (i - 0.5)로 설정하여 구할 수 있으며 종..

[Python] BOJ / 17609번 / 회문

17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 📝 풀이 문자열이 주어졌을 때 회문인지, 유사 회문인지, 일반 문자열인지 구분하여 출력하는 프로그램 문자열의 처음(left = 0)과 끝(right = len(word) - 1)에 포인터를 두고 대치되는 위치의 두 문자를 비교해 감 1. 대치되는 두 문자가 동일한 경우 왼쪽 포인터(left)는 +1을, 오른쪽 포인터(right)는 -1을 하여 다음 문자 비교 2. 대치되는 두 문자가 동일하지 않은 경우 왼쪽 문자 혹은 오른쪽 문자를 제거했을 때 회문이 되는지 확인 이 과정에서 회문이 된다면 유..