척척석사의 코딩기록

위상정렬 (topological sort)에 대한 내용이 나왔다.

복습으로서는 굉장히 좋을 것 같다 !

from collections import deque
N,M = map(int,input().split())

graph = [[] for _ in range (0,N+1)]
ind = [0 for _ in range (0,N+1)]
for _ in range (0,M):
    a,b = map(int,input().split())
    graph[a].append(b)
    ind[b] += 1

deq = deque()
for i in range (0,N+1): #진입차수가 0인 친구들 먼저 추가 (끝에 있는 친구들부터)
    if ind[i] == 0:
        deq.appendleft(i)

ans = []
while deq:
    x = deq.popleft()
    if x == 0:
        break
    ans.append(x)
    for j in range (0,len(graph[x])):
        ind[graph[x][j]] -= 1
        if ind[graph[x][j]] == 0:
            deq.appendleft(graph[x][j])
answer = " ".join(str(s) for s in ans)
print(answer)

역시 주요한 아이디어는, Indegree가 0인 노드를 추가하면서 (이 친구가 시작점이 되기 때문)

그 노드에서 이어진 Node들의 indegree를 1씩 줄여가며 찾아내가는 방법이 되겠다. 

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for i in range (0,12):
    d[chr(i + 65)] = 0 #각각의 인덱스 저장

cant_zero = []
for i in range (0,N):
    s = input() #입력되는 문자
    n = len(s)
    for j in range (0,n):
        if j == 0:
            cant_zero.append(s[j])
        d[s[j]] += 10 ** (n - 1 - j)

spell = []
for i in range (0,12):
    if d[chr(i + 65)] != 0:
        spell.append([chr(i+65) , d[chr(i + 65)]])
spell.sort(reverse = True, key = lambda x: x[1])
can_zero = []
revised = []

for i in range (0,len(spell)):
    if spell[i][0] in cant_zero:
        revised.append(spell[i])
    else:
        can_zero.append(spell[i])

if len(revised) <= 9:
    for i in range (0,len(can_zero)):
        revised.append(can_zero[i])
    if len(revised) <= 9:
        for j in range (0,9):
            revised.append([0,0])
            
revised = revised[0:9]
revised.sort(reverse= True, key = lambda x : x[1])

ans = 0
for i in range (0,9):
    ans += revised[i][1] * (9-i)
print(ans)

골드 3 문제였는데, 꽤 그래도 재밌게 풀은 느낌이 든다.

도중 몇가지 작업이 필요가 없을 수도 있었는데, 일단은 굉장히 빠르게 해결할 수 있었으니 ... 일단은 만족하는 것으로.

가장 중요한 아이디어 중 하나는, 0이 될 수 없는 문자들을 미리 분류해두고 우선순위에 둘 필요가 있는 것이다.

이 알고리즘에서는 알파뱃들을 총 2번에 걸쳐서 필터링을 하였다.

첫번째로, spell 리스트에서의 for문인데, 여기서 0이 될 수 없는 것들을 우선적으로 revised라는 리스트에 넣어줄 필요성이 있었다.

두번째로, if len(revised)에서, 길이를 강제로 9로 만들어주는 방법을 취하였다. 

꽤 재밌었던 문제 같았다.

from collections import deque
from itertools import combinations
import copy

N,M = map(int,input().split())
block = []
empty = []
virus = []
for i in range (0,N):
    A = list(map(int,input().split()))
    for j in range (0,M):
        if A[j] == 0:
            empty.append([i,j])
        if A[j] == 2:
            virus.append([i,j])
    block.append(A)
ans = 0
for x in combinations(empty,3):
    cnt = 0
    x = list(x)
    B = copy.deepcopy(block)
    B[x[0][0]][x[0][1]],B[x[1][0]][x[1][1]], B[x[2][0]][x[2][1]]  = 1,1,1
    dx,dy = [0,0,-1,1],[1,-1,0,0]
    deq = deque()
    for i in range (0,len(virus)):
        deq.appendleft(virus[i])
    while deq:
        y = deq.popleft()
        for i in range (0,4):
            z = y[0] + dx[i]
            w = y[1] + dy[i]
            if 0 <= z < N and 0 <= w < M and B[z][w] == 0:
                B[z][w] = 2
                deq.append([z,w])
    for i in range (0,N):
        for j in range (0,M):
            if B[i][j] == 0:
                cnt += 1
    ans = max(ans,cnt)
print(ans)

생각보다 클린코드가 나와서 좋았던 것 같습니다. 

바이러스가 옮겨질 조건은, 아무것도 없는 0인 공간에 한하므로, B[z][w]에서 적절하게 이용하면 좋을 것 같습니다.

결국 벽 3개라는 조건이 주어졌으므로, 브루트포스를 통해서 문제를 해결할 수 있었습니다.

문제를 살짝 응용한다면, 벽 하나를 세우는데 cost가 들 때, 최적의 cost - safety area를 컨트롤 하는 방법도 있겠습니다.

오히려 이쪽이 더 재밌을 것 같은 느낌이네요. 대신 이렇게 된다면 난이도는 조금 더 올라갈지도 ... ? 

(벽 갯수를 다시 제한하는 방식 등등으로...)

2023년 9월 에너지솔루션 수시채용 포지션에 지원했습니다.

포지션은 데이터 분석 / 모델링이었던것으로 기억합니다.

먼저, 서류가 굉장히 불이었던 것으로 기억합니다.

서류에서 떨어질줄 알았는데, 정말 운이 좋게 붙었던 것이 기뻐서 지하철 안에서 싱글벙글 했던 것이 떠오르네요.

인적성 검사도 무사히 통과하고, 면접까지 진행되었습니다.

면접은 1차 2차로 나누어지지 않고, 원데이로 이루어졌었고, 대전 -> 서울 순으로 일주일씩 진행이 되었던걸로 기억합니다.

대면면접으로 진행이 되었기에, 한국으로 입국한 뒤 파크원에서 이루어진 면접에 참여했습니다.

파크원 정말 좋더라고요. 그런곳에서 일할 수 있으면 정말 좋겠다는 생각을 참 많이 했던 것 같습니다.

인성, 직무 면접이 각각 40분씩이었고, PT를 준비했습니다.

한 타임에 같은 포지션인 사람 2명이 1조 느낌으로 이루어졌었습니다. 한명이 인성을 보고 있을 때, 다른 한명이 직무를 보는 방식이었네요.

저같은 경우에는 아침 8시반정도의 타임이었던걸로 기억하는데, 다 끝나고 나니 한 11시쯤 되었던걸로 기억해요.

그렇게 하루에 4~5개의 그룹으로 면접이 진행 되었을 것 같습니다. 

직무는 1:1로 이루어졌었고, 인성은 1:2였던 것으로 기억합니다.

두 면접 둘 다 기본적으로 정말 편안한 분위기에서 진행 되었습니다.

굉장히 릴렉스된 분위기에서 면접 진행해 주셨던 것이 기억에 남네요.

인성 부분은 유학을 했었기에 그에 대한 경험을 위주로 많이 물어보셨던 것 같습니다.

그리고 저같은 경우에는 전공이 수학이어서 그랬는지는 모르겠지만, 에너지솔루션, 더 나아가 2차전지에 왜 관심을 가지게 되었는지?

왜 에너지솔루션이어야하는지? 즉, 로열티에 관련된 이야기를 하셨던 것 같습니다.

자신이 에너지솔루션에서 어떤 일을 하고싶은지, 그리고 지원한 직무에서 어떻게 성장해나가고 싶을지 제대로 파악하고 있는 것이 좋을 것 같습니다.

직무 부분은 전공에 대한 이야기를 조금 했던 것 같습니다.

전공 내용 발표를 한 뒤, 그에 대한 질의 응답이 이어졌습니다.

그리고 어떠한 문제에 대한 솔루션을 물어보시고, 그에 대답하는 방식이었습니다.

그리고 면접이 다 끝나고, 같은 타임에 면접이 진행된 사람들끼리 에너지솔루션 파크? 휴게층? 투어가 있었습니다.

HR쪽분이 커피를 사주셨던 것이 떠오르네요 ㅎㅎ.

여러가지 편의시설이 있는 것을 설명해주시고, 그렇게 면접이 종료가 되었습니다.

비록 떨어졌지만 꼭 가고 싶은 매력적인 회사라고 생각했습니다.

입사시기가 1월이었던지라 아직 학기중이라는 단점도 있긴 했지만 .....

떨어져서? 그런건 아니지만 학회 발표도 무사히 마칠 수 있었고, 석사 논문 발표도 무사히 잘 마칠 수 있었던 것 같습니다.

from collections import deque
N,K = map(int,input().split())
deq = deque()
for i in range (1,N+1):
    deq.append(i)

cnt = 1
ans = []
while deq:
    x = deq.popleft()
    if cnt % K == 0:
        ans.append(x)
    else:
        deq.append(x)
    cnt += 1

s = "<" + ", ".join(str(t) for t in ans) + ">"
print(s)

덱으로 빠르게 풀 수 있었다.

백준 28449 누가 이길까

여기서 키워드인것은 인원수가 각각 100,000이므로, 아무리 봐도 O(log N)에서 해결해야한다는 것을 알 수 있다.

아이디어로 사용한 것은

hi / arc 팀을 점수로 정렬한 뒤, 점수별 인원을 defaultdict에 저장해서 나중에 불러오는 형식으로 알고리즘을 짰습니다.

점수로 정렬한 이유는, 이진탐색을 하기 위함입니다.

i) 기본적인 셋팅

먼저, hi, arc에 주어진 list를 아래와 같이 둡니다.

hi = [1,3,7,1,7], arc = [2,2,6,10,6]

#28449 누가 이길까
import sys
from collections import defaultdict

N,M = map(int,input().split())
total = N * M
hi = list(map(int,input().split()))
arc = list(map(int,input().split()))

hi_dict = defaultdict(int)
arc_dict = defaultdict(int)

for i in range (0,N):
    hi_dict[hi[i]] += 1
for i in range (0,M):
    arc_dict[arc[i]] += 1

#hi, arc로 덮어 씌우기
hi = list(hi_dict.keys())
arc = list(arc_dict.keys())

#크기로 조절하기
hi.sort()
arc.sort()

위 과정을 통해 얻어진 hi_dict, arc_dict은 다음과 같습니다.

hi_dict = dict(1 : 2, 3 : 1, 7 : 1), arc_dict = dict(2 : 2, 6 : 2, 10 :1)

hi, arc는 아래와 같습니다.

hi = [1,3,7] , arc = [2, 6, 10] 꼴이 되겠습니다.

누적합을 통해 arc팀의 인원을 더해줍니다.

#arc팀의 인원 순서대로 카운팅하기
N,M = len(hi),len(arc)
arc_people = [0]
for i in range (0,M):
    x = arc_people[i] + arc_dict[arc[i]]
    arc_people.append(x)

그렇다면 arc_people의 리스트는 

arc_people = [0,2,4,5] 가 되겠군요 !

문제에서 활용할 이진 탐색은 이하와 같습니다.

#위치 찾는 인덱스 변환
def binary_search(x,A):
    start,end = 0,len(A)-1
    while start <= end:
        mid = (start + end) // 2
        if A[mid] == x:
            return mid 
        elif A[mid] < x:
            if A[mid] <= x < A[mid + 1]:
                return mid
            else:
                start = mid
        else:
            if A[mid -1] <= x < A[mid]:
                return mid - 1
            else:
                end = mid

아이디어는 이하와 같습니다.

hi[i]가 arc[j]에서 몇번째 인덱스에 있을까? 라는 것입니다

즉, arc[j] <= hi[i] < arc[j+1] 꼴이 되는 j는 무엇인가? 라는 알고리즘이 되겠습니다.

물론, 일부 경우를 제거해야합니다.

예를 들어, hi[i]  <= arc[0] 이거나, hi[i] >= arc[-1]라면 위의 이진탐색 알고리즘을 사용하지 못하겠습니다.

이 경우는, 따로 케이스를 구분해서 계산해주도록 합니다.

#이진탐색 알고리즘 적용
win,draw = 0,0
for i in range (0,N):
    if hi[i] < arc[0]:
        #아무것도 못함
        continue
    elif hi[i] == arc[0]:
        #비기는 것만 가능
        draw += hi_dict[hi[i]] * (arc_people[1] - arc_people[0])
    elif hi[i] == arc[-1]:
        #마지막 인덱스를 제외하고 전부 승리, 마지막 인덱스에서는 비김
        draw += hi_dict[hi[i]] * (arc_people[-1] - arc_people[-2])
        win += hi_dict[hi[i]] * arc_people[-2]
    elif hi[i] > arc[-1]:
        #모든 인원들을 이길 수 있다는 뜻
        win += hi_dict[hi[i]] * arc_people[-1]
    else:
        #hi 값이 arc내에서 부등식 꼴로 나타낼 수 있다는 것
        x = binary_search(hi[i],arc)
        if arc[x] < hi[i]:
            win += hi_dict[hi[i]] * arc_people[x+1]
        else:
            win += hi_dict[hi[i]] * arc_people[x]
            draw += hi_dict[hi[i]] * (arc_people[x+1] - arc_people[x])

print(win,total -(win + draw),draw)

마지막 알고리즘으로 들어왔습니다.

hi[i]가 이기는게 몇번인지, 비기는게 몇번인지 카운팅 해줍니다. 지는 것은 전체 경우에는 앞의 두개를 빼주면 나옵니다.  (total - win - draw)

i) hi[i]가 "arc[0]보다 작은 경우"

hi[i]는 아무도 코딩으로 이길 수 없습니다. pass 합니다.

ii) hi[i]가 "arc[0]과 같은 경우"

hi[i]는 arc[0]과 비기는 방법 밖에 없습니다. 

draw만 추가가 되겠습니다.

iii) hi[i]가 "arc[-1] 보다 큰 경우"

hi[i]는 arc팀의 모든 인원들을 이길 수 있습니다.

win에만 추가가 되겠습니다.

iv) hi[i]가 "arc[-1]과 같은 경우"

hi[i]는 arc[-1] - arc[-2]명의 사람들에게는 비기지만, 그 외에 사람들에게는 전부 이깁니다.

win, draw 같이 올라갑니다.

v) 그 외

arc[j] <= hi[i] < arc[j +1]가 되는 j를 이분탐색을 통해 찾았습니다.

만약 arc[j] = hi[i]라면, win과 draw가 같이 올라가겠습니다

arc[j] < hi[i]라면, win에만 인원수를 추가해주면 되겠습니다.

전체 코드는 이하와 같습니다.

#28449 누가 이길까
import sys
from collections import defaultdict

N,M = map(int,input().split())
total = N * M
hi = list(map(int,input().split()))
arc = list(map(int,input().split()))

hi_dict = defaultdict(int)
arc_dict = defaultdict(int)

for i in range (0,N):
    hi_dict[hi[i]] += 1
for i in range (0,M):
    arc_dict[arc[i]] += 1

#hi, arc로 덮어 씌우기
hi = list(hi_dict.keys())
arc = list(arc_dict.keys())

#크기로 조절하기
hi.sort()
arc.sort()

#hi,arc팀의 인원 순서대로 카운팅하기
N,M = len(hi),len(arc)
arc_people = [0]
for i in range (0,M):
    x = arc_people[i] + arc_dict[arc[i]]
    arc_people.append(x)

#위치 찾는 인덱스 변환
def binary_search(x,A):
    start,end = 0,len(A)-1
    while start <= end:
        mid = (start + end) // 2
        if A[mid] == x:
            return mid 
        elif A[mid] < x:
            if A[mid] <= x < A[mid + 1]:
                return mid
            else:
                start = mid
        else:
            if A[mid -1] <= x < A[mid]:
                return mid - 1
            else:
                end = mid

#이진탐색 알고리즘 적용
win,draw = 0,0
for i in range (0,N):
    if hi[i] < arc[0]:
        #아무것도 못함
        continue
    elif hi[i] == arc[0]:
        #비기는 것만 가능
        draw += hi_dict[hi[i]] * (arc_people[1] - arc_people[0])
    elif hi[i] == arc[-1]:
        #마지막 인덱스를 제외하고 전부 승리, 마지막 인덱스에서는 비김
        draw += hi_dict[hi[i]] * (arc_people[-1] - arc_people[-2])
        win += hi_dict[hi[i]] * arc_people[-2]
    elif hi[i] > arc[-1]:
        #모든 인원들을 이길 수 있다는 뜻
        win += hi_dict[hi[i]] * arc_people[-1]
    else:
        #hi 값이 arc내에서 부등식 꼴로 나타낼 수 있다는 것
        x = binary_search(hi[i],arc)
        if arc[x] < hi[i]:
            win += hi_dict[hi[i]] * arc_people[x+1]
        else:
            win += hi_dict[hi[i]] * arc_people[x]
            draw += hi_dict[hi[i]] * (arc_people[x+1] - arc_people[x])

print(win,total -(win + draw),draw)

오늘 논문 발표 하고 왔습니다.

Title은 작성한 논문 그대로, Critical polyratio and Core entropy 였습니다.

다항식에서의 Hubbard Tree를 보다 넓게, Rational map에 대해서도 비슷한 구조를 구성한 내용입니다.

10여분간의 짧은 발표가 끝나고, 질의응답 시간.

아마 이제 수학계에서 발표하는 마지막 순간이겠거니 싶어서 마음도 아팠습니다.

자리로 돌아온 그 순간 힘이 풀렸던 것 같습니다.

이로서 수학에서의 6년간의 여정이 끝나게 되었네요.

여정이 끝났다는 실감이 나는 것은 아닙니다.

어느순간 다시 수학을 공부하고 있어야할 것 같고, 펜을 잡으며 노트패드에 아이디어를 휘갈겨쓴다던지.

그러한 마음은 어쩔수 없나봅니다.

좋아하는 학문이었습니다.

수학을 좋아해서 수학과로 진학을 하였고, 조금 더 공부하고 싶은 마음에 대학원에 진학하게 되었습니다.

하지만 수학을 공부하면서 힘든 점들이 참 많았던 것 같습니다.

상당히 마이너한 분야의 공부를 하면서 물어볼 수 있는 사람이 적었다는 것이 나름대로 힘들었던 것 같습니다

한편으로 제 스스로의 역량을 키울수 있는 기회도 되었지만요.

수많은 증명들을 만나고, 스스로의 머리에 새기면서 이해하려고 보낸 시간들. 

출장을 간다면서 부랴부랴 짐을 싸서 신칸센을 타고 이동하거나 그런 사소한 일상들이 소중했던 것 같습니다.

8평 남짓의 방에서 아침에 일어나서 아카이브를 둘러보며, 턱을 괴고 논문을 읽었던 그러한 나날들이 소중하다는 것을 이제서야 다시 알게 된 것 같습니다.

조금 더 천천히 생각을 곱씹어가면서 글을 더 써보겠습니다.

import math
N,M = map(int,input().split())
A = list(map(int,input().split()))
num = []
for i in range (1,1050):
    if i not in A:
        num.append(i)
m = len(num)
val = 1e9
for i in range (0,m):
    if num[i] ** 3 > N + val:
        break
    for j in range (i,m):
        for k in range (j,m):
            val = min(val, int(math.fabs(N - num[i] * num[j] * num[k])))
print(val)

브루트포스로 계산하지만, 시간을 어떻게 더 단축할 수 있을지가 관건이었던 문제

추가 기재)

import math
N,M = map(int,input().split())
A = list(map(int,input().split()))
num = []
for i in range (1,1050):
    if i not in A:
        num.append(i)
m = len(num)
val = 1e9
for i in range (0,m):
    if num[i] ** 3 > N + val:
        break
    for j in range (i,m):
        if num[i] * num[j] * num[j] > N + val:
            break
        for k in range (j,m):
            val = min(val, int(math.fabs(N - num[i] * num[j] * num[k])))
print(val)

for j 에 있어서도 같이 제한 조건을 넣어줌으로서 훨씬 연산이 빨라진 것을 확인할 수 있었다 !

from collections import deque
N= int(input())
picture1 = [[] for _ in range (0,N)]
picture2 = [[] for _ in range (0,N)]
for i in range (0,N):
    a = list(input())
    for j in range (0,N):
        if a[j] == "B":
            picture1[i].append(a[j])
            picture2[i].append(a[j])
        else:
            picture1[i].append(a[j])
            picture2[i].append("G") #R이 G가 된다고 생각하자.
visited1 = [[False for _ in range (0,N)] for _ in range (0,N)]
visited2 = [[False for _ in range (0,N)] for _ in range (0,N)]

dx,dy = [0,0,1,-1],[1,-1,0,0]
cnt1,cnt2 = 0,0
for i in range (0,N):
    for j in range (0,N):
        if visited1[i][j] == False:
            cnt1 += 1
            deq = deque()
            deq.appendleft([i,j])
            while deq:
                x = deq.popleft()
                visited1[x[0]][x[1]] = True
                for k in range (0,4):
                    a = x[0] + dx[k]
                    b = x[1] + dy[k]
                    if 0 <= a < N and 0 <= b < N and visited1[a][b] == False and picture1[a][b] == picture1[x[0]][x[1]]:
                        deq.appendleft([a,b])
        if visited2[i][j] == False:
            cnt2 += 1
            deq = deque()
            deq.appendleft([i,j])
            while deq:
                x = deq.popleft()
                visited2[x[0]][x[1]] = True
                for k in range (0,4):
                    a = x[0] + dx[k]
                    b = x[1] + dy[k]
                    if 0 <= a < N and 0 <= b < N and visited2[a][b] == False and picture2[a][b] == picture2[x[0]][x[1]]:
                        deq.appendleft([a,b])
print(cnt1,cnt2)

그냥 조오금 복잡할 뻔한 BFS / DFS 유형이었다

from collections import deque
M,N,H = map(int,input().split())
cnt = 0
deq = deque() #다 익은 애들 deq에 넣어서 해결
box = [[[0 for _ in range (0,M)] for _ in range (0,N)] for _ in range (0,H)]
for i in range (0,H): #높이 정보
    floor_box = []
    for j in range (0,N): #가로 정보
        A = list(map(int,input().split()))
        for k in range (0,len(A)):
            box[i][j][k] = A[k]
            if A[k] == 0: #안 익은애들
                cnt += 1
            if A[k] == 1:
                deq.append([i,j,k])
dx,dy,dz = [1,-1,0,0,0,0], [0,0,1,-1,0,0], [0,0,0,0,1,-1]
if cnt == 0:
    print(0)
if cnt != 0:
    day = 0
    while True:
        if cnt == 0:
            print(day)
            break
        if len(deq) == 0:
            print(-1)
            break
        day += 1
        tomato = []
        while deq:
            a = deq.popleft() #list의 형태로 출력됨
            for i in range (0,6):
                z,y,x = a[0] + dx[i], a[1] + dy[i], a[2] + dz[i]
                if 0 <= x < M and 0 <= y < N and 0 <= z < H and box[z][y][x] == 0:
                    box[z][y][x] = 1
                    tomato.append([z,y,x])
                    cnt -= 1
        for i in range (0,len(tomato)):
            deq.append(tomato[i])

3차원인 점을 제외하고는 2차원과 크게 다를 것이 없었다.