▼ What ? 이번에도 해결한 문제도 구현 - 시뮬레이션 유형의 문제이다. ▼ 좌석 번호 문제 정보 현수는 자신의 홍채 지문을 읽으면 비밀번호가 자동으로 입력되는 소프트웨어를 만들고 있습 니다. 이 소프트웨어는 1부터 9까지의 숫자가 3 * 3 격자모양으로 되어 있는 키패드에서 비밀번호의 순서대로 이동하면서 입력되는 방식입니다. 키패드의 숫자배치는 항상 변합니다. 소프트웨어는 비빌번호의 첫 숫자에서 시작하여 이웃한(상하좌우, 대각선) 8개의 방향으로 이동하면서 입력됩니다. 이웃한 번호로의 이동시간은 1초가 걸립니다. 그리고 이웃하지 않은 숫자로의 이동은 이웃한 숫자를 통해서 이동하는 형태를 취하며, 이웃한 숫자로 이동때마다 1초씩 걸립니다. 즉 키패드에 숫자가 아래와 같이 배치되고, 시작위치가 2라면 ..
▼ What ? 이번에도 구현 - 시뮬레이션 유형의 문제를 풀어보려고 한다. ▼ 좌석 번호 문제 정보 세계 최고의 알고리즘 전문가인 현수의 강연을 보기위해 많은 사람들이 찾아왔습니다. 강연장에는 가로로 c개, 세로로 r개의 좌석이 c×r격자형태로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다. 아래 그림은 가로 6개, 세로 5개 좌석으로 구성된 6×5격자형 좌석배치입니다. 각 격자에 표시 된 (x,y)는 해당 좌석의 번호를 말합니다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (6, 5)이다. 사람들은 온 순서대로 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아 들어가면서 빈 좌석에 앉습니다. 만약 5번째로 온 사람은 (1, 5)좌석에 앉고, ..
▼ What ? 이번엔 구현 - 시뮬레이션 유형의 문제를 풀어보려고 한다. ▼ 잃어버린 강아지 문제 정보 현수는 농사지을 땅을 찾아 강아지를 데리고 산으로 들로 땅을 찾아 다니고 있었다. 숲속에서 낮잠을 자던 현수는 강아지가 도망가버려 강아지를 잃게 되었다. 강아지가 어디로 갔는지 모르는 현수는 강아지를 찾아 나섰다. 다행히 강아지에게 위치 추적기가 달려 있어 핸드폰 실시 간 위성지도로 현수의 위치와 강아지의 위치, 그리고 근처의 지도를 현수는 알 수 있습니다. 지도의 크기는 항상 10*10이며, 각각의 칸에는 각각 나무, 빈칸, 강아지, 그리고 현수가 있을 수 있습니다. 지도는 다음과 같이 주어진다. 0 - 빈칸, 1 - 나무, 2 - 현수, 3 - 강아지 강아지와 현수는 항상 고정된 방법으로 지도를 ..
▼ What ? 이제 지금까지 배운 것들을 전체적으로 활용해보는 문제들을 풀어보려고 한다. 이번 문제는 문자열을 다루는 문제이다. ▼ 문자열 압축 문제 정보 알파벳 대문자로 이루어진 문자열을 입력받아 같은 문자가 연속으로 반복되는 경우 반복되는 문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축하는 프로그램을 작성하세 요. 단 반복횟수가 1인 경우 생략합니다. 제한사항 문자열 s의 길이는 100을 넘지 않습니다. 입출력 예 어떻게 해결해야 할까 ? 새로운 문자가 발견되기 전까지 해당 문자의 빈도수를 체크해주고, 새로운 문자가 발견되면 그전 문자와 해당 문자의 빈도수를 해주면 StringBuilder에 더해주면 될 것 같다 기본형 정수(int)를 StringBuilder에 'append()' ..
▼ Why ? 이번 문제는 전에 배웠던 해시함수와 정렬을 활용하여 해결하는 문제이기 때문에 한 번 풀어보았다. ▼ 과일 장수 문제 정보 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에..
▼ Why ? 이번 문제는 이전에 풀었던 "최대 사과의 개수" 문제와 유사해보이지만 정렬 관련 문제는 계속 풀어보려고 한다. ▼ 과일 장수 문제 정보 과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다. 한 상자에 사과를 m개씩 담아 포장합니다. 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다. 과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다. (사과는 상자 단위로만 판매하며, 남는 사과는 버립니다) 예를 들어, k = 3, m = 4, 사과 7개의..
