: 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

(이코테 2021 강의 몰아보기) 2. 그리디 & 구현

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

• 구현
  • 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
  • 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
  • [이코테] 완전 탐색, 시뮬레이션 유형
    • 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 (100만 개 이하일 때)
    • 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형
      • 2차원 공간, 방향 벡터
• 유의해야 할 점
  • 파이썬에서 리스트 크기(메모리 제한)
  • 시간 제한 1초, 데이터 개수 100만 개 → 시간 복잡도 $O(NlogN)$ 이내의 알고리즘을 이용해야
• 접근 방법
  • 파이썬: 구현 난이도 쉬움, 프로그램 실행 시간 긴 편
  • Pypy3: 파이썬3의 문법 그대로 지원 + 실행 속도는 더 빠름

[예제 4-1] 상하좌우 시뮬레이션

[예제 4-2] 시각 완전 탐색

실전 문제

왕실의 나이트

게임 개발

[백준] 문제 풀이

• 브루트 포스 문제 다 풂!

4673 셀프 넘버

• [시도1] 답은 나오는데 시간 초과

arr = []
for i in range(1, 10001):
    i_sum = i
    for j in range(len(str(i))):
        i_sum += int(str(i)[j])
    arr.append(i_sum)

for i in range(1, 10001):
    if i in arr:
        continue
    else:
        print(i)

2108 통계학

• from collections import Counter
  1. Counter(arr).items()
  2. Counter(arr).most_common(n)

import sys
from collections import Counter

input = sys.stdin.readline

N = int(input())
arr = []
for n in range(N):
    arr.append(int(input()))
    
mean = round(sum(arr)/N)
med = sorted(arr)[N//2]
count = Counter(arr)
modes = []
for el, cnt in count.items():
    if cnt == max(count.values()):
        modes.append(el)
if len(modes) > 1:
    modes.remove(min(modes))
mod = min(modes)
rang = max(arr) - min(arr)
print(mean, med, mod, rang, sep='\\n')

1331 나이트 투어

import sys
input = lambda: sys.stdin.readline().rstrip()

def loc_to_coord(loc):
    return [int(ord(loc[0]) - ord('A') + 1), int(loc[1])]

def check_next(new, past):
    global visited
    if abs(new[0] - past[0]) == 2 and abs(new[1] - past[1]) == 1:
        return True
    elif abs(new[0] - past[0]) == 1 and abs(new[1] - past[1]) == 2:
        return True   
    else:
        return False

loc = loc0 = loc_to_coord(input())
visited = [[0]*6 for _ in range(6)]
visited[loc[0]-1][loc[1]-1] += 1

for i in range(35):
    new_loc = loc_to_coord(input())
    
    if visited[new_loc[0]-1][new_loc[1]-1] == 0 and check_next(new_loc, loc):
        loc = new_loc
        visited[loc[0]-1][loc[1]-1] += 1
    else:
        break

is_zero = 0
for i in range(6):
    is_zero += int(0 in visited[i])
    
if is_zero == 0 and check_next(loc, loc0):
    print("Valid")
else:
    print("Invalid")