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각 단계에서 '최선의 선택' 을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 ..

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

1. 문제그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성하시오 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V M 개의 줄에는 간선이 연결하는 두 정점의 번호가 주어지고, 입력으로 주어지는 간선은 양방향이다1 2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 깊이 우선 탐색3. 접근 방식DFS (Stack 이용) 와 BFS (deque 이용) 를 공부한 김에 관련 문제를 풀어봤다DFS, BFS 개념 정리 [TIL] DFS 깊이 우선 탐색 BFS 너비 우선 탐색그래프를 탐색하는 방법에는DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다 그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다 1. DFSDepth-First Se..

플로이드 와샬 Floyd Warshall 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘거쳐가는 정점을 기준으로 최단 거리를 구한다  플로이드 와샬 특징 1. 시작 정점과 도착 정점의 구분 없이 모든 경로에 대한 최단 경로를 구하는 데 사용된다2. 동적 계획법을 사용하여, 경로가 점차적으로 개선되면서 최단 경로를 찾는다3. 음수 가중치를 갖는 그래프에서도 동작하지만, 음수 사이클이 있으면 알고리즘이 제대로 동작하지 않는다  (음수 사이클 - 음수 가중치를 갖는 경로로 인해 무한히 작은 경로가 생기는 경우)4. 시간 복잡도 가 O(N^3) 으로, 정점의 수가 적을 때는 효율적이지만 정점 수가 많을 수록 비효율적일 수 있다 5. 인접 행렬로 표현하여 사용되며, 행렬의 각 값은 두 정점 사이의..

1. 문제1번부터 N번까지의 도시와 M개의 단방향 도로가 존재할 때 (모든 도로의 거리는 1이다)특정한 도시 X로부터 출발하여 최단 거리가 K인 모든 도시의 번호를 구하는 프로그램을 작성하시오2  2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 최단 경로* 데이크스트라 3. 접근 방식Week02 퀴즈 주제인 다익스트라를 이용하여 문제를 푸려고 한다 4. 전체 코드첫번째 시도 다익스트라 함수를 별개로 구현하고, N, M, K, X 를 입력 받아 딕셔너리 형태로 graph 를 만들었다 그리고 딕셔너리에서 items() 로 node 와 edge 를 꺼내 edge 와 K 를 비교해서 result list 에 append 하고, 나중에 .join() 으로 정리해서 print 했다import h..