전체 글

1일 1PS 35일차!📚 문제Lv 1MBTI 처럼 각 유형에 대한 질문이 정해져있고 질문에 대한 답으로 유형에 대해서 +- 계산해 판단할 수 있다.예를 들어 AN 에서 1을 골랐다면 N 형에 3점을 주고 NA 에서 1번을 골랐다면 A 형에 2점을 주는 것을 (+3) + (-2) 로 AN 의 유형이 양수이므로 N 형으로 판단하는 것이다.💡 풀이과정survey 가 어떤 유형에 속하는 지, 또한 정방향 유형인지 판단한다.유형값을 저장하는 ch 배열에 응답값들을 더한다.총 합이 양수인지 음수인지 판단해 유형값을 출력한다.💻 코드def solution(survey, choices): answer = "" # RT, CF, JM, AN form = ['RT', 'CF', 'JM', 'AN'] ..

Lv 4처음부터 어떤 숫자를 떨어트릴 지 정할 수 없다.몇 개의 숫자가 떨어질 지 정한 후 이를 통해 어떤 숫자를 떨어트렸는 지 파악한다.💡 풀이과정단방향 graph 를 저장하고 각 노드들이 현재 가르키고 있는 graph_path 를 배열로 저장한다.root 노드부터 graph 를 따라 이동하며 해당 node 를 이동할 때 graph_path 를 +1 한다. 당연히 마지막에 도달하면 0으로 돌아간다.child 가 없는 노드라면 count 에 저장하고 모든 count 수만큼 1, 2, 3 을 조합해서 목표값이 만들어진다면 루프문을 멈춘다.current_node 로 노드에 떨어진 순서를 저장하고 각 모든 노드의 1, 2, 3 조합을 사전 순서대로 구한다.current_node 를 각 노드에서 조합한 1, ..

📚 문제Lv 3사전 순으로 가장 빠른 경로를 찾고 있다는 뜻은 이동 순서에 우선순위가 있다는 뜻이다.d l r u 순으로 우선순위를 가진다.dfs 에서는 Stack 에 가장 마지막에 넣는 것이 가장 높은 우선순위를 가진다.dfs 도중에 남은 움직임으로 도착지에 도착할 수 없는 경우는 도중 삭제한다.💡 풀이과정d - l - r - u 순으로 우선순위를 가지기에 이를 반대 배열로 만든다.stack 에 반대 배열을 순회하며 u - r - l - d 순으로 push 되도록 한다.dfs 중 도착지 거리를 계산해 거리가 남은 이동보다 크다면 continue 한다.💻 코드def solution(n, m, x, y, r, c, k): dx = [-1, 0, 0, 1] dy = [0, 1, -1, 0] ..

📚 문제Lv 3MERGE 와 UNMERGE 가 핵심이며 이를 위해 DSU 알고리즘을 사용했다.DSU 알고리즘은 Union Find 이다.2차원 배열을 1차원으로 변환하여 Union 시킨다.DSU 알고리즘에서는 Find 후에 가장 Parent Node 를 사용해서 다른 Node 들을 Union 해야한다.💡 풀이과정re 를 사용하여 커맨드를 분리한다.MERGE 시 Union 한다.UNMERGE 시 해당 값으로 Union 된 모든 노드들을 초기화한다.💻 코드import reclass DSU: def __init__(self): self.par = [n for n in range(2501)] def find(self, x): if self.par[x] != x: ..

📚 문제Lv 3이진트리를 만들고 아래에서부터 검사해나가면 된다.실제 이진트리를 만들었을 때,1 or 3 이 존재하면 2 가, 5 or 7 이 존재하면 6이 존재해야한다.2 or 6 이 존재하면 4가 존재해야한다.가장 아래단부터(1, 3), (5, 7), (7, 9) ...홀수 두 개씩 검사하며 둘 중 하나가 1일 경우 둘의 평균값인 짝수도 1이어야한다.아래에서 두 번째는(2, 6), (10, 14) ...4 차이를 두고 검사한다.결국 단이 올라갈 수록 2의 거듭제곱의 차이만큼 검사해야하며, 시작하는 값 또한 1, 2, 4 .. 등 2의 거듭제곱이다.💡 풀이과정숫자를 2진수로 변환한다.변환된 2진수를 이진트리를 검사할 수 있도록 길이를 2^n - 1 형태로 맞춰준다.가장 아래부터 가장 위까지 검사해나간..