동적 계획법 (28) 썸네일형 리스트형 [알고스팟] 지니어스 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)GENIUS20000ms65536kb751177 (23%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제MP3 플레이어에 들어 있는 곡들을 전부 셔플 모드로 들을 때 최대의 문제점은 서로 어울리지 않는 노래들이 갑자기 나올 수 있다는 것입니다. 끈적한 애시드 재즈를 듣고 있다가 갑자기 시끄러운 데스 메탈이 나오는 것만큼 분위기를 깨는 것도 없지요. 때문에 전세계에서 가장 잘 나가는 MP3 플레이어를 생산하는 오렌지 사에서는 이번에 지니어스라는 기능을 출시했습니다. 지니어스는 MP3 플레이어에 들어 있는 곡들을 셔플 모드로 들을 때 잘 어울리는 것끼리 순서대로 재생되도록 해 줍니다.태윤이는 오렌지 사의 새 MP3 플레이어를.. [알고스팟] 회전초밥 문제 링크 회전초밥문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)SUSHI8000ms65536kb1899628 (33%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의를 시작했습니다. 회전초밥집에는 n종류의 메뉴가 있는데, 운영진들은 각 메뉴에 대해 선호도를 매겼습니다.초밥계란연어장어대뱃살스테이크후라이드 치킨가격25003000400050001000015000선호도791012201운영진들은 주어진 예산 안에서 선호도의 합을 최대한으로 하도록 초밥을 먹고 싶습니다. 각 종류의 초밥은 무한정으로 공급된다고 가정합.. [알고스팟] 블록 게임 문제 링크 블록 게임문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)BLOCKGAME2000ms65536kb1313485 (36%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제시티빌과 비주얼드에 지친 진호와 현환이는 집에 굴러다니는 블럭들을 모아 새로운 게임을 하기로 했습니다. 5×5 크기의 게임판에서 시작해, 둘이 번갈아 가며 블럭을 하나씩 게임판에 내려놓습니다. 블럭은 L 모양으로 구성된 3칸짜리 블럭과 2칸짜리 블럭이 있으며, 항상 게임판에 있는 줄에 맞춰 내려놓아야 합니다. 블럭들은 서로 겹칠 수 없습니다. 다음 그림은 진행중인 게임판의 모습을 보여줍니다.그림에서 보이는 바와 같이 각 블록은 자유롭게 뒤집거나 회전해서 올려놓을 수 있습니다. 두 사람이 번.. [알고스팟] 숫자 게임 문제 링크 숫자 게임문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)NUMBERGAME1000ms65536kb1349795 (58%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다.게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다.게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다.게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의.. [알고리즘] 동적 계획법(dynamic programming) - fin. 드디어! 마지막입니다!! 오늘 알려드릴 동적 계획법 테크틱은 반복적 동적 계획법 입니다!지금까지는 재귀 함수를 이용해서 메모이제이션을 하기 위한 저장 공간을 만드는 것을 많이 보여드렸었죠! 반복적 동적 계획법을 이용하면 좋은점이 몇 가지 있습니다! 첫번째로는, 공간 복잡도를 줄일 수 있다는 것입니다! 재귀 함수를 통해서 메모리를 만들어 놓으면 함수 간에 순서가 명확하지 않기 때문에 처음부터 끝까지 사용할 공간을 미리 만들어 놓고,지우지 않습니다! 하지만, 반복적 동적 계획법을 이용하면 다릅니다. 대표적으로 유용하게 이를 활용하는 것이 슬라이딩 윈도 테크닉입니다! 예전에 삼각형 위의 최대 경로 알고리즘을 푼 적이 있었죠!재귀 함수를 이용한 메모이제이션을 이용할 때에는, 삼각형의 높이에 따라서 공간 복잡도가.. [알고스팟] 틱택토 문제링크 틱택토문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)TICTACTOE1000ms65536kb896341 (38%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다.xoo .x. ..x게임은 항상 x부터 시작합니다.틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요.입력입력의 첫 줄에는 테스트 케이스의 수 C( [알고리즘] 동적 계획법(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번 연꽃까지 연꽃마다 갈 수 있는 연꽃으로 딱 한번씩만 이동시키면 답이 .. 이전 1 2 3 4 다음
