본문 바로가기
반응형

알고리즘

 (104)
[알고리즘] 동적 계획법(dynamic programming) - 6 이번에는 조합 게임을 하는 경우에서 사용하는 동적계획법입니다! 바로, 체스나 바둑, 오목처럼 두 사람의 참가자가 하는 게임이죠!이 게임의 문제를 해결한다는 것은, 게임의 상태가 주어졌을때 완벽한 수를 찾아내는 알고리즘, 다시 말하면 자신이 최대한으로 이길 수 있는 수를 찾아내는 것이죠! 이런 수는 어떻게 찾아내면 될까요? 어떠한 경우에도 결국 게임이 끝나는 부분은 존재할 것입니다! 거기서 게임의 승/패는 갈리게 되겠죠. 여기서 A는 당연히 A가 이기는 결과로 갈 것입니다! 즉, 해당 차례인 사람의 차례에서 이기는 루트가 있다면 바로 이기는 수를 두게 되고, 해당 차례 사람은 이기게 되는 것이죠! 만약, B 차례인데 B가 이기는 경우가 없다면 어떻게 될까요? 위와 같은 경우는 어떻게 하더라도 A가 이기는 ..
[SW Expert Acade] 4616. 점프점프! 개굴이의 점핑! 4616. 점프점프! 개굴이의 점핑! SW Expert Academy는 문제의 무단 복제가 금지되어 있기 때문에 링크로 대체하겠습니다! 어떻게 풀까? 동적 계획법에서 가장 중요한 것은 어떠한 규칙으로 점화식을 만들까에 대한 것이죠!연꽃의 규칙을 발견하는 것이 가장 중요합니다!연꽃 f1에서 연꽃 f2로 이동하는 경우를 생각해봅시다.f1에서 f2로 이동하면, 결국 f2에서 f1으로 올 방법은 사라집니다!왜냐하면, 이동했다는것 자체가 바로 x나 y가 증가했다는 것을 의미하기 때문입니다!x나 y가 계속해서 증가해야 이동할 수 있는데, 더 작은 f1으로는 이동할 방법이 사라지는 것이죠! 이를 이용해서 연꽃을 한 번 정렬하면, 1번 연꽃부터 n번 연꽃까지 연꽃마다 갈 수 있는 연꽃으로 딱 한번씩만 이동시키면 답이 ..
[알고스팟] 실험 데이터 복구하기 RESTORE
[BOJ] 1158번 조세퍼스 문제 조세퍼스 문제 링크 어떻게 풀까? 해당 문제는 환형 링크드 리스트를 이용했습니다. 환형 링크드 리스트란?!처음과 끝이 연결되어있는 링크드 리스트입니다! 환형 링크드 리스트는 보통 링크드 리스트와는 조금 다르게 head가 없습니다!왜냐하면, 어짜피 끝과 처음이 연결되어 있기 때문입니다! tail의 바로 다음이 head가 되겠죠! 해당 문제는 환형큐를 만들기만 하면 아주 쉽게 해결됩니다. m칸 옮긴 다음에 해당 칸을 삭제후 출력하는 것을 n번 반복하면 되기 때문이죠! 예제를 풀어보면, 처음에 리스트에는 1,2,3,4,5,6,7 이 들어있습니다!그리고 커서를 3번 옮겨줍니다.그러면 3에서 커서가 멈추게 됩니다!3을 출력후 삭제합니다! 출력 : 3환형 리스트 : 1,2,4,5,6,7커서 : 2 또다시 커서를 3..
[BOJ] 2161번 문제 카드1, 2164번 문제 카드2 카드1 문제 링크카드2 문제 링크어떻게 풀까? 두 문제는 N만 다르지 거의 같은 문제입니다! 두 문제를 풀기 위해 리스트를 사용했습니다. 카드 1의 경우에는 리스트에서 맨 앞에 하나는 출력하고 리스트에서 삭제합니다.그리고 또다시 맨 앞의 수를 삭제하고 맨 뒤에 넣습니다.이 행동을 n-1번 반복하면 마지막 카드가 남고, 이 카드를 출력해주면 됩니다! 예제를 한번 풀어보겠습니다! 처음에 리스트에는 1,2,3,4,5,6,7이 들어있습니다. 맨 앞에있는 수는 출력하고, 2는 삭제한 뒤에 맨 뒤에 다시 넣어줍니다. 이제 맨 앞의 수가 3이 되고, 해당 수를 출력하고 삭제합니다.4는 삭제하고 맨 뒤로 보냅니다. 이제 맨 앞의 수는 7이 됩니다. 7을 출력하고 리스트에서 삭제합니다.2도 리스트에서 삭제 후에 맨 뒤에..
[알고스팟] 웨브바짐 ZIMBABWE클릭시 이동합니다! 웨브바짐문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)ZIMBABWE2000ms65536kb842354 (42%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러!계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르기 때문에 물건의 가격을 실시간으로 바꿔야 합니다. 웨브바짐에서 가장 큰 무가베 마트에서는 그래서 위와 같이 빈 칸만 쓰여 있는 광고판을 붙여놓고 계란 가격이 오름에 따라 (정확히는 웨브바짐 달러의 가치가 추락함에 따라) 실시간으로 숫자가 크게 적힌 플라스틱 판을 빈 칸에 갈아 끼웁니다. ..
[알고리즘] 동적 계획법(dynamic programming) - 5 오랜만에 쓰는 알고리즘 글입니다!요즘 뭔가 하고싶은 일이 많다보니 알고리즘을 조금 줄이게 됐네요!종만북 1권도 도대체 언제 끝낼지 모르겠습니다 후덜덜;; 각설하고 이제 동적 계획법에 대해서 설명하겠습니다! 오늘은 정수 이외의 입력에 대해서 어떻게 메모이제이션을 할 것인가? 에 대해 알아보겠습니다! 지금까지는 메모이제이션에 사용되는 값이 정수였습니다!하지만, 가끔씩 메모이제이션에 사용해야 하는 값이 문자열이거나 배열인 경우가 있습니다. 이런 경우에는 어떻게 메모이제이션을 해야할까요!? 첫번째로는 STL의 힘을 빌리는 방법이 있습니다.C++ STL에는 map과 vector라는 아주 훌륭한 stl이 있기 때문에 다음과 같이 메모이제이션을 사용할 수 있습니다. map memoi STL의 컨테이너는 자체적인 대소..
[SW Expert Academy] 괄호 짝짓기 괄호 짝짓기 SW Exeprt Academy의 문제들은 무단복제가 금지되어있기 때문에 링크로 대체합니다. 어떻게 풀까? 대표적인 스택 활용 문제입니다. 열린 괄호의 경우에는 모두 스택에 저장합니다.그리고, 닫힌 괄호가 나타나면 스택의 맨 위의 괄호와 비교합니다. 만약, 스택의 맨 위의 열린 괄호와 현재 나타난 닫힌 괄호가 매칭이 되지 않는다면 제대로 맞지 않는 괄호겠죠! 또한, 마지막에 스택 사이즈도 확인해야 합니다.스택 사이즈가 0이 아니라면, 열린 괄호가 많이 남아있다는 것이겠죠! 이 상황도 괄호의 짝이 맞지 않는 경우입니다. 간단한 예시 문제 2개를 풀어보겠습니다. 열린 중괄호이기 때문에 스택에 넣습니다.마찬가지로 열린 대괄호이기 때문에 스택에 넣습니다.마찬가지로 열린 소괄호이기 때문에 스택에 넣습..
반응형

티스토리툴바