이코테 CHAPTER 04 구현 정리 및 실전 문제

아이디어를 코드로 바꾸는 구현

• 구현
  • 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
  • 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
  • ex
    • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
    • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
    • 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
    • 적절한 라이브러리를 찾아서 사용해야 하는 문제
    • N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야 하는 문제 → python itertools 사용(표준 라이브러리)
• 시뮬레이션 및 완전 탐색 문제
  • 시뮬레이션
    • 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제
  • 완전 탐색
    • 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 2차원 공간 → 행렬(Matrix)
  • 방향 벡터 사용(동서남북)
• 구현 시 고려해야 할 메모리 제약 사항
  • 파이썬에서 리스트 크기
  • 대체로 코테에서 128~512MB로 메모리 제한

  

  • 파이썬은 다른 언어에 비해 구현상의 복잡함이 적은편
  • 하지만 데이터 처리량이 많을 때는 꼭 메모리 제한 고려
  • 1,000만 이상의 크기를 갖는 리스트 주의
• 채점 환경
  • 시간 제한, 메모리 제한
  • 파이썬은 동작 속도 느림
    • 1초에 ~2000만 번의 연산 수행 시 무리 없음
  • 시간 제한이 1초, 데이터 개수가 100만개
    • 시간복잡도 O(NlogN) 이내의 알고리즘 이용
    • N= 1,000,000 → Nlog2N  20,000,000
• 구현 문제에 접근하는 방법

  

  • Pypy3
    • 파이썬3의 문법을 그대로 지원
    • 그러나 대부분 실행 속도가 더 빠름
    • 1초에 2000만번~1억번 연산 처리 가능
  • API 개발 문제(카카오 공채)
    • 웹 서버, 데이터 분석 기초 지식

예제

4-1 상하좌우

• 나의 풀이

n = int(input())
#5

direct = list(map(str, input().split()))
#R R R U D D
direct
#['R', 'R', 'R', 'U', 'D', 'D']

def travel(n, direct):
	location = [1,1]
	#L,R,D,U
	direction = {'L':[0,-1],'R':[0,1],'D':[1,0],'U':[-1,0]}

	for i in direct:
	    new_x=location[0]+direction[i][0]
	    new_y=location[1]+direction[i][1]
	    #print('x:',new_x,'y:',new_y)
	    if new_x<1 or new_x>n or new_y<1 or new_y>n:
	        pass
	    else:
	        location[0] = new_x
	        location[1] = new_y
	    #print(location[0],location[1])

	return location[0],location[1]

X, Y = travel(n, direct)
print(X,Y)
#3 4

• 답안 예시

# N을 입력받기
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_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans: # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]: 
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny
    
print(x, y)

#5
#R R R U D D
#3 4

• 함수 안쓰고 바로 for문 사용
• dict 안쓰로 list 여러개 씀 => 메모리 크기 비교하기

 

4-2 시각

• 나의 풀이

  24*60*60
  #86400
  #10만개도 안되는 데이터 탐색이므로 2초 안에 수행 가능
  
  n = int(input())
  #5
  
  count = 0
  
  for h in range(n+1):
      for m in range(60):
          for s in range(60):
              if '3' in str(h) or '3' in str(m) or '3' in str(s):
                  count+=1
  
  print(count)
  #11475​

• 답안 예시

  # H를 입력받기
  h = int(input())
  count = 0
  
  for i in range(h + 1):
      for j in range(60):
          for k in range(60):
              # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
              if '3' in str(i) + str(j) + str(k):
                  count += 1
  print(count)
  
  #5
  #11475​

• str(i) + str(j) + str(k) : or 구문 대신 문자열 덧셈 이용하기

 

 

실전 문제

1. 왕실의 나이트 (성공)

• 나의 풀이

location = str(input())

#direction
dx=[2,2,-2,-2,1,1,-1,-1]
dy=[1,-1,1,-1,2,-2,2,-2]

#column 변환
col_x={'a':1,'b':2,'c':3,'d':4,'e':5,'f':6,'g':7,'h':8}

x=int(col_x[location[0]])
y=int(location[1])

cnt=0

for i in range(len(dx)):
    nx = x + dx[i]
    ny = y + dy[i]

    if nx>=1 and nx<=8 and ny>=1 and ny<=8:
        cnt+=1

print(cnt)
#a1
#2

#c2
#6

• 답안 예시

##답안 예시

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps: 
	# 이동하고자 하는 위치 확인
	next_row = row + step[0]
	next_column = column + step[1]
	# 해당 위치로 이동이 가능하다면 카운트 증가
	if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
		result += 1

print(result)

• ord(c)는 문자의 유니코드 값을 돌려주는 함수이다.

     ※ ord 함수는 chr 함수와 반대이다.

 

2. 게임 개발 (실패)

• 답안 예시

n,m = map(int,input().split())
x,y,d=map(int,input().split())

map = []
for i in range(n):
    map.append(list(map(int, input())))

##############################

n = 4
m = 4
x = 1
y = 1
direct = 0

map = [[1,1,1,1],
       [1,0,0,1],
       [1,1,0,1],
       [1,1,1,1]]
       
##############################

# 0: 북쪽 / 1: 동쪽 / 2: 남쪽 / 3: 서쪽
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
d[x][y] = 1     # 현재 좌표 방문 처리

# 왼쪽으로 회전
def turn_left():
    global direct
    direct-=1
    if direct == -1:
        direct = 3
    return direct

# 시뮬레이션 시작
cnt = 1
turn_time = 0

while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[direct]
    ny = y + dy[direct]

    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and map[nx][ny]==0:
        d[nx][ny] = 1
        x = nx
        y = ny
        cnt +=1
        turn_time = 0
    
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1

    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[direct]
        ny = y - dy[direct]

        # 뒤로 갈 수 있다면 이동하기
        if map[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다로 막혀있는 경우
        else:
            break
        turn_time = 0

    
print(cnt)
#3

 

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저