검은도화지

문제 Chapter 04 구현 中 4-2. 시각 난이도 ★☆☆, 풀이시간 15분, 시간제한 2초, 메모리 제한 128MB 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오, 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다. 00시 02분 55초 01시 27분 45초 입력조건 첫째 줄에 정수 N이 입력된다, (0

구현이란? 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 모든 문제에서 이 과정은 필수적이지만, 현재 설명하고자 하는 문제 유형은 특히 위의 명제부분이 까다로운 문제, 즉 '풀이를 떠올리는 것은 쉬우나 소스코드로 옮기기 어려운 문제'를 뜻한다. 현재 가장 취약한 부분이기도 하다. 위에 해당되는 문제는 크게 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제이거나 특정 소수점 자리까지 출력해야하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제 등이 있다. 구현 시 고려해야 할 메모리 제약 사항 변수의 표현 범위 전통적인 프로그래밍 언어에서 정수형을 표현할 때 int형의 4바이트 자료형을 사용한다. 이의 표현 범..

교재: 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈 지음) Chapter 03. 그리디 中 1이 될 때까지 난이도 ★☆☆ 문제 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N에서 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 가정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을..

교재: 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈 지음) Chapter 03. 그리디 中 숫자 카드 게임 난이도 ★☆☆ 문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록..

교재: 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈 지음) Chapter 03. 그리디 中 큰 수의 법칙 난이도 ★☆☆ 문제 '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+..

어느날 solved.ac를 확인하다가 안 사실, 문제의 분류가 있었다는 것! 당시 낮은 티어 별로 문제를 풀었기에 문제의 유형을 생각해 볼 겨를이 없었다. 되짚어보면 브론즈 그리드 알고리즘은 문제를 한 번에 파악하기 힘들었다는 특징이 있었다는 것이 기억난다. 확률처럼, 문제를 푸는 방법이 여러가지지만 그 중에서 가장 최적의 방식을 골라야 시간을 단축할 수 있었기 때문이다. 방금 '알고리즘의 기본 아니냐'는 생각이 들었다면, 지금부터 이 알고리즘이 어떤 것인지 알아가보자. 그리디 알고리즘이란? 탐욕법이라고도 소개되는 이것은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'으로, 각 단계에서 가장 최선의 선택을 하는 기법이다. 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은, 즉 문제 출제의 폭이 넓..