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, ..
Algorithm/PS
📚 문제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 형태로 맞춰준다.가장 아래부터 가장 위까지 검사해나간..
📚 문제Lv 2할인은 4 종류 뿐이며 이모티콘의 종류는 최대 7종류 뿐이다.이모티콘 할인 총 경우의 수는 4^7 이므로 충분히 완전 탐색이 가능하다.💡 포인트모든 이모티콘을 할인률을 적용한 값들을 계산한다.이모티콘의 수를 m 이라 했을 때 4^m 번 반복하며 모든 경우에 대해서 계산한다.💻 코드def solution(users, emoticons): discount = [0.6, 0.7, 0.8, 0.9] m = len(emoticons) emoticon_discount = [[0 for _ in range(4)] for _ in range(m)] for i in range(m): for j in range(4): emoticon_discount..
📚 문제Lv 2사실상 택배 배달 문제 두 개를 동시에 진행시키면 된다.택배가 배달갈 때와 돌아올 때 모두 가능한 용량을 가장 먼 곳에서부터 사용하면 된다.이때 배달과 수거 모두에서 가장 마지막 index 번호의 배달이나 수거 양이 0일 경우를 주의하면 된다.즉, 가장 먼 곳에서 cap 개수만큼 배달했으면 배달할 것이 없는 곳들을 모두 제외하고 다음으로 가장 먼 곳에 배달할 것이 있는 index 를 찾아 저장해야한다.💡 포인트처음 시작에 가장 멀리 배달 혹은 수거해야하는 index 를 저장한다.cap 개수만큼에서 가장 먼 배달, 수거부터 진행시키고 다음 멀리 있는 배달, 수거의 index 를 저장한다.이때 가장 멀었던 길이를 answer 에 합한다.배달, 수거하는 index 가 -1 이 될 때까지 반복..
📚 문제Lv 1String 으로 들어오는 날짜를 오늘 날짜로부터 몇 일이 지났는 지 계산해서 저장해야한다.Int 값으로 저장된 날짜들을 month * 28 과 비교해 유효 기간이 지났는 지 살핀다.💡 포인트re 를 사용하여 날짜 입력을 포맷팅하여 받아낸다.모든 날짜들을 today 와 비교해 days 를 계산해 Integer 로 저장한다.약관의 유효기간도 month 가 아닌 day 로 계산해 비교한다.💻 코드import redef solution(today, terms, privacies): pattern = re.compile(r'(\d{4})\.(\d{2})\.(\d{2})') today_day = pattern.findall(today) answer = [] for inde..
www.acmicpc.net/problem/6884 6884번: 소수 부분 수열 각 테스트 케이스마다 가장 짧은 소수 부분 수열의 길이가 x라면 "Shortest primed subsequence is length x:"를 출력하고, 그 수열 공백으로 구분해 출력한다. 가장 짧은 소수 부분 수열이 여러 가지면, 먼저 www.acmicpc.net 정말 오랜만에 알고리즘을 풀어본다. 먼저 문제 자체는 간단하다. 테스트 수 t와 수열의 길이 n 을 입력받아 수열 내부에서 연속적인 인수들의 합이 소수가 되는지 검사하고 가장 짧은 연속 인수들을 찾아내는 것이다. 가장 처음에는 수열의 길이를 받는 것을 보지 못해서 가변함수 등을 찾아봤다. 아래는 입력 개수를 모를때 getc(stdin) 으로 입력을 모두 받은 후 ..
