문제1 : 곱하기 혹은 더하기
- 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하자
단, + 보다 x 를 먼저 계산하는 일반적인 방식과는 달리, "모든 연산은 왼쪽부터 순서대로 이루어진다" 를 가정한다 - 예를 들어 02984 라는 문자열로 만들 수 있는 가장 큰 수는
((((0+2) * 9))*8)* 4) = 576이고, 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.
문제 해결 아이디어
- '+' 보다는 ' * ' 이 값을 더 크게 만듬
- 다만, 두 수중에서 하나라도 0 혹은 1이 나올 경우, 곱하기 보다는 + 연산이 효율적
- 두 수에 대하여 연산을 수행할 때, 두 수중에서 하나라도 1이하 인경우는 더할 것!
해답 (난이도 쉬움)
#입력데이터
data = input()
#첫번쨰 문자부터 시작
result = int(data[0])
for i in range(1, len(data)):
a = int(data[i])
if a <= 1 or result <= 1:
result += a
else:
result *= a
print(result)문제2 : 모험가 길드
- 한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
- 모험가 길드장인 동빈씨는 모험가 그룹을 안전하게 구성하고자 공포도가 X 인 모험가는 반드시 X 명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다
- 즉, 공포도가 높을수록 멤버의 수는 많아져야 된다는 뜻!
- 동빈씨는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금해합니다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성해보자
- 예를 들어 N= 5 이고 각 모험가의 공포도가 다음과 같다고 가정하자
2 3 1 2 2- 이 경우 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있다.
- 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다
문제 해결 아이디어
- 오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인
1 2 2 2 3- 앞에서부터 공포도를 하나씩 확인하며 '현재 그룹에 포함된 모험가의 수'가 '현재 확인하고 있는 공포도' 보다 크거나 같다면 이를 그룹으로 설정하면 된다.
1 | 2 2 | 2 3
1 2- 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 된다.
해답
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0 ## 그룹 수
count = 0 ## 현재 그룹에 속한 모험가 수
for i in data:
count += 1
if count >= i: # 그룹 결성
result += 1 # 그룹 수 하나 추가
count = 0 # 현재 그룹에 포함된 모험가 수 초기화
print(result)구현 : 시뮬레이션과 완전 탐색
1. 구현
-
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
-
흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까?
- 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 지칭한다
-
구현 문제 유형의 예시
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
-
많은 연습이 필요한 분야
-
일반적으로 많은 기업 코딩테스트 문제에서는 2차원 공간(행렬 : Matrix)에서의 처리를 요구한다
- 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
# 동 북 서 남
dx = [0,-1,0,1]
dy = [1,0,-1,0]
x, y = 2, 2
for i in range (4):
#다음 위치
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)
2 3
1 2
2 1
3 2문제 : 상하좌우
-
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1X1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상(1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여있다.
-
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L,R,U,D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 아래와 같다
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
-
이떄 여행가 A 가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어(1,1) 의 위치에서 L 혹은 U를 만나면 무시된다.
-
아래는 N = 5 인 지도와 계획서이다.
- 입출력 예시
문제 해결 아이디어
- 요구사항대로 충실히 구현하면 되는 문제
- 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로도 분류 되며 구현이 중요한 대표적인 문제 유형
해답
n = int(input())
x, y = 1, 1
plans = input().split()
## L R U D 분류
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move = ['L','R','U','D']
# 이동 계획 확인
for plan in plans:
# 이동 후 좌표 계산
for i in range(len(move)):
if plan == move[i]:
nx = x + dx[i]
ny = y + dy[i]
# 공간 벗어 날때?
if nx < 1 or ny <1 or ny > n or nx > n :
continue
x, y = nx, ny
print(x, y)
5
R R R U D D
3 4문제 : 시각
- 정수 N 이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성해라
예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.- 00 시 00분 03초
- 00 시 13분 30초
- 반면에 아래는 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각
- 00시 02분 55초
- 01시 27분 45초
문제 해결 아이디어
- 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제
- 하루는
24 * 69 * 60 = 86,400초 즉, 경우의 수는 86400 가지 - 이러한 유형을 완전 탐색(Brute Forcing) 문제 유형이라고 함
- 가능한 경우의 수를 모두 검사하는 탐색 방법
해답
h = int(input())
count = 0
for i in range (h+1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)
5
11475참고 자료
서적 : 이것이 코딩 테스트다 with 파이썬
채널 : '동빈나' YouTube Channel
무럭무럭 자라볼까