No. 10819
1. Problem
2. My Solution
- 백트래킹을 이용해서 모든 수열을 구하고 각각 sum 을 구한뒤 max 로 출력
import sys
def permutation(level):
if level >= n:
res.append(sum(arr.copy()))
else:
for i in range(n):
if visited[i] == True:
continue
visited[i] = True
arr[level] = nums[i]
permutation(level+1)
visited[i] = False
def sum(arr):
temp = 0
for i in range(len(arr)-1):
temp += abs(arr[i] - arr[i+1])
return temp
n = int(sys.stdin.readline())
nums = list(map(int,sys.stdin.readline().rstrip().split()))
arr = [0] * n
visited = [False] * n
res = []
permutation(0)
print(max(res))No. 7562
1. Problem
2. Others' Solutions
- BFS 알고리즘을 이용하여 문제 해결
- 최단 경로를 판단할 때 가장 먼저 해당 정점을 탐색한 경로가 최단경로임
- 최단 경로 다음으로 탐색되는 경로는 최단경로보다 같거나 뒤늦은 경로임
import sys
from collections import deque
def bfs(x,y):
queue = deque()
queue.append((x,y))
chess[x][y] = 0 # 원점으로 다시오는 것을 제거
while(queue):
x,y = queue.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy
# 제일 먼저 해당 좌표값을 수정하는 경로가 최단거리임
if 0 <= nx < i and 0 <= ny < i and chess[nx][ny] == 1: # 아직 아무도 방문하지 않았다면
chess[nx][ny] = chess[x][y] + 1
queue.append((nx,ny))
if nx == target_x and ny == target_y:
return chess[nx][ny]
test_n = int(sys.stdin.readline())
for _ in range(test_n):
i = int(sys.stdin.readline())
target_x, target_y = map(int,sys.stdin.readline().rstrip().split())
present_x, present_y = map(int,sys.stdin.readline().rstrip().split())
chess = [[1]*i for _ in range(i)]
move = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]
if target_x == present_x and target_y == present_y:
print(0)
else:
print(bfs(present_x, present_y))
3. Learned
- DFS 알고리즘을 이용한다면 최단경로를 보장할 수 없음
No. 1991
1. Problem
2. My Solution
- 트리를 배열(리스트)로 구현
- 이진트리는 최악의 경우(경사트리) 원소가 n개 일때 2^n-1 개의 배열공간이 필요함
- 2^26-1 = 4608MB -> 메모리 초과
import sys
sys.setrecursionlimit(10**8)
def preorder(index):
if index < len(tree):
if tree[index] != '.':
result[0].append(tree[index])
preorder(index*2+1)
preorder(index*2+2)
def inorder(index):
if index < len(tree):
inorder(index*2+1)
if tree[index] != '.':
result[1].append(tree[index])
inorder(index*2+2)
def postorder(index):
if index < len(tree):
postorder(index*2+1)
postorder(index*2+2)
if tree[index] != '.':
result[2].append(tree[index])
n = int(sys.stdin.readline())
tree = ['A'] + ['.'] * (2**n -3) # 경사 이진트리일 경우를 대비
result = [[],[],[]]
# 트리를 배열(리스트)에 저장
for i in range(n):
root, left, right = sys.stdin.readline().rstrip().split()
tree[tree.index(root)*2+1] = left
tree[tree.index(root)*2+2] = right
preorder(0)
inorder(0)
postorder(0)
for i in range(3):
print(*result[i], sep='')- 해결방법
- dict 자료형을 사용하여 {문자:index, index:문자} 정보를 저장
- 그러면 n*2 개의 dict 공간만을 사용하게됨 ({'.' : index} 처럼 필요없는 값이 하나 생기기는 함)
- dict.get(index) 의 반환값이 None 이라면 배열 범위를 벗어났다고 판단
import sys
sys.setrecursionlimit(10**8)
def preorder(index):
if dict.get(index) and dict[index] != '.':
result[0].append(dict[index])
preorder(index*2+1)
preorder(index*2+2)
def inorder(index):
if dict.get(index) and dict[index] != '.':
inorder(index*2+1)
result[1].append(dict[index])
inorder(index*2+2)
def postorder(index):
if dict.get(index) and dict[index] != '.':
postorder(index*2+1)
postorder(index*2+2)
result[2].append(dict[index])
n = int(sys.stdin.readline())
dict = { 0: 'A', 'A': 0}
result = [[],[],[]]
for i in range(n):
root, left, right = sys.stdin.readline().rstrip().split()
dict[dict[root]*2+1], dict[left] = left, dict[root]*2+1
dict[dict[root]*2+2], dict[right] = right, dict[root]*2+2
preorder(0)
inorder(0)
postorder(0)
for i in range(3):
print(*result[i], sep='')
3. Learned
- 메모리 초과를 생각하며 값을 저장하게 될 collection 자료형 사용에 주의하자
No. 2292
1. Problem
2. My Solution
- 해당 층에서의 최대값보다 크면 다음층으로 넘어가야함
- 최대값보다 큰 게 아니라면 -> 같거나 작다면 해당층에 n이 존재하므로 while 종료
- 0 level 은 그냥 보너스로 증가한다고 생각하면 편할듯
import sys
n = int(sys.stdin.readline())
level = 0
level_max = 1
if n == 1:
print(0)
else:
while(n > level_max):
level_max += (6 * level)
level += 1
print(level)
3. Learned
- 부등호의 방향과 모양을 여러 의미로 받아들일 줄 알아야함
- a는 b보다 큰 게 아니다 = a는 b와 같거나 작다
- a는 b보다 크거나 같은게 아니다 = a는 b보다 작다 ...등등
