본문 바로가기

분류 전체보기

 (224)
[python] 10986 - 나머지 합 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 부분합 문제이다. 이전까지의 부분합 개념을 이용하여 풀려고 했는데 계속 런타임 에러가 났다. 도저히 방법을 찾을 수가 없어 다른 풀이를 참고하여 해결하였다. 참고 사이트 : [파이썬] 백준 10986번 나머지 합 (tistory.com) 수학적 지식이 필요했는데, 간단하게 말하면 부분합을 구한 후 m으로 나누었을 때의 나머지가 동일한 구간을 찾으면 된다. 쉽게 이해하..
[TIL] knapsack 알고리즘 (배낭 문제) knapsack problem - 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값은 정해져 있고 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 넣을 짐을 고르는 방법을 찾는 문제 냅색 알고리즘은 물건 분할 유무에 따라 분할 가능한 문제와 0-1 문제로 나뉜다. 여기서 다룰 문제는 0-1 냅색 알고리즘으로 백준 12865 문제를 풀다가 접하게 되었다. 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,0..
[TIL] LCS 알고리즘 (최장 공통 부분 수열) 최장 공통 부분 수열(LCS, Longest Common Subsequence) - 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 수열 LIS 문제와 비슷한데 LCS는 수열 2개가 주어진다. 9251번: LCS (acmicpc.net) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 위 문제를 예시로 들어 수열 ACAYKP와 CAPCAK를 가지고 표를 만들어 보았다. 이 때, 두 가지 경우를 고려해야 하는데 1. 같은 알파벳인 경우 2. 알파벳..
패스트캠퍼스 Python 코딩테스트 강의 1주차 이번 강의에서는 백준 2920 문제와 2798번 문제를 학습하였다. 1. 2920 2920번: 음계 (acmicpc.net) 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 이번 문제에서의 핵심은 2가지다. 1. 리스트에서의 원소를 차례대로 비교하는 것 2. 비교 시 원소의 오름차순과 내림차순 여부를 체크하는 것 이 두가지를 비교하며 오름차순과 내림차순의 값을 각각 False와 True를 사용하여 변경한다. 코드는 아래와 같다. a = list(map(int, inpu..
[TIL] LIS 알고리즘 (최장 증가 부분 수열) 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) - 원소가 n개인 배열의 일부 원소로 만든 수열 중 각 원소가 이전의 원소보다 크며 길이가 최대인 부분 수열 백준 dp 알고리즘을 풀다가 LIS 알고리즘을 접하게 되었다. LIS를 푸는 방법으로는 DP를 이용한 방법과 이분탐색 방법 두 가지가 있다. 1.DP를 활용 [1,3,2,7,6,4,9,8] 이라는 배열 lst가 존재할 때 dp 리스트를 사용하여 각 인덱스별로 최장 증가 부분 수열의 길이를 구한 것이다. lst =[1,3,2,7,6,4,9,8] dp=[1]*len(lst) for i in range(len(lst)): for j in range(i): if lst[i]>lst[j]: dp[i] = max(dp[i..
[python] 2447 - 별 찍기 2447번: 별 찍기 - 10 (acmicpc.net) 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 별이라던가 도형찍는 문제는 아주 초반부터 자주 접했는데.. 다른 방식으로 나올 때마다 헷갈려 죽겠다. 언제쯤 익숙해질지 모르겠다. 이번에는 재귀를 사용해서 풀어야 하는 문제인데 접근법을 아예 찾지 못해 한참을 해매다가 결국 다른 분의 풀이 방법을 참고하였다 ㅠㅠ * 참고 블로그 : [백준] 2447 - 별 찍기 - 10 [Python(파이썬)] — TaxFree (tistory.c..
[python] Tree 순회하기 1. python으로 트리를 구현할 때 dictionary를 사용하여 루트노드와 left, right를 저장한다. 2. 전위/ 중위/ 후위 순회는 재귀함수로 코드의 순서를 바꿔 구현한다. 다음과 같은 이진트리가 존재할 때 각각 전위/중위/후위 순회를 해본다면 다음과 같다. 1. 전위순회 : [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회 A - B - D - G - C - E - F 2. 중위순회 : [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회 G - D - B - A - E - C - F 3. 후위순회 : [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회 G - D - B - E - F - C - A python으로 트리 순회 구현 1991번: 트리 순회 (acmicpc.net) 1991번..
[python] heapq 파이썬의 heapq 모듈은 우선순위 큐 알고리즘의 구현을 제공한다. 따라서 heapq를 사용하여 최소힙과 최대힙을 구현할 수 있다. heappush(heap, item) 힙의 조건을 유지하며 item을 heap으로 push한다. heappop(heap) 힙의 조건을 유지하며 heap에서 가장 작은 item을 pop하고 반환한다. heap이 비어있다면 IndexError가 발생한다. 최소 힙 heapq는 기본적으로 최소 힙을 구현한다. 백준에 최소 힙을 구현하는 문제가 있어 적용하여 보았다. 1927번: 최소 힙 (acmicpc.net) 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가..
728x90

티스토리툴바