[Python] 이코테 Chapter 3, 4 문제풀이

학교에서 코테스터디를 시작하였다.

코테 빈출유형 14가지에 대해 약 7주동안 스터디를 진행할 예정이다.

 

이번이 첫주차이다. 

이번 주차에는 그리디와 구현 유형에 대해 공부하였다.

쉬운 유형이지만 그만큼 방심하면 안된다고 생각해서 열심히 풀었다.

 

3-2. 큰수의법칙

 

3-2. 소스코드

import sys
ip = sys.stdin.readline

#입력부분
n, m, k = map(int,ip().split())
arr = list(map(int,ip().split()))

#값 정렬 (가장큰수와 두번째로큰수 찾기위함)
arr.sort()

res = 0

# m번반복
for i in range(1,m+1) :

    # 한 수를 k번 반복시 두번째로 큰수로 갈아탐
    if (i % k == 0) :
        res += arr[-2]

    # ...
    else :
        res += arr[-1]

print(res)

3-2. 풀이

 

기본적으로 가장 큰 수를 만들어야 하므로 가장 큰수를 계속 더해준다.

여기에 한 수가 k번 까지만 반복되도록 두번째로 큰수를 사이사이에 넣으면 끝

 

3-3. 숫자 카드 게임

3-3. 소스코드

import sys
ip = sys.stdin.readline

# 가로세로 입력
n,m = map(int,ip().split())

maxx = 0

for _ in range(n) :
    # 각 행의 최솟값중 최댓값 n번갱신
    # 정렬된리스트의 첫번째값으로 최솟값 찾고 max로 최댓값 찾기
    maxx = max(maxx, sorted(list(map(int,ip().split())))[0]) 


print(maxx)

 

3-3. 풀이

각 행에서 필요한 수는 그 행의 최솟값 뿐이다.

따라서 각 행의 최솟값만 저장해준 후 이들 수의 최댓값을 찾으면 끝

 

3-4. 1이 될 때까지

3-4. 소스코드

import sys
ip = sys.stdin.readline

n,k = map(int,ip().split())

cnt = 0

while True :
	# n이 1이면 종료
    if (n == 1) :
        break
    
    # n을 k로 나눌 수 있으면 나누기
    if (n % k == 0) :
        n /= k
    
    # n을 k로 나눌 수 없으면 1빼기
    else :
        n -= 1
    
    # count 저장
    cnt += 1

print(cnt)

3-4. 풀이

n에 1을 빼는 것보다 k로 나누어주는 것이 무조건 계산횟수상 이득이다.

 

4-2. 왕실의 나이트

 

4-2. 소스코드

import sys
ip = sys.stdin.readline

# 값 입력
knight = ip()
x = ord(knight[0]) - ord('a') + 1
y = int(knight[1])

# 9가지의 경우로 나뉜다
if x == 1 or x == 8 :
    if y == 1 or y == 8 :
        print(2)
    elif y == 2 or y == 7 :
        print(3)
    else :
        print(4)
elif x == 2 or x == 7 :
    if y == 1 or y == 8 :
        print(3)
    elif y == 2 or y == 7 :
        print(4)
    else :
        print(6)
else :
    if y == 1 or y == 8 :
        print(4)
    elif y == 2 or y == 7 :
        print(6)
    else :
        print(8)

4-2. 풀이

 

체스판에 각 칸에서 나이트가 움직일 수 있는 경우의수를 체스판에 다 적어보았다.

 

적고보니 그림이 좀 징그러워서 접은글에 그림을 남겨놓았다

 

이 경우의 수를 일일이 if문을 사용하여 구현하였다.

 

4-3. 게임 개발

 

4-3. 소스코드

import sys
from collections import deque
ip = sys.stdin.readline

# 상하좌우 움직임
direction = [[0,1],[0,-1],[1,0],[-1,0]]

# 값 입력
n,m = map(int,ip().split())
x0, y0, start = map(int,ip().split())

# 방문여부 저장
visited = [[False for _ in range(m)] for _ in range(n)]
arr = []


for _ in range(n) :
    arr.append(list(map(int,ip().split())))

cnt = 0
queue = deque()
queue.append([y0,x0])

# BFS
while queue :
    y,x = queue.popleft()
    visited[y][x] = True
    for dy, dx in direction :
        if arr[y+dy][x+dx] == 0 and not visited[y+dy][x+dx] :
            queue.append([y+dy,x+dx])
            
    cnt += 1

print(cnt)

4-3. 풀이

 

구현문제지만 bfs풀이가 가장 이상적인 것 같았다.

 

bfs 이용하여 시작점으로부터 연결되어있는 육지의 개수를 세주었다.

좌표문제풀때는 direction을 설정하는 것이 중요한 것 같다.

 

+ 4-3. 소스코드 추가

 

import sys
ip = sys.stdin.readline

# 움직임 방향
direction = [[-1,0],[0,-1],[1,0],[0,1]]

n,m = map(int,ip().split())
x,y,dcnt = map(int,ip().split())

visited = [[False for _ in range(m)] for _ in range(n)]
arr = []

for _ in range(n) :
	arr.append(list(map(int,ip().split())))

# 답 카운트
cnt = 0




# 턴 카운트
tcnt = 0

while True :
    dcnt += 1
    
    # 왼쪽으로 턴
    nx = x + direction[dcnt%4][1]
    ny = y + direction[dcnt%4][0]

    # 1번 경우
    if not visited[ny][nx] and arr[ny][nx] == 0 :
        visited[ny][nx] = True
        x = nx
        y = ny
        cnt += 1
        tcnt = 0
        continue

    # 2번 경우
    else :
        tcnt += 1

    # 3번 경우
    if tcnt == 4 :
        nx = x-direction[dcnt%4][1]
        ny = y-direction[dcnt%4][0]
        if arr[ny][nx] == 0 :
            x = nx
            y = ny
        else :
            break
        tcnt = 0
        
 print(cnt)

문제에 주어진 말그대로 푸는 방법이 정석인 것 같다.