본문 바로가기

자료구조 & 알고리즘 & cs

 (88)
[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. 알파벳..
[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] 백준 1629번 - 곱셈 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 자체는 어렵지 않았다. 물론 이해하는 데만 어렵지 않았다. 분할정복을 이용해 풀어야 했기 때문에 대체 어떻게 접근해야 하는 것인지 모르겠어서 애를 먹었고 결국 다른 풀이를 참고하여 이해할 수 있었다. 지수법칙만 알면 간단하게 풀 수 있다. 문제의 예제인 [10, 11, 12]를 예로 들자면 10**11%12는 10**5*10**6%12와 같이 나눌 수 있다. 마찬가지로 계속해서 지수법칙을 사용하여 나누면 계산해야 할 횟수가 줄어든다. a,b,c = map(int, input()...
[python] 백준 11660번 - 구간 합 구하기 5 11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준 단계별 알고리즘의 누적합 카테고리에 있는 문제이다. 처음에는 누적합을 쓰는 것이 익숙하지 않았는데 이젠 나름 잘 적용하는 것 같다. 표의 크기와 수가 주어지면 구간합을 구하는 문제인데 처음에는 문제를 잘못 이해해서 테스트 케이스는 통과하였으나 오답처리되었다. 예를들어 4*4인 표에서 (2,2)부터 (3,4)까지의 구간합을 구한다고 친다면 (2,2), (2,3..
[python] 백준 2559번 - 수열 2559번: 수열 (acmicpc.net) 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 누적 합 문제이다. 처음에 for문을 두번 돌려서 답은 나왔는데 계속 시간제한이 걸렸다. 첫 인덱스부터 더해가며 누적 합을 구하는 것도 아니었기 때문에 어떻게 누적합 리스트를 만들 수 있을까 고민하였지만.. 결국 다른 해설을 보고 이해했다. 다시 해결한 방법은 다음과 같다. import sys input = sys.stdin.readline n,k = map(int, input().split()) lst=[..
[TIL] 최단 경로 알고리즘 - 다익스트라 최단 경로란? 두 노드를 잇는 가장 짧은 경로를 찾는 것 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 특정 노드에서 출발하여 또 다른 특정노드에 도착하는 가장 짧은 경로를 찾음 그래프 내의 특정 노드에 대해 다른 모든 노드 각각에 대한 가장 짧은 경로를 찾음 ex) 다익스트라 그래프 내의 모든 쌍에 대한 최단 경로를 찾음 다익스트라 알고리즘 최단 경로 알고리즘 중 하나로 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 알고리즘 인접한 정점들의 거리를 계산하여 최단 거리로 갱신 BFS와 비슷 다익스트라 알고리즘 이해 우선순위 큐를 사용 (최소힙) -> 가장 낮은 우선순위를 가진 노드를 pop 각 정점까지의 거리를 계산하는 배열과 인접노드와 그 거리를 비교하는 우선순위 ..
[python] 백준 5430 - AC 5430번: AC (acmicpc.net) 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 파이썬의 deque를 활용하는 문제였다. 그런데 처음에 계속 시간초과가 나서 코드를 수정하였고 이후로는 답이 틀렸다고 나와서 또 코드를 수정하였다. 간과한 점이 있었는데 문제를 꼼꼼하게 고민해보는 습관을 좀 길러야 할 것 같다. 이 문제를 풀면서 주의해야 할 점은 1. R이 두번 나올 경우 역순의 역순 즉, 원래 상태와 비슷하기 때문에 R의 개수를 세어서 짝수인 경우는 굳이 역순으로 바꿔줄 필요가 없다. 2. D를 수행할 때 배열에 아무것도 들어가 있지 않는다면 error를 ..
728x90

티스토리툴바