이코테 2021] 2. 구현 강의 노트

https://youtu.be/2zjoKjt97vQ

 

구현(Implementation)

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

알고리즘 대회에서 구현 유형의 문제란?

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭

구현 유형의 예시

• 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루거나, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아 사용해야 하는 문제

---

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix) 의 의미로 사용된다.

 

for i in range(5):
	for j in range(5):
    	print('(',i,',',j,')',end=' ')
    print()

 

시뮬레이션 및 완전 탐색 문제에서는 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)

 

<문제1> 상하좌우

솔루션

<문제2> 시각

솔루션 : 86,400 초 동안 모든 경우의 수 탐색하기 (완전 탐색)

# 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)

---

<문제3> 왕실의 나이트

아이디어

• 요구사항대로 충실히 구현하면 되는 문제
• 나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인

솔루션

2차원 배열을 이용해서 방향벡터를 정의 -> dx, dy 2개의 리스트 대신 1개의 리스트(방향 벡터 리스트)로 풀이 가능

---

<문제4> 문자열 재정렬

 

문제 해결 아이디어

 

솔루션