본문 바로가기

DataScience/백준8

[백준] 1655 가운데를 말해요 (python) 이 문제를 차례대로 숫자가 들어오고 , 그 동안 들어온 값들 중 중위값을 구하는 문제다. 처음에는 이진정렬을 이용해 매번 정렬을 하고, 그 후 중위값을 구해야겠다고 생각했지만 이는 시간을 초과했다. 잘 모르겠어서 찾아보니 heap( 우선순위 queue)를 이용해서 푸는 문제라고 한다. 먼저 우선순위 큐는 이진트리를 이용해 정렬된 값을 가지는 자료구조를 말한다. 🌈 자료구조:: 우선순위 큐(Priority Queue) -> 정리를 잘 해놓은 사이트라 참고하면 쉽게 이해할 수 있을 것이다. 따라서 이 자료구조를 이용하면 $O(log_2 n)$으로 정렬된 자료구조를 사용할 수 있다. 이 문제의 풀이방식의 컨셉은 2개의 heap를 이용하고 왼쪽 heap의 루트노드에 중위값이 오도록 유지하는 것이다. 먼저 lef.. 2023. 6. 21.
[백준] 12865번: 평범한 배낭 평범한 배낭문제는 배낭에 담을 수 있는 최대 무게가 정해져있고, 이 무게를 넘지 않고 물건의 가치의 합이 최대가 되도록 물건을 가방에 담는 문제다. 사실 굉장히 단순한 문제인데 이해하지 못하는 부분이 있어 풀이에 시간이 꽤 걸렸다. 이 문제는 dp(dynamic programming)로 풀 수 있는 문제이다. dp는 큰 문제를 작은 문제로 나눠서 푸는 문제를 말한다. 이를 위해서는 작은 문제가 반복되어야하고, 작은 문제의 최적의 결과를 이용해 큰 문제의 결과를 도출해낼 수 있어야한다. 여기서는 전체 배낭(최대 무게 k)에 전체 물건을 담을 수 있는 경우가 큰 문제에 해당하고, 몇 개의 물건을 작은 배낭(최대 무게 < k)에 담는게 작은 문제에 해당한다. 해당 식은 다음과 같고, ( 현재 물건의 가치+ 현.. 2023. 6. 21.
백준 개발환경에서 테스트 쉽게하기 제출하기 전에 개발환경에서 테스트를 할 때 일일이 input을 입력해줄 수는 없는 노릇이다. 이를 위해 .txt파일에 저장해놓고 불러와야하는데, 제출코드와 테스트코드의 차이가 최대한 없어야 불필요한 과정을 줄일 수 있다. 테스트코드와 제출코드의 차이를 딱 한 줄로 만들 수 있는 방법을 소개한다. from sys import stdin, setrecursionlimit setrecursionlimit(10**6) # 파이썬 최대 재귀깊이 높이기 stdin = open('11726/sample_input.txt', 'rt') # 테스트할 때, 제출할 때는 주석처리 해주기 cnt_dict = {} cnt_dict[1] = 1; cnt_dict[2] = 2 def find_cnt(n: int) -> int: ".. 2023. 6. 11.
[백준] 11726 : 2xn 타일링 1006번 문제를 풀다가 막혀, 해설을 찾아보던 중 11726번의 응용버전이라는 글에 이것부터 풀어보기로 했다. 풀이과정은 다음과 같다. 이 문제의 핵심은 , 현재의 문제가 더 작은 문제들의 합으로 나뉘어진다는 것이다. 즉 , 전체 경우의 수 = 처음에 2x1 타일을 붙였을 때의 경우의 수 + 처음에 1x2 2개 타일을 붙였을 때의 경우의 수, 로 정의된다. 이는 전형적인 DP(Dynamic Programming)문제이다. DP문제를 풀기위해서는 2가지 정의가 필요하다. 1. 점화식 ( 재귀식과 같이 자기 자신의 함수의 합으로 표현되는 식 ) f(n) = f(n-1) + f(n-2)로 정의된다. 이는 피보나치 수열 문제와 완전히 동일하게 된다. 2.기본 상태 정의하기 ( n=1일때와 n=2일 때 ) if.. 2023. 6. 11.
1005번 문제풀이 * 문제 풀이에 필요한 개념 recursive function ( DFS ), list-comprehension, memoization 1005번 문제는 재귀함수를 이용해서 풀 수 있다. 즉 역으로 추적하는 것인데, 큰 컨셉은 다음과 같다. 4번을 마치는데 필요한 시간 = max(2번을 마치는데 필요한 시간, 3을 마치는데 필요한 시간) + 4번에 걸리는 시간 3번을 마치는데 필요한 시간 = max(1을 마치는데 필요한 시간) + 3번에 걸리는 시간 일반화해보면, n번 node를 마치는데 필요한 시간 = max([선행node를 마치는데 필요한 시간]) + n번 노드에 걸리는 시간 이러한 풀이방식을 DFS (Depth-First-Serch) , 깊이우선탐색이라고 부른다. 4번노드 -> 2번노드 -> 1번노.. 2023. 6. 9.
1004번 문제풀이 배1004번 문제는 출발점에서 도착점까지 가는 길에서 행성에 진입/이탈하는 최소 횟수를 구하는 문제다. 문제 풀이과정은 다음과 같다. 이 문제의 핵심은 거리는 최소가 아니라는 점에 있다. 따라서 출발점과 도착점이 같은 원 안에 위치하는지가 중요하다. 즉 둘 중 하나만 원 안에 있으면 +1 이되고, 그렇지 않은 경우는 모두 0이 된다. 이를 구현한 코드는 다음과 같다. def check_InOrOut(point: tuple, planet:tuple): x, y = point a, b, r = planet d = ((x - a) ** 2 + (y - b)**2) ** 0.5 if (d > r): return False else: return True N = int(input()) for _ in range(.. 2023. 6. 9.
1003번 문제풀이 피보나치 수열에 대한 문제이다. recursive function(재귀함수), memoization, tuple, dict의 개념이 사용되었다. 풀이과정은 다음과 같다. memo_dict = {} memo_dict[0] = (1, 0) memo_dict[1] = (0, 1) def fibo(n: int): if (n in memo_dict.keys()): return memo_dict[n] else: result = (fibo(n-1)[0] + fibo(n-2)[0] , fibo(n-1)[1] + fibo(n-2)[1]) memo_dict[n] = result return result n = int(input()) for i in range(n): result = fibo(int(input())) pri.. 2023. 6. 8.
1002번 문제풀이 이 문제를 보면 결국 두 원 사이의 위치에 대한 문제이다. 한 좌표와 거리 안에 존재할 수 있는 점은, 원으로 표시되기 때문이다. 이에 대해 다음과 같이 풀어봤다. 그리고 이를 구현한 코드는 다음과 같다. N = int(input()) for _ in range(N): x1, y1, r1, x2, y2, r2 = map(int, input().split()) d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 if (x1==x2 and y1==y2 and r1==r2): print(-1) elif (d == r1 + r2 or d == max(r1,r2) - min(r1, r2)): print(1) elif (d < r1 + r2 and max(r1, r2) < d + min.. 2023. 6. 8.

티스토리툴바