일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 코딩테스트
- CleanCode
- html
- Web
- 순환
- Kotlin
- 자바
- 프로그래머스
- DFS
- algorithm
- java
- 정렬
- codecademy
- front-end
- 클린코드
- BFS
- Spring
- Color
- 구현
- 다이나믹 프로그래밍
- android
- CSS
- javascript
- 알고리즘
- inflearn
- SWEA
- DP
- 검색트리
- SQL
- 해슁
- Today
- Total
깡뇽
[코테] 구현 공부하기 본문
Day5
구현 → 완전 탐색(모든 경우의 수를 다 계산하는 방법), 시뮬레이션(문제에서 제시한 알고리즘을 차례대로 직접 수행)
파이썬 < int 자료형 데이터의 개수에 따른 메모리 사용량 >
데이터의 개수(리스트의 길이) : 1,000 → 메모리 사용량 약 4KB
1,000,000 → 약 4MB
10,000,000 → 약 40MB
주의) 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 못 풀 수도 있음.
1초에 2,000만 번의 연산 수행 가능하다고 가정.
시간 제한이 1초, 데이터의 개수 100만 개인 문제는 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 풀어야 함.
예제1) 상하좌우
Q. N X N 크기의 정사각형 공간을 L(왼쪽), R(오른쪽), U(위쪽), D(아래쪽) 방향으로 한 칸 씩 이동할 수 있고, 가장 왼쪽 위 좌표는 (1,1) 이다. 그러나 공간을 벗어나는 이동은 무시된다. N 값, 이동 방향이 주어졌을 때 최종적으로 도착할 지점의 좌표를 출력하자.
A. 공간과 좌표를 구현해야 한다.
n = int(input()) #N입력
guide = input().split() #이동 방향 입력
x, y = 1, 1 #기준 좌표
#방향에 따른 이동 좌표
direction = ['L','R','U','D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
#이동 방향에 따라 좌표 이동
for i in guide:
for j in range(0, len(direction)):
if i == direction[j]:
nx = x + dx[j]
ny = y + dy[j]
#공간을 벗어나는 경우에는 무시하고 넘어가기
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
#좌표에 이동한 좌표 대입
x, y = nx, ny
print(x, y)
예제2) 시각
Q. 00시 00분 00초부터 N(0≤N≤23)시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우의 수를 구하자.
A. 00시 00분 00초 ~ 23시 59분 59초까지의 모든 경우는 86,400가지로 100,000개보다 작아서 하나씩 세서 풀어도 된다. → 완전 탐색(Brute Forcing) 유형. 탐색할 전체 데이터가 100만 개 이하일 때 완전 탐색 사용.
n = int(input())
cnt = 0
#시
for i in range(0, n+1):
#분
for j in range(0, 60):
#초
for k in range(0, 60):
#시간을 str타입으로 변환
clock = str(i) + str(j) + str(k)
#시간에 3이 들어가 있다면 1을 카운트
if '3' in clock:
cnt += 1
else:
continue
print(cnt)
'Algorithm > Coding Test' 카테고리의 다른 글
[코테] 구현 문제풀기 - 게임 개발 (0) | 2022.02.04 |
---|---|
[코테] 구현 문제풀기 - 왕실의 나이트 (0) | 2022.02.03 |
[코테] 그리디 문제풀기 - 1이 될 때까지 (0) | 2022.02.01 |
[코테] 그리디 문제풀기 - 숫자 카드 게임 (0) | 2022.02.01 |
[코테] 그리디 문제풀기 - 큰 수의 법칙 (0) | 2021.08.20 |