심플 이즈 베스트

글

라벨이 알고리즘인 게시물 표시

[알고리즘] 3. 동적 계획법 개념

6월 05, 2016

동적 계획법 이란, 동적 계획법(Dynamic Programming) , 줄여서 DP는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 조금 장난스럽게 말해서 답을 재활용하는거다. 앞에서 구했던 답을 뒤에서도 이용하는 것으로 볼 수있다. (출처 : 나무위키 - 동적계획법 https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95?from=%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95) 이 말처럼 DP, 동적계획법은 완전 탐색에서 중복된 부분 문제를 한번만 계산 하기 위한 메모이제이션( Memoization) 이다. 메모이제이션이란, 같은 계산을 여러 번 해야 할 때, 한 번 계산한 결과를 메모리에 저장해 이후 동일한 계산 과정을 생략할 수 있게 하는 기법이다. (출처 : 나무위키 - 메모이제이션) https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98 ) 보통 동적계획법 알고리즘 구현은, 1. 주어진 문제를 완전 탐색 이용 해결, 2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션 적용 두가지 방법으로 나뉜다. 이를 토대로 탐색을 통해 이전 값을 참고하는 것을 해 본다면, [취업] 삼성 SW후기 포스팅의 문제를 동적계획법으로 설계 해 보려 한다. 일단 문제는, Player 비행기가 끝까지 도달하였을 때, 코인의 최대값이 문제다 (자세히는 포스팅을 참조...) 보통 완전탐색으로 모든 경우의 수 탐색을 통해 해결할 수 있지만, 크기가 커지면 탐색하는데 시간 초과가 발생한다. 이를 해결하기위해 동적계획법을 쓴다면, ...

[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

4월 14, 2016

출발점, 도착점 사이의 최단 경로를 알아내는 알고리즘, 각 꼭지점은 도시를 나타내고 변은 도로의 길이를 나타날 때, 도시간 최단경로 찾기가 문제이다 최단 경로 찾기에선 가장 간단한 문제 이기도 할 것이다. 일단 5개의 도시로 고정되어있고, -1은 갈 수 없는 거리 0은 자기 자신을 표현한다. 알고리즘을 대략적으로 설계하면, for i -> 0 , 5 , 1 [시작도시][i]로 전체를 검사한다. 완전탐색이지만, 예외조건을 둔다 0과 -1을 제외하고, isVisit을 도시크기만큼 2차원 배열을 같이 두어 방문 체크를 한다. 그리고 최소값만을 Return하는 형식을 취하면 될 것 같다. 도시를 출력하고자 한다면, vector를 따로 두어, 경로를 push_back 하면 될 것 같긴하다. 테스트 케이스 및 자료는 [알고리즘 자료] 2-1 을 보시면 있습니다. #include #include using namespace std; int city[5][5] = { 0, }; bool isVisit[5][5] = { false, }; bool isFinal = false; bool isPossiblePath(int val) { if (val == 0 || val == -1) return false; return true; } void VisitCheck(int src, int dst) { isVisit[src][dst] = true; } void VisitUnCheck(int src, int dst) { isVisit[src][dst] = false; } int Dijkstra(int src,int dst,int fDst,int path) { path = path + city[src][dst]; if (dst == fDst) return path; // 하나의 경로를 찾은 것 int result = 9999; for (int i = 0; i 추...

[알고리즘] 1. [C/C++] 4방향 체인코드를 이용한 논 크기 측정 문제

4월 13, 2016

알고리즘 문제 공부를 하고 있는데, 정리하여 공부겸 포스팅 할려 합니다. '논 그룹묶기 문제' 이며, 0은 논이아니고 1은 논입니다. 2차원 배열 nxn으로 구성되어있으며, test.txt의 첫 줄에는 테스트 케이스 숫자 다음 줄 부터는 nxn의 배열 크기 , 배열 값 순으로 되어있는 것을 읽으면 됩니다. 이 후 체인코드로 그룹핑된 갯수와 각 그룹들의 크기를 출력하는 문제입니다. ChainCode를 구현하는 문제로서, 4방향이지만, 여기서 대각선만 추가하면 8방향 체인코드 또한 구성됩니다. test.txt는 '알고리즘 자료' 카테고리의 첫번째에 답과 함께 올려 놓았습니다. 다음은 구현 코드이며, 알고리즘으로는, 모든 배열 인덱스에 접근하지만, 이미 그룹화 된 값과 0은 제외를 하고, 방문 할 때마다 그룹 값을 넣고, 그룹화가 끝나면, GroupNum을 증가시켜, 다시 시작하는 방법입니다. 값을 얻을 수 있습니다. 일종의 완전 탐색이지만, 예외조건이 있기에, 모든 곳을 탐색하진 않습니다. 아래 코드에서, 대각선 조건만 추가한다면, 8방향 체인코드로 구성됩니다. #include #include using namespace std; class NoN{ public: int size; }; NoN InitialNoN(int size) { NoN mData; mData.size = size; return mData; } bool IsOutBoard(int arrSize, int y, int x) { if (y = arrSize || x >= arrSize) return true; return false; } bool IsZeroOrGroupCheck(int y, int x, int **board) { if (board[y][x] != 1) return true; return false; } int...

이 블로그 검색

심플 이즈 베스트

글

진공 속 목소리: 의미 없는 세계에서 이유 찾기

[알고리즘] 3. 동적 계획법 개념

[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

[알고리즘] 1. [C/C++] 4방향 체인코드를 이용한 논 크기 측정 문제

이 블로그의 인기 게시물

윤석열 계엄령 선포! 방산주 대폭발? 관련주 투자 전략 완벽 분석

한국 핵무장 논의와 방위산업 관련주: 핵무기 개발 과정과 유망 종목 분석

[로스트아크] 제작 효율 최적화 위한 영지 세팅