반응형 Computer Science/Algorithms10 다이나믹 프로그래밍 Dynamic Programming 1. divide and conquer와 dynamic programming의 차이 divide and conquer(분할정복)는 하나의 문제를 해결할 수 있을 정도의 작은 부분으로 분할하여 하나하나 정복해나가는 프로그래밍 기법을 말합니다. 작게 나눌수록 복잡해 보였던 문제는 단순화되고 보다 쉽게 해결책을 도출해낼 수 있게 됩니다. dynamic programming(동적계획법)은 문제를 작은 조각들로 분해하여 한꺼번에 해결한다는 점에서 분할정복과 유사해보입니다. 하지만 분명한 차이가 있습니다. 분할정복은 하나의 문제를 작은 문제들로 나누고, 그 작은 문제들을 해결한 결과를 합쳐나가는 방식으로 문제에 대한 최종 해를 구하는 것인 반면, 다이내믹 프로그래밍은 일련의 문제들을 해결하기 위해서 문제를 작은 조.. 2022. 12. 29. 선택정렬, 버블정렬, 삽입정렬 1. 개요 1) 선택정렬 가장 간단한 정렬방법입니다. 6 3 4 5 1 2 리스트 중에서 최소값을 찾아 맨 앞에 위치시킵니다. 1 6 3 4 5 2 그리고 나머지 원소 중에서 다시 최소값을 찾습니다. 1 2 6 3 4 5 이를 n번 반복하면 1 2 3 6 4 5 1 2 3 4 6 5 1 2 3 4 5 6 정렬된 리스트를 얻을 수 있습니다. 2) 버블정렬 오른쪽 끝에서부터 최소값(왼쪽에서 시작할 경우는 최대값)을 거품이 올라오듯 보글보글 불러오는 방법입니다. 인접한 두 개 원소를 비교해서 작은 값을 땡겨오고 또 옆에 있는 놈과 비교해서 땡겨오고 하다보면 최소값이 리스트 시작점에 쌓이게됩니다. 3) 삽입정렬 길이가 1인 정렬된 리스트에 원소를 하나씩 추가하여 정렬된 리스트의 길이가 n이 되면 종료합니다. 2.. 2021. 11. 9. 스택과 괄호의 값 문제 : https://www.acmicpc.net/problem/2504 1. 개요 주어진 괄호들이 규칙에 맞는지 확인, 계산하는 문제입니다. 2. 고난과 역경 1) check () 우선 괄호의 짝이 맞는지 확인하기 위해 왼쪽 괄호를 하나씩 읽어와 스택에 추가합니다. 오른쪽 괄호를 만났을 때 스택이 비어있거나, 꺼내온 값이 왼쪽 괄호가 아니라면 규칙에 어긋나므로 0을 리턴합니다. 처음 완성한 check() 에는 " ( ( [ " 와 같이 왼쪽 괄호만이 들어왔을 때 그냥 통과시켜버리는 문제가 있었습니다. check가 규칙에 맞지 않는 녀석들을 통과시켜버리는 바람에 EmptyStackException 이 발생했습니다. for 문이 종료되었을 때, 스택에 값이 남아있다면 0을 리턴하는 문장을 추가하여 문제를.. 2021. 11. 4. 그리디 알고리즘? 1. 문제 기다란 다리가 있습니다. 다리가 낡아 여기저기 구멍이 나서 지나가는 사람들이 종종 물에 빠지곤 합니다. 다리의 구멍을 메우기 위해서 한 칸을 이동하는 데에는 1분이 걸립니다. 다만, 배를 타고 다리의 끝으로 이동할 경우 1분이 걸립니다. 구멍이 난 곳을 1, 멀쩡한 곳을 0으로 표시한 배열 bridge가 주어졌을 때, 다리를 보수하기 위해 이동하는데 걸리는 총시간을 구하십시오. 예) 아래와 같은 다리의 경우 현위치 0 0 0 0 0 1 1 배를 타고 이동하는데 1분 + 옆으로 한 칸 이동하는데 1분 총 2분이 소요됩니다. 2. 풀이과정 firstX lastX 0 0 1 0 0 1 0 0 0 위와 같이 처음 구멍이 난 곳을 firstX라 하고, 마지막으로 구멍이 난 곳을 lastX라 할 때, 배.. 2021. 11. 4. 완전탐색 - 순열 1. 개요 n개의 숫자로 가능한 모든 순열을 만드는 문제입니다. 2. 고난과 역경 완전탐색이 그렇게 어려운 문제는 아니라고 하는데 저한테는 왜 이렇게 골치가 아팠는지 모르겠습니다. 1) 잦은 실수 소수를 찾기 위해 n 보다 작은 수 (i < n) 로 모조리 나눠보던 기존의 코드에서, 효율성을 높여보겠다고 n의 제곱근* 까지 (i < Math.sqrt((double)n) 로 범위를 좁힌 게 화근이었습니다. 간단하게 더하기 1을 해주니 i < Math.sqrt((double)n) + 1 제곱근 값이 포함되면서 해결되었습니다. 이외에도 순열이 0으로 시작하는 경우의 문제라든지 문자열을 붙이는 순서 같은 것들이 여러 번 발목을 잡는 통에 시간을 지체하게 되었습니다. 완전탐색의 경우 적당히 어림잡아서 때려맞히는 .. 2021. 11. 3. 피보나치 함수 카운팅 문제 : https://www.acmicpc.net/problem/1003 1. 개요 재귀함수의 대명사 피보나치 함수가 구현은 쉽지만 얼마나 성능이 구린지 확인해보는 문제입니다. 2. 고난과 역경 ver 1. fibo함수에 count만 추가하면 기능 자체는 쉽게 구현할 수 있지만 당연하게도 시간초과로 실패하고 말았습니다. ver 2. import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] count = new int[2]; while(T>0) { int n = sc.nextInt(); fiboCount(count,.. 2021. 11. 1. 이전 1 2 다음 반응형
