본문 바로가기

0

 (102)
백준 2042번 구간 합 (Python) 세그먼트 트리 (Segment Tree)배열 A가 있고 다음과 같은 두 연산을 수행해야하는 문제를 생각해보자.1. 구간 l, r이 주어졌을 때, A[l] + ... A[r] 구해서 출력하기2. i번째 수를 V로 바꾸기. A[i] = v수행해야하는 연산은 최대 M번이다.다른 방법을 사용하지 않고 문제를 푼다면, 1번 연산을 수행하는데 O(N), 2번 연산을 수행하는데 O(1)이 걸린다.총 시간 복잡도는 O(NM) + O(M) = O(NM)이 나오게된다. 2번 연산이 없다고 생각해보자.수를 바꾸는 경우가 없기 때문에, 합도 변하지 않는다. 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀 수 있다.S[i] = A[1] + ... + A[i] 라고 했을 때, i~j까지의 합은 S[j] - S[i-1]이 된..
백준 1620번 나는야 포켓몬 마스터 이다솜 (Python) 문제포켓몬의 수 N, 내가 맞춰야하는 문제의 수 M.N개의 줄에 포켓몬의 이름이 입력으로 들어옴. 그 다음 줄부터 M개의 줄에 맞춰야하는 문제가 입력으로 들어옴.숫자로 들어오면 포켓몬 번호에 해당하는 문자 출력. 알파벳으로 들어오면 포켓몬 번호 출력. 풀이문제는 쉬운것 같은데 정답 비율이 낮아서 '함정이 있는건가..' 하는 생각이 들었다. 혹시나가 역시나.처음에는 단순히 python의 내장 라이브러리 함수들을 이용해서 출력하는 방식으로 풀었다. (.index() or .get())아니나 다를까 계속해서 시간초과 ㅠㅠㅠㅠㅠ결국에는 이진 탐색을 이용해서 풀고 제출했다. 하지만 내가봐도 너무 지저분하다.. 1234567891011121314151617181920212223242526272829303132333..
백준 9184번 신나는 함수 실행 (Python) 문제에 점화식까지 쓰여있어서 당황스러웠다..너무나도 당연하게 문제에 쓰여져있는대로 코드를 작성하면 안된다!재귀함수를 사용해야할 때 이것을 메모이제이션 하는 방법을 묻는 문제이다. 12345678910111213141516171819202122232425262728MAX = 21dp = [[[0]*MAX for _ in range(MAX)] for __ in range(MAX)] def w(a, b, c) : if a20 : return w(20, 20, 20) # 값이 이미 존재한다면 그 값을 바로 리턴. if dp[a][b][c]: return dp[a][b][c] if a
백준 1992번 쿼드트리 (Python) 진작에 알고리즘 공부 좀 열심히 좀 할걸! 오늘도 반성반성... 문제 모두 0이나 1로 되어있으면 압축 결과는 0이나 1, 0과 1이 섞여 있으면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 된다. 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.NXN 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 영상의 크기를 나타내는 숫자 N이 주어짐. N은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진. 두 번째 줄부터는 길이 N의 문자열이 N개 들어옴. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타냄. 출력 영상을 압축한 결과를 출력해라. 풀이 다양한 ..
하노이의 탑 (Python) 컴퓨터공학과 1학년이라면 누구나 이 탑을 만나봤을 것이다.1학년 때 알코올로 뇌를 적셔서 기억이 하나도 없는 관계로 이 포스팅을 계기로 한번 정리해보고자한다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 1. 한번에 하나의 원판만 옮길 수 있다.2. 큰 원판이 작은 원판 위에 있어서는 안된다. 이 그림을 보면 쉽게 이해할 수 있다. 이 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 일반적으로 원판이 n개 일 때, 번의 이동으로 원판을 모두 옮길 수 있다. 자, 그럼 어떻게 옮겨야할까? 문제를 유심히 보면 다음 과정이 반복되는 것을 알아챌 수 있다. 1. A에 있는 n-1개의 원판을 C를 이..
합병 정렬 (Merge sort) 정의 합병 정렬 또는 병합 정렬 (merge sort)는 O(nlogn) 비교 기반 정렬 알고리즘이다. 이 정렬은 분할 정복 알고리즘의 하나로, 존 폰 노이만이 1945년에 개발했다. * 비교 정렬은 하나의 추상적인 비교 동작을 통해 목록 요소들을 읽어내는 정렬 알고리즘의 일종으로, 두 요소 중 어느 것이 최종 정렬 목록에 발생되어야 하는지를 결정한다. 알고리즘 1. 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 소스코드 def mergeSort(X) : if le..

티스토리툴바