본문 바로가기
728x90

백준7

[백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 행렬 곱셈 순서에 따라 곱셈의 횟수가 달라진다. 행렬이 주어졌을 때 다이나믹 프로그래밍(DP)를 이용하여 곱셈 횟수의 최솟값을 구하는 문제이다. 뭔가 어려운 포인트들이 많아 한 번 정리해두면 좋은 문제이다. https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 생각 포인트 이 문제에서 중요한 포인트는 3가지 정도 있다. i 번 째 행렬의 행은 i-1 번 째 행렬의.. 2021. 9. 1.
[백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 다이나믹 프로그래밍 대표 문제인 LCS 문제를 풀어봤다. LCS(Longest Common Subsequence)는 최장 공통 부분 문자열로 다이나믹 프로그래밍의 대표적인 문제이다. 문자열 출력까지 포함하는 9252번 문제를 풀어보았다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 생각 포인트 다이나믹 프로.. 2021. 8. 27.
[백준_11279] 우선순위 큐, 최대 힙 [백준_11279] 우선순위 큐, 최대 힙 최대 힙을 이용해 원하는 값을 출력하는 우선순위 큐 문제를 풀어보았다. 내 코드 - 모듈 없이 do it! 책대로 풀었는데 시간초과가 떳다.... 남들은 더 간단하게 했는지 input()만 sys.stdin.readline()으로 고쳐주면 통과 된다는데 이 방식으론 통과가 안된다. 그래서 옆에 친구한테 물어보니 모듈을 쓰면 된단다 =.=;; 그래도 원리 이해한 거에 의의를 두는 걸로 import sys def heap_sort(a): def down_heap(arr, left, right): # left : 기준, right가 n-1 가장 마지막 leaf tmp = arr[left] parent = left #left 뺴고 다 heap 구조 가정 while pa.. 2021. 8. 16.
[백준_2470] 중, 이분 탐색, 두 용액 [백준_2470] 중, 이분 탐색, 두 용액 산성 용액과 알칼리성 용액은 각각 양수와 음수의 특성값을 가지고 있다. 두 용액을 섞어 0에 가깝게 만들려고 할 때, 용매 각각의 특성값을 출력하는 문제이다. 이 문제는 처음에도 그렇고 풀고 나서도 그렇고 이분 탐색인지 직관적으로 와닿지 않는다는 게 어려웠다. 처음에 '이전의 start와 end의 합'과 'start index +1', 'end index -1'일 때 각각과 비교해 차이가 더 작은 방향으로 움직여야 한다고 생각했다. 그런데 이렇게 했을 때 문제는 [-95, -4, 3, 100]과 같은 경우 답이 -95, 100으로 출력된다는 점이다. 문제를 푸는 핵심 포인트는 정렬 후 양쪽에서 0의 방향으로 진행하는 부분(이진 탐색) 합이 양수인지 음수인지에 .. 2021. 8. 13.
[백준_2110] 중, 이분 탐색, 공유기 설치 생각 포인트 가장 인접한 두 공유기 사이의 최대 거리를 구해야 하므로 N개의 집의 양 끝에는 공유기가 무조건 설치된다. 그 다음 공유기 설치 위치는 좌표적으로 1번째와 N번째 공유기 중간에 가장 가까운 곳에 위치해야 한다. (순서상 중간이 아니다) 이 부분이 이진 탐색과 연결이 된다. 그럼 중간 좌표와 가장 주변 집의 좌표들 차이의 최솟값을 구해 최소가 되는 지점의 index에 공유기를 설치한다. 그 다음 공유기는 방금 설치한 공유기를 기준으로 1번째와 N번째 공유기 위치와의 거리 중 긴 곳 영역에 설치된다. 이후 반복. 이란 생각으로 풀었는데, 완전 오답 풀이였다.... 일단 이 방식은 딱 중간 가까운 공유기를 설치하기 때문에 공유기 개수가 짝수일 경우에는 오답이다.. 정답 코드를 작성하기 위한 핵심은.. 2021. 8. 13.
[백준_2805] 하, 이분 탐색, 수 찾기 [백준_2805] 하, 이분 탐색, 수 찾기 이분 탐색(Binary Search) 절단기의 높이를 차례대로 높이는 알고리즘으로는 시간 초과가 발생한다. 이 때 사용할 수 있는게 Binary Search(이분 탐색 or 이진 탐색)을 이용해야 한다. 이진 탐색이란 찾고자 하는 target 값을 오름 차순으로 정렬된 list에서, target값과 list의 중간값 비교를 통해 진행된다. 만약 중간값보다 target이 크면 검색 범위를 중간값 이상의 범위에서 다시 찾기 시작한다. 이 때 중간값은 하기와 같은 새로운 중간값을 이용한다. 첫 번 째 코드 import sys input = sys.stdin.readline from typing import Any, Sequence def bin_search(woo.. 2021. 8. 12.
728x90

티스토리툴바