알고리즘20 백준 2644번 촌수계산 파이썬 풀이 사실 문제를 봤을때 촌수를 계산하라지만 노드간의 부모가 하나뿐인 전형적인 그래프라서 bfs를 돌리면 풀수 있겠단 생각이 들었어요 근데 이것이 코딩테스트다에서 find_parent를 이용해 푸는 문제를 봤던 생각이 나서 처음엔 부모 경로를 찾아서 만나는 경로의 거리를 찾는식으로 작성했었는데 n = int(input()) a, b = map(int, input().split()) d = [i for i in range(n + 1)] for _ in range(int(input())): x, y = map(int, input().split()) d[y] = x def findParent(n, depth, path): if n == d[n]: return n, depth path.append(n) return .. 2021. 3. 19. 백준 1094번 막대기 파이썬 풀이 처음 문제를 보고 구현하는 방법이 그대로 적혀있길래 쓰인대로 구현해서 통과했었는데, 1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 이 부분을 가장 짧은걸 자르라길래 우선순위 큐를 이용해서 구현했었습니다 import heapq target = int(input()) heap = [64] while sum(heap) != target: splited = heapq.heappop(heap) // 2 if splited < 1: continue heapq.heappush(heap, splited) if not target < sum(heap): heapq.heappush(heap, splited) print(len(heap)) 그래서 이렇게 코드를 짜서 통과했는데 코드를 보니까 어차피 힙에.. 2021. 3. 13. 백준 1292번 쉽게 푸는 문제 파이썬 풀이 이름 그대로 단순하게 반복을 돌면서 수열을 진짜로 만든후에 입력된 A부터 B구간을 수열에서 잘라 합을구하면 됩니다 구현하는데는 3가지 방법이 있었습니다 1. 1부터 45까지 더하면 B의 최대범위인 1000을 넘는 1035이기 때문에 반복문을 무조건 45번 돌아서 모든 수열을 만드는 방법 2. 반복문을 돌면서 수열을 만들때마다 수열의 길이를 체크해 B를 넘어가면 종료하는 방법 3. 제너레이터 함수를 만든 후에 itertools에 있는 islice함수를 사용해 원하는 구간만 잘라 더하는방법 만약에 3번으로 푼다면 코드는 이렇게 나오는데 from collections import deque from itertools import count, islice def sequence(): que = deque() c.. 2021. 3. 12. CodeSignal 17번 arrayChange 문제풀이 def arrayChange(inputArray): cnt=0 for i in range(len(inputArray)-1): if inputArray[i]>=inputArray[i+1]: cnt+=inputArray[i]-inputArray[i+1]+1; inputArray[i+1]=inputArray[i]+1 return cnt 2020. 2. 3. 이전 1 2 3 4 5 다음
