from collections import deque
N = int(input())
gp = [[] for _ in range (0,N+1)]
for _ in range (0,N-1):
a,b = map(int,input().split())
gp[a].append(b)
gp[b].append(a)
depth = [[] for _ in range (0,N+1)]
depth[1] = (1,1)
deq = deque()
check = [False for _ in range (0,N+1)]
new_graph = [[] for _ in range (0,N+1)]
deq.append((1,1))
while deq:
x = deq.popleft()
x,y = x[0], x[1]
check[x] = True
for z in gp[x]:
if check[z] == False:
deq.append((z,y + 1))
new_graph[x].append((z,y+1))
ans = [0 for _ in range (0,N+1)]
for i in range (0,N+1):
if new_graph[i] != []:
for x in new_graph[i]:
ans[x[0]] = i
for i in range (2,N+1):
print(ans[i])
from collections import defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
cnt = defaultdict(int)
length = defaultdict(int)
for _ in range (0,N):
a = input().rstrip()
if len(a) >= M:
cnt[a] += 1
length[a] = len(a)
words = []
dd = list(cnt.keys())
for word in dd:
words.append([word, cnt[word], length[word]])
words.sort(key = lambda x:(-x[1],-x[2],x[0]))
for word in words:
print(word[0])
import sys
sys.setrecursionlimit(10000)
N,M = map(int,input().split())
x,y,di = map(int,input().split())
mapp = []
for _ in range (0,N):
a = list(map(int,input().split()))
mapp.append(a)
direction =[[-1,0],[0,1],[1,0],[0,-1]]
check = [[False for _ in range (0,M)] for _ in range (0,N)]
#di는 방향을 나타내고 있는 것
def algo(x,y,di):
cnt = 0
while True:
if mapp[x][y] == 0 and check[x][y] == False:
cnt += 1
check[x][y] = True
#첫번째 스텝에서 진행하는 자리가 더러우면 청소하는 경우
#자신의 4방향 탐지하기
jud = True
for i in range (1,5):
#반시계방향부터 탐색한다는 것에 유의
t = (di - i) % 4
xx = x + direction[t][0]
yy = y + direction[t][1]
if 0 <= xx < N and 0 <= yy < M:
if mapp[xx][yy] == 0 and check[xx][yy] == False:
jud = False
x,y,di = xx,yy,t
break
if jud == True:
a = x - direction[di][0]
b = y - direction[di][1]
if mapp[a][b] == 1 or (0 > a or a == N or 0 > b or M == b):
print(cnt)
return
x,y = a,b
algo(x,y,di)
시간이 좀 오래 걸렸던 문제 ... 다 짜놓고서 이상한 곳에서 뻘짓을 많이했던 기억이 ....
import copy
N,M = map(int,input().split())
mapp = []
check = [[0 for _ in range (0,M)] for _ in range (0,N)]
camera = []
dx,dy = [1,0,-1,0], [0,1,0,-1]
for i in range (0,N):
a = list(map(int,input().split()))
mapp.append(a)
for j in range (0,M):
if 1 <= a[j] <= 5:
camera.append([a[j], i,j])
ans = int(1e9)
pattern = [[],[[0],[1],[2],[3]],[[0,2],[1,3]],[[0,1],[1,2],[2,3],[3,0]],[[0,1,2],[1,2,3],[2,3,0],[3,0,1]],[[0,1,2,3]]]
#pattern은 카메라 종류를 지시함
#카메라의 x,y는 위치
def view(area,mode,x,y):
for i in mode:
a,b = x,y
while True:
a += dx[i]
b += dy[i]
if 0 <= a < N and 0 <= b < M:
if area[a][b] == 0:
area[a][b] = -1
elif area[a][b] == 6:
break
else:
break
def dfs(depth, area):
global ans
if depth == len(camera):
cnt = 0
for i in range (0,N):
cnt += area[i].count(0)
ans = min(ans,cnt)
area = copy.deepcopy(mapp)
return
new_area = copy.deepcopy(area)
cctv,x,y = camera[depth]
for i in pattern[cctv]:
view(new_area,i,x,y)
dfs(depth + 1, new_area)
new_area = copy.deepcopy(area)
dfs(0,mapp)
print(ans)
from itertools import permutations
N = int(input())
num = list(map(int,input().split())) #숫자들
cal = list(map(int,input().split())) #연산자 갯수
sym = []
for i in range (0,4):
for j in range (0,cal[i]):
if i == 0:
sym.append("+")
elif i == 1:
sym.append("-")
elif i == 2:
sym.append("*")
elif i == 3:
sym.append("//")
#A가 결국은 연산자 순서를 나타나게 될 것이다.
number = [i for i in range (0,N-1)]
A = list(permutations(number,N-1))
minimum = 1e10
maximum = -1e10
for a in A:
t = num[0]
for i in range (0,N-1):
if sym[a[i]] == "+":
t += num[i+1]
elif sym[a[i]] == "-":
t -= num[i+1]
elif sym[a[i]] == "*":
t *= num[i+1]
elif sym[a[i]] == "//":
t = int(t / num[i+1])
minimum = min(minimum, t)
maximum = max(maximum, t)
print(maximum, minimum)
이 코드를 짜면서 문제인 부분은, 답이 1e9가 나왔을때 출력이 10000..... 0.000... 으로 실수형으로 나온다는 점에 제대로 착안해야한다는 점이다.
이 부분을 피하기 위해서, 초기 셋팅을 1e10과 -1e10 등으로 변경하는 것이 주효하였다.
삼성 서류에 붙었으니만큼, 코테를 확실히 준비하는 것이 맞지 않나싶어 열심히 풀어보고 있다.
작년 하반기에는 메모리 분석 및 평가 포지션에 넣었는데 광탈했던 슬픈 기억이 새록새록 ㅎㅎ...
from collections import deque
N = int(input())
pool = [] #전체적인 지도
for i in range (0,N):
a = list(map(int,input().split()))
for j in range (0,len(a)):
if a[j] == 9:
start = [i,j]
pool.append(a)
ans,exp,lev = 0,0,2 #exp가 lev와 같아지면 lev += 1, exp = 0
dx,dy = [0,0,1,-1], [1,-1,0,0]
def bfs(x,y):
visited = [[0 for _ in range (0,N)] for _ in range (0,N)]
deq = deque([[x,y]])
next = []
visited[x][y] = 1
while deq:
t = deq.popleft()
a,b = t[0], t[1]
for i in range (0,4):
aa,bb = a + dx[i], b + dy[i]
if 0 <= aa < N and 0 <= bb < N and visited[aa][bb] == 0:
if pool[x][y] > pool[aa][bb] and pool[aa][bb] != 0:
visited[aa][bb] = visited[a][b] + 1
next.append([visited[aa][bb]-1, aa,bb])
elif pool[aa][bb] == pool[x][y]:
visited[aa][bb] = visited[a][b] + 1
deq.append([aa,bb])
elif pool[aa][bb] == 0:
visited[aa][bb] = visited[a][b] + 1
deq.append([aa,bb])
next.sort(key = lambda x: (x[0], x[1], x[2]))
pool[x][y] = 0
if next == []:
return None
return next[0]
while True:
pool[start[0]][start[1]] = lev
t = bfs(start[0], start[1])
if t == None:
break
else:
ans += t[0]
exp += 1
start = [t[1], t[2]]
if lev == exp:
exp = 0
lev += 1
pool[start[0]][start[1]] = 0
print(ans)
import math
N = int(input())
jud = False
t = int(math.log2(N+1)) #t개까지 할 수 있을듯?
for k in range (3, t+1): #k는 항의 갯수
r = 2
while r ** (k-1) <= N:
if N * (r - 1) % (r ** k - 1) == 0:
a = N * (r - 1) // (r ** k - 1)
ans = [a * (r**l) for l in range (0,k)]
jud = True
break
else:
r += 1
if jud == False:
print(-1)
else:
print(len(ans))
print(*ans)
부등식을 통해서 수를 얼마나 잘 컨트롤 할 수 있을지 체크하는 것이 중요하겠다.
처음 공비의 상한을 () ** (1/k) 꼴로 만들어서 했었는데, 이러면 10000이상에서 문제가 해결이 되지 않는 경우가 생겼었다.
이를 해결하게 위해 while을 통해서 그 범위를 컨트롤 하는 것으로 변경하였더니 바로 문제가 풀렸다 :)
def prime_set(n):
if n == 2:
return [2]
if n == 3:
return [3]
prime = []
t = int(math.sqrt(n)) + 1
num = [False for i in range (0,t+1)]
for i in range (2,t+1):
if num[i] == False:
prime.append(i)
for j in range (i, t+1, i):
num[j] = True
return prime
#prime은 소수를 저장하고 있는 집합
위 과정에서는 주어진 n까지의 소수를 취하고 싶은 상황인데, n까지의 집합을 취하게 되면 꼭 도중에 메모리가 터지게 되는 것 같았다.
그래서, 메모리 관리를 해주는 법으로, t를 저렇게 정리해둔 다음에, t까지의 소수들을 전부 취해준다.
나머지 것들은 이후에 핸들링 해주는 것으로 저렇게 얻어낸다.
def ofprime(n):
prime = []
t = prime_set(n)
for i in range (0,len(t)):
if n % t[i] == 0:
prime.append(t[i])
while n % t[i] == 0:
n //= t[i]
if n != 1:
prime.append(n)
return prime
ofPrime이라는 함수를 통해서, n의 소인수들을 얻어줄 것이다. 이 과정에서 위에서 구한 prime_set을 활용하겠다.
여기서 중요한 점으로서, 마지막 조건문인 n!= 1이라면 n을 추가해주는 것. 이게 핵심인 부분이다.
예를 들어 주어진 수 n이 합성수라면, n = a x b라는 형식으로 얻어질텐데, 일반성을 잃지 않고 a <= b라고 둘 수 있겠다.
저말이 무슨 뜻이냐면, 만약 n의 제곱근정도까지의 소수로 안 나눠떨어졌다 ! 그러면 n은 반드시 소수여야만 한다는 것
이후의 과정은 포함배제의 원리를 사용하면 되겠다.
이거는 아래에 추가로 기재해두겠다.
import sys
from itertools import combinations
import math
input = sys.stdin.readline
def prime_set(n):
if n == 2:
return [2]
if n == 3:
return [3]
prime = []
t = int(math.sqrt(n)) + 1
num = [False for i in range (0,t+1)]
for i in range (2,t+1):
if num[i] == False:
prime.append(i)
for j in range (i, t+1, i):
num[j] = True
return prime
#prime은 소수를 저장하고 있는 집합
def ofprime(n):
prime = []
t = prime_set(n)
for i in range (0,len(t)):
if n % t[i] == 0:
prime.append(t[i])
while n % t[i] == 0:
n //= t[i]
if n != 1:
prime.append(n)
return prime
T = int(input())
for case in range (0,T):
a,b,N = map(int,input().split())
cnt1,cnt2 = a-1,b
prime = ofprime(N)
for i in range (1,len(prime)+1):
k = list(combinations(prime,i))
k = list(set(k))
for comb in k:
t = 1
for j in range (0,len(comb)):
t *= comb[j]
#t로 나누겠다는 뜻
if i % 2 != 0:
cnt1 -= (a-1) // t
cnt2 -= b // t
else:
cnt1 += (a-1) // t
cnt2 += b // t
print(f'Case #{case + 1}: {(cnt2 - cnt1)}')
간만에 기분 좋게 풀었던 문제가 되겠다. 꽤 오래된 체증이 내려가는 느낌....
내일부터는 계약직으로 일을 시작하게 되는데, 코딩 역량도 키우면서 운동도 해보고, 바쁜 삶을 한동안 살아봐야겠다.
