알고리즘 공부/codingame 사이트 문제

[Codingame] ROLLER COASTER(롤러코스터 대기열 시뮬레이션 - Circular queue, Dynamic programming

문제 간략 설명: 놀이공원 분석 센터에 새로 배치된 당신은 놀이기구의 수익을 예측하는 임무를 맡게 됩니다. 가장 먼저 롤러코스터를 살펴봅니다. [사진] [Rules_규칙] 목표: 하루 동안 롤러코스터가 벌어들일 수익을 예측합니다. 규칙: 놀이공원의 사람들은 롤러코스터를 매우 좋아해서 롤러코스터에서 내리자마자 다른 기구에는 관심도 없이 다시 롤러코스터를 타려고 줄을 섭니다. ■롤러코스터의 탑승 규칙은 다음과 같습니다. - 롤러코스터 앞에 차례대로 줄을 서고, 줄을 선 순서대로 탑승합니다. - 단체 손님은 모두 함께 탑승하기를 원합니다. 같은 그룹에 속한 손님들은 여러 대에 나눠 탑승할 수 없습니다. - 지정된 좌석보다 초과한 인원을 태울 수 없습니다. - 단체 손님을 모두 태우기에 좌석이 부족한 경우에는 ..

[Codingame] TAN NETWORK(거리별 최단 경로 찾기 - Dijkstra, A*)

문제 간략 설명: 철도 노선도에서 출발 정거장과 도착 정거장 사이를 최단 경로로 지나가는 모든 정거장의 이름을 알아내는 것이 이 게임의 목적입니다. 이 게임을 통해 여러분은 그래프 간선의 길이가 다를 경우에도 최단 경로를 찾을 수 있는 알고리즘을 학습합니다. [사진] [Rules_규칙] 목표: TAN이 공개한 정보에는 각 정거장의 이름, 시간표, 운행 경로 등이 있습니다. 여러분은 지역 주민을 위해 대중교통 앱을 개발해야 합니다. 공개된 정보를 바탕으로 임의의 두 정거장 사이의 최단 경로를 구하는 것이 목표입니다. 규칙: 공개된 데이터에는 다음 정보가 문자열로 표현됩니다. - 출발 정거장의 이름 - 모든 정거장의 정보 - 도착 정거장의 이름 - 각 정거장의 연결 정보 모든 정거장은 다음 정보를 가지고 있..

[Condingame] DEATH FIRST SEARCH - EPISODE 1(탈출 차단하기 - 그래프, 너비 우선 탐색)

문제 간략 설명: 이 에피소드는 영화 를 모티브로 해서 만들었습니다. 스카이넷 skynet은 터미네이터에서 인류의 적으로 나오는 인공지능 슈퍼컴퓨터입니다. 저항군은 스카이넷을 교란하기 위해 바이러스를 네트워크에 침투시키기 시작했습니다. 스카이넷은 이에 대응해서 에이전트를 보내 바이러스를 제거하려 합니다. 여러분은 저항군을 도와 바이러스가 에이전트에 의해 파괴되지 않도록 해야 합니다. [사진] [Rules_규칙] 목표: 문제 간략 설명에서 스카이넷이니... 바이러스니... 침투하니... 파괴되지 않게 하니... 이런 어려운 설명보다는 그냥 탈옥 영화를 보면 탈옥수가 감옥에서 탈옥하는데 탈옥수와 출구와의 최단 경로의 길목을 봉쇄한다고 생각하는 게 더 직관적입니다. 문제의 설명과는 다르지만 문제가 솔직히 너무..

[Condingame] SUPER COMPUTER(가장 효율적인 스케쥴-탐욕 알고리즘)

문제 간략 설명: 데이터 센터에 슈퍼컴퓨터를 새로 들였습니다. 데이터 센터의 연구자는 모두 슈퍼컴퓨터를 이용하여 본인의 연구를 수행하길 원합니다. 최대한 많은 연구자의 요청을 충족시키기 위하여 슈퍼컴퓨터의 효율을 극대화해야 합니다. 여러분은 컴퓨터가 쉬는 시간 없이 최대한 많은 작업을 수행하도록 스케줄을 조정하는 프로그램을 작성해야 합니다. [사진] [Rules_규칙] 목표: 과학자들이 사용할 수 있는 슈퍼컴퓨터 사용 계획을 세우기 위해, 과학자들이 필요로 하는 연구 일정을 고려하여 가능한 최대한 많은 연구를 처리할 수 있는 방법을 찾는다. 규칙: N개의 계산이 주어진다. 시작일과 연구 일수로 주어진다. 시작일과 연구 일수가 주어진다. 시작일부터 종료일(시작일+연구 일수-1)까지 해당 계산을 위해 슈퍼컴..

[Condingame] THE GIFT(돈을 나누는 가장 공평한 방식-탐욕 알고리즘)

문제 간략 설명: 이 게임의 등장인물은 영국 BBC 드라마 에 나오는 외계종족 우드(Ood)와 해결사 역할을 하는 닥터입니다. 닥터는 타임머신 우주선을 타고 우드 행성에 착륙했습니다. 성년에 이른 한 우드를 위해 여러 우드들이 멋진 선물을 사주고 싶어 하지만, 각자 예산이 달라서 문제입니다. [사진] [Rules_규칙] 목표: 선물을 사려하는데 우드마다 가진 예산이 다릅니다. 최대한 공평하게 비용을 지출해야 하는 상황입니다. 프로그램은 사람이 선물을 살 충분한 돈이 있는지 확인하고, 각자 지출해야 할 금액을 계산해야 합니다. 규칙: 닥터는 우드의 개별 예산 리스트를 가지고 있고, 최대한 개인의 지출 비용을 비슷하게 책정하 려 합니다. 최적의 해결책을 찾기 위해 닥터는 다음과 같이 기준을 정했습니다. 모두..

[CodinGame] SHADOWS OF THE KNIGHT(이진 탐색으로 폭탄 찾기)

문제 간략 설명: 배트맨이 되어 건물에 설치된 폭탄의 위치를 찾는 것입니다. [사진] [Rules_규칙] 목표: 건물 어딘가 인질이 있는 방에 폭탄이 설치되어 있습니다. 배트맨의 임무는 창문을 넘나들면 서 폭탄이 설치된 방을 찾아 폭탄을 제거하고 인질을 구출하는 것입니다. 배트맨은 창문 이곳 저곳을 자유롭게 점프하며 다닐 수 있습니다. 하지만 폭탄이 터지기 전에 움직일 수 있는 횟 수는 제한되어 있으니 서둘러야 합니다. 규칙: 초기 입력으로 빌딩의 가로 세로 크기 W, H와 남은 점프 가능 횟수 N, 시작 위치 X0, Y0를 입력받는다. 무한 루프를 돌며 매턴마다 폭탄이 있는 방향을 입력받는다. 입력된 방향으로부터 폭탄이 있는 방향을 추정하고, 다음으로 이동할 윈도우의 위치를 출력한다. 이동 가능한 방향..

[CodinGame] SCRABBLE(해시맵으로 단어 만들기)

문제 간략 설명: 이 문제는 스크래블이라는 유명한 단어 조합 게임에서 가져왔습니다. 스크래블은 주어진 알파벳을 조합하여 사전에 있는 단어를 만드는 게임입니다. [사진] [Rules_규칙] 목표: Scrabble 게임에서 각 플레이어는 7개의 글자를 뽑고, 이 중에서 가능한 가장 높은 점수를 얻을 수 있는 단어를 만들어야 합니다. 단어의 길이는 1에서 7 사이일 수 있습니다. 규칙: 각 글자는 난이도에 따라 점수가 주어집니다. 점수는 아래와 같습니다. e, a, i, o, n, r, t, l, s, u: 1점 d, g: 2점 b, c, m, p: 3점 f, h, v, w, y: 4점 k: 5점 j, x: 8점 q, z: 10점 주어진 7개의 글자를 이용하여 사전에 있는 단어 중 가장 높은 점수를 얻을 수 ..

[CodinGame] WAR(카드 게임 알고리즘-Queue)

이번 게임은 War이라는 오직 운빨만으로 승자가 결정되는 카드 게임입니다. [Rules_규칙] 목표: 현재 카드 상황을 보고 승자가 누구인지 판별하는 프로그램 규칙: 두 명의 플레이어 사이에서 진행되는 카드 게임입니다. 각 플레이어는 시작 시 덱의 변수 수의 카드를 받습니다. 각 라운드마다, 각 플레이어는 덱의 맨 위 카드를 뒤집어 보여주며, 숫자가 높은 쪽이 그 라운드의 승자가 됩니다. 이것을 "결투"라고 합니다. 만약 두 카드의 숫자가 같다면, "전쟁"이 발생합니다. "전쟁"에서는 각 플레이어가 덱에서 다음 세 장의 카드를 뒤집어 놓습니다. 이후 다시 승자를 가리기 위해 라운드를 다시 시작합니다. 한 플레이어가 "전쟁" 도중 카드가 부족해지면, 게임은 끝나며 무승부가 됩니다. 각 카드는 값과 모양으로..

[CodinGame] THERE IS NO SPOON - EPISODE 1(2차원 노드 찾기)

이번 게임은 제목부터 설명, 연출까지 모두 영화 에서 가져왔습니다. There is no spoon'은 영화에서 나 온 대사로, 현실에서 일어나기 힘든 일이라고 믿는 것은 사실 우리 마음속의 관념에 지나지 않는다는 뜻입니다. [Rules_규칙] 목표: 주어진 격자 내에서 각 노드의 오른쪽 및 아래쪽 이웃 노드를 찾아서 출력하는 것입니다. 규칙: 노드를 포함하는 (x1, y1) 좌표를 찾아 오른쪽에 있는 가장 가까운 다음 노드의 (x2, y2) 좌표와 아래쪽에 있는 가장 가까운 다음 노드의 (x3, y3) 좌표를 출력 이웃이 없으면 (x2, y2) 및/또는 (x3, y3) 대신 -1 -1 좌표를 출력 잘못된 이웃을 제공하거나 비어있는 셀의 이웃을 계산하거나 노드의 이웃을 계산하지 않거나 동일한 노드를 두 ..