본문 바로가기
반응형

Computer Science/Algorithm21

[알고리즘/파이썬] 세그먼트 트리 segment tree 세그먼트 트리는 언제 쓰나? 배열과 같은 자료형에서 특정 구간에 속한 원소들의 연산(합, 최솟값, 최댓값 등)을 알아볼 때 선형 탐색보다 좀 더 효율적인 탐색이 가능하다. 그럼 누적합이랑 비슷한거 아닌가? 합만을 알려주는 누적합보다 좀 더 폭넓게 활용이 가능하다. 특히 특정 데이터가 변경되었을 때 누적합은 O(N)으로 누적합 데이터를 업데이트해줘야 하지만, 세그먼트는 O(logN)에 특정 데이터 변경을 반영할 수 있다. 사실 알고리즘보다는 자료구조에 가깝다. 대략 아래의 그림처럼, 어떤 배열이 존재할 때 세그먼트 트리는 그 배열의 특정 구간에 대한 정보를 추가로 담고 있게 된다. 이해가 안되면 그림을 보면 된다. 아래의 그림에서 트리의 루트 노드는 0~8번 데이터를 포함하는 정보를 담고 있다. 예를 들어.. 2022. 3. 27.
[알고리즘] 부분합, 누적합 (Prefix Sum) 쉽게 알아보기(파이썬) 부분합, 누적합이라고 불리우는 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있게 해주는 스킬이다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 부분합을 이용하면 모든 부분합을 O(1)에 바로바로 구할 수 있다. 1차원 배열 - 직관적으로 매우 쉽게 이해가 가능하다. arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. sum[i]에는 arr[0] + arr[1] + ... + arr[i-1]의 정보가 담겨 있다고 생각하면 된다. - 활용법 arr의 i항부터 j항까지의 합을 S(i, j)라고 하자. 이때 S(i, j) = sum[j+1] - sum[i]이다. 2차원 배열 - 2차원 배열도 같은 방식이다. arr을 순차 탐색하면서 sum.. 2022. 3. 25.
[알고리즘] 증가하는 최장 부분 수열(LIS) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS라는 명칭으로 잘 알려진 문제다. 결론부터 얘기하면 DP로 접근하여 풀 수 있다. 아래는 나의 답안 코드다. n = int(input()) nums = list(map(int, input().split())) lst = [0 for _ in range(n)] for i in range(n): max_val = 0 .. 2021. 11. 12.
[알고리즘] 비트마스킹 - 파이썬 비트마스킹을 활용하여 원소의 개수 n이 주어질 때 모든 조합의 경우의 수를 구할 수 있다. n = 4 for i in range(1 2021. 9. 9.
파스칼 삼각형(조합) nCr = n-1Cr-1 + n-1Cr n, r = map(int, input().split()) dp = [[1]*(i+1) for i in range(n+1)] for i in range(2, n+1): for j in range(1, i): dp[i][j] = dp[i-1][j-1]+dp[i-1][j] print(dp[n][r]) # nCr 2021. 9. 2.
[알고리즘 algorithm] LCS에 대하여 LCS : Longest Common Subsequence 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열에 해당하는 수열 중 가장 긴 수열을 의미한다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net a = input() b = input() dp = [[0]*(len(b)+1) for _ in range(len(a)+1)].. 2021. 8. 15.
반응형

티스토리툴바