[알고리즘] 구현

[구현]

• 피지컬 문제라고도 한다. 아이디어를 코드로 바꾸는걸 구현이라고 한다.
• 이코테 책에서는 완전탐색과 시뮬레이션을 가지고 구현 예제를 들었다.
  완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법
  시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

 

[파이썬에서 리스트 크기]

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

리스트를 여러개 선언하고, 그 중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자.

 

 

[채점 환경]

• 파이썬의 경우 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다.
• 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있따면 일반적으로 시간 복잡도 \( O(NlogN) \) 이내의 알고리즘을 이용해 문제를 풀어야 한다.
  ( N = 1,000,000  일 때, NlogN 은 약 20,000,000개 )
• 팁, Pypy3 가 있다면, 파이썬3 와 동일한 코드를 작성하고, 실행 시간을 때론 C/C++ 과 견줄 정도로 단축 시킬 수 있다.

---

[상하좌우] 

• .n x n 박스 안에서 상하좌우 입력받는다고 한다. 이코테 110p 참고
• 그냥 해도 O(N) 만큼의 연산이 걸리므로 간단히 풀어낼 수 있다. (시뮬레이션 문제)

N = int(input())
direct = input().split()
present = [1,1]

for i in direct:
    if i == 'R':
        if present[1] == N : continue
        present[1] += 1
    elif i == 'L':
        if present[1] == 1 : continue
        present[1] -= 1
    elif i == 'U':
        if present[0] == 1 : continue
        present[0] -= 1
    elif i == 'D':
        if present[0] == N : continue
        present[0] += 1
print(f'{present[0]} {present[1]}')

'''
5
R R R U D D

3 4
'''

 

---

[시각] 

• 00시 00분 00초 부터 정수 N이 입력되면, N시 59분 59초까지 3이 하나라도 포함된 모든 경우의 수를 구하는 문제 
  이코테 113p
• 23시 59분 59초까지 모든 경우의 수는 86,400가지 밖에 존재하지 않는다. 따라서 매번 모든 경우의 수를 다 돌려가며 세도 괜찮다.
• 시, 분, 초에 대해 3중 for문을 이용해 확인할 수 있을 것이다.
• 풀이는 생략