helloahram

1. 문제두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다예를 들어, ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다 2. 요구사항시간 제한 0.1초메모리 제한 256MB 3. 알고리즘 분류* 다이나믹 프로그래밍* 문자열 4. 접근 방식 ㄷㅎ님이 기깔나게 설명해 주신 LCS 알고리즘을 이용하여 풀었다 LCS 알고리즘 정리한 내용 문제에서 문자열 A "ACATKP" 과 문자열 B "CAPCAK" 을 비교한 내용을 표로 정리하면 아래와 같다  0ACAYKP00000000C0011111A0112222P0112223C0122223A0123333K0123344 0 인 행렬을 추가한 이유는 비교 과정에서 대각선 +1 과 왼쪽/ 위쪽 비교를 위해서 추가했고,그렇기 때..

LCS 알고리즘Longest Common Subsequence 최장 공통 부분 수열 또는 Longest Common Substring 최장 공통 부분 문자열  Longest Common Substring두 개 이상의 문자열에서 연속적으로 나타나는 가장 긴 부분 문자열 찾기 부분 문자열은 주어진 문자열의 연속된 부분을 의미한다원래 문자열에서 특정 시작 위치에서부터 특정 끝 위치까지의 모든 문자를 포함한다이는 문자들이 연속적으로 이어져 있어야 하며, 반드시 전체 문자열의 일부분이어야 한다ex. 문자열 abcde 에서 bcd 는 부분 문자열이지만 acd 는 부분 문자열이 아니다 Longest Common Substring 찾는 방법 1. 문자열 A, 문자열 B 를 한 글자씩 비교해 보기2. 두 문자가 다르다면..

1. 문제계단에 쓰여 있는 점수가 주어질 때 점수의 최댓값 구하기1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다3. 마지막 도착 계단은 반드시 밟아야 한다2. 요구 사항* 계단의 개수는 300 이하의 자연수 * 계단에 쓰여 있는 점수는 10,000 이하의 자연수 3. 알고리즘 분류* 다이나믹 프로그래밍 4. 접근 방식계단을 올라가는 것만 생각하지 말고, 이미 올라간 상태에서 이전에 내가 어떤 계단을 밟고 올라올지를 생각하는 방식으로 접근한다1) 직전 계단 (n-1) 을 밟고 올라온 경우는 세번 연속 계단을 오를 수 없으므로 그 이전 계단은 n-3 번째 계단이다2) 두 칸 전 (n-2) 계단을 밟고 올라온 경우  i 번째 계단까지 올라왔을 때까지의..

그리디 알고리즘 Greedy Algorithm 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 알고리즘 설계 기법 항상 최적의 값을 보장하는 것이 아니라 최적의 값에 '근사한 값'을 목표로 한다  예시) 경로1 이 [ 1 - 1 - 1 - 100 ] 이고 경로2 가 [ 3 - 10 - 3 - 10 ] 일 때경로1 에서는 첫 세 단계에서 최적의 답을 선택했지만 최종 가중치는 103이고경로2 에서는 각 단계에서의 선택이 더 나은 결과를 가져와 최종 가중치가 더 작아진다이 때 경로1 에서의 선택이 그리디 방법론의 예시 그리디 알고리즘 주요 속성탐욕 선택 속성 Greedy Choice Property각 단계에서 '최선의 선택' 을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 ..

Week03 기간 2024.09.27 FRI - 10.03 THU 조원 ㅎㅇ ㅅㅈ  1. 문제 풀이No문제 알고리즘 분류난이도진행 여부 12748 피보나치수2동적 프로그래밍하진행21904 01타일동적 프로그래밍하진행39084 동전동적 프로그래밍중 49251 LCS동적 프로그래밍중진행512865 아주 평범한 배낭 동적 프로그래밍중 611049 행렬 곱셈 순서동적 프로그래밍중 711053 가장 긴 증가하는 부분 수열동적 프로그래밍중 82098 외판원 순회동적 프로그래밍상 92253 점프동적 프로그래밍상 1011047 동전 0그리디하 111541 잃어버린 괄호그리디하 121931 회의실 배정그리디중 131946 신입사원그리디중 141700 멀티탭 스케줄링그리디상 159249 최장 공통 부분 문자열도전?상   ..

1. 문제2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오 2. 요구사항시간 제한 1초메모리 제한 256 MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식이것도 n = 7 까지 모든 경우의 수를 계산해 봤는데 아니나 다를까 피보나치였고n= 1 는 1, n = 2 는 2 를 초기값으로, n = 3 이상은 n-1 과 n-2 합으로 계산했다4. 코드 구현# 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 # 10,007 로 나눈 나머지를 출력한다 # 1

1. 문제00과 1로 이루어진 타일을 붙여 길이가 n인 모든 2진 수열의 개수를 구하고그 값을 15746로 나눈 나머지를 출력하는 문제 2. 요구사항시간 제한 0.75초 메모리 제한 256MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식처음에는 n = 7 까지 모든 경우의 수를 계산해 봤는데, 알고보니 피보나치 수열이었다그리고 같은조 ㅎㅇ님이랑 얘기하며 알게된 내용인데, 아래와 같은 사실을 알게 되었다1) 타일은 00 과 1 로 구분할 수 있다2) 그래서 n == 3 이상일 때◻️◼️◼️ 한 칸만 비어있는 경우는 빈 칸에 1 이 들어가고 ◻️◻️◼️ 두 칸이 비어있는 경우는 빈 칸에 00 이 들어간다고 생각하면n == 3 이상 일 때는 n-1 과 n-2 의 합이다(◻️◼️◼️ / ◼️◼️◻️..

1. 문제n 이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), 0  2. 알고리즘 분류* 수학* 다이나믹 프로그래밍 3. 접근 방식n 이 90까지라서 재귀로 풀면 시간 초과가 뜬다는 말을 듣고,어제 공부했던 Dynamic Programming 의 메모이제이션을 활용하여 구현해 보았다메모이제이션 - 이전 결과 값을 저장하여 중복 계산을 피하는 것  4. 코드 구현 def fibo(n): if n

추석이 끝나고 시작한 Week02, 알고리즘 2주차가 끝났다 목요일 시험이 끝나고 여기저기서 시끌벅적했지만 나는 기운이 나질 않았다 Week02 는 뭔가 아쉬움이 남았던 주차였다 회고 Keep 좋았거나 계속 유지할 것1. 러닝 실력이 성장하고 있다 + 푸시업, 스쿼트 시작09/11 WED 난생 처음 러닝을 시작했을 땐 4바퀴 1.7km 를 겨우겨우 뛰었는데, 09/18 WED 에는 5바퀴 도전에 성공했고 09/26 THU 에는 6바퀴 2.50km 를 뛰었다 이번주에는 월화수목금토 러닝을 했고, 그 중 4일은 6시a.m.에 일어나 뛰었다 밤이 길어지면서 눈도 안 떠지고 몸도 너무 무거웠지만, 막상 나가서 칭구들과 같이 스트레칭을 하고 뛰면서 땀흘리면, 상쾌하고 기분도 좋다 그리고 저녁에는 월수금 푸시업 +..

다이나믹 프로그래밍 Dynamic Programming, DP복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다, '기억하며 풀기' 1. 알고리즘 기법문제를 해결하기 위해 사용되는 절차적인 방법 또는 계획2. 알고리즘 설계 기법문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식 다이나믹 프로그래밍 사용 조건Overlapping Subproblems 겹치는 부분 문제DP 는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구하기 때문에동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다 Optimal Substructure 최적 부분 구조 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 ..