저자 자체 제작 문제는 저작권을 위해 문제를 작성하지 않았음을 알립니다.
와 진짜 어렵다...카카오 4문제는 어떻게든 풀었지만 30~50분은 커녕 몇 시간씩 걸렸다. 이걸 현장에서 어떻게 풀어...참 갈 길이 너무 멀다.
Q.01 - 럭키 스트레이트
문제
https://www.acmicpc.net/problem/18406
현재 캐릭터의 점수를 N이라고 할 때 점수 N을 자릿수를 기준으로 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미한다. 예를 들어 현재 점수가 123,402라면 왼쪽 부분의 각 자릿수의 합은 1+2+3, 오른쪽 부분의 각 자릿수의 합은 4+0+2이므로 두 합이 6으로 동일하여 럭키 스트레이트를 사용할 수 있다.
현재 점수 N이 주어졌을 때, 럭키 스트레이트를 사용할 수 있는 상태인지 아닌지를 알려주는 프로그램을 작성하시오. 럭키 스트레이트를 사용할 수 있다면 "LUCKY"를, 사용할 수 없다면 "READY"라는 단어를 출력한다. 또한 점수 N의 자릿수는 항상 짝수 형태로만 주어진다.
문제접근
- 매우 쉬운 문제다. 자릿수의 길이는 항상 짝수로 주어지므로 왼쪽 절반, 오른쪽 절반으로 나눌 수 있다.
- 왼쪽 절반에서 점수 합을 구하고, 오른쪽 절반에서 점수 합을 구한 뒤 두 계산 결과를 비교한다.
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// 과정 1 - 입력을 받고 값을 배열에 저장한다.
string input; cin >> input;
vector<int> score(input.length());
for (int i = 0; i < input.length(); ++i) score[i] = input[i] - '0';
// 과정 2 - 왼쪽 절반 점수 합과 오른쪽 절반 점수 합을 구한다.
int leftVar = 0;
for (int i = 0; i < input.length() / 2; ++i) leftVar += score[i];
int rightVar = 0;
for (int i = input.length() / 2; i < input.length(); ++i) rightVar += score[i];
// 과정 3 - 합한 두 값을 비교하고 결과를 출력한다.
if (leftVar == rightVar) cout << "LUCKY\n";
else cout << "READY\n";
}Q.02 - 문자열 재정렬
문제
알파벳 대문자와 숫자로만 구성된 문자열이 있을 때 모든 알파벳을 오름차순으로 정렬하여 출력한 뒤에 모든 숫자를 더한 값을 이어서 출력한다. 예를 들어, K1KA5CB7 = ABCKK13이다.
문제접근
- 문자열에는 중복된 숫자와 문자가 들어올 수 있다.
- 알파벳은 23개, 숫자는 10개이므로 해시(hash)를 사용하는게 유효한 방법이다.
- 문자열을 앞에서부터 읽으며 알파벳이라면 '알파벳 해시'에서 해당하는 인덱스의 값을 하나 증가시키고, 숫자라면 '숫자 해시'에서 해당하는 인덱스의 값을 하나 증가시킨다.
- 출력할 때는 다음과 같은 규칙으로 출력한다.
- '알파벳 해시'의 앞에서 부터 인덱스의 값만큼 알파벳을 출력한다.
예를 들어, [0]에4가 들어있다면,AAAA를 출력하고, [3]에2가 들어있다면,DD를 출력한다. - '숫자 해시'에서는 을 계산한 뒤 합을 구한다.
예를 들어,{1, 0, 0, 2, ... , 0}이라면, 로 문제에서 원하는 조건을 만족할 수 있다.
- '알파벳 해시'의 앞에서 부터 인덱스의 값만큼 알파벳을 출력한다.
코드
#include <iostream>
#include <string>
using namespace std;
static int alphabet[23], number[10]; // 외부 해시 배열
int main() {
string input; cin >> input;
// 과정 1: 각 케이스에 알맞게 해시값을 증가시킨다.
for (size_t i = 0; i < input.length(); ++i) {
if (isalpha(input[i])) alphabet[input[i] - 'A']++;
else number[input[i] - '0']++;
}
// 과정 2: 알파벳을 출력한다.
for (int i = 0; i < 23; ++i)
for (int j = 0; j < alphabet[i]; ++j)
cout << static_cast<char>(i + 'A');
// 과정 3: 숫자의 합을 출력한다.
int sum = 0;
for (int i = 0; i < 10; ++i) sum += (i * number[i]);
cout << sum << '\n';
}Q.03 - 문자열 압축
문제
https://programmers.co.kr/learn/courses/30/lessons/60057#
데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.[string] [result] "aabbaccc" 7 "ababcdcdababcdcd" 9 "abcabcdede" 8 "abcabcabcabcdededededede" 14 "xababcdcdababcdcd" 17
문제접근
문제 풀이 전 생각해야 할 사항들
- 문자열을 자르는 단위를 1부터 하나씩 증가시켜 나가면서 최소 문자열 길이를 구한다.
- 본 문제에서는 압축된 문자열 이 아니라 길이가 관심사임을 파악한다.
- 매 loop 마다 문자열을 자르지 않을 때를 기준으로 길이를 압축하거나(줄이거나)
- 매 loop 마다 문자열 길이 0을 기준으로 길이를 추가하거나(늘리거나)
- 위 두 가지 방법 중 하나를 사용하면 된다. 여기서는 두 번째 방법을 사용한다.
- 문자열을 자르는 단위가
n일 때 비교하는 문자의 개수는2n개 임을 알아야 한다.- 예) 자르는 단위:
2->aabbaabb = (aa|bb)(aa|bb)이렇게 4개씩 잘린다.
- 예) 자르는 단위:
- 자르고 남은 문자들도 있을 수 있음을 고려해야 한다.
문제 풀이
- 최악의 경우는 문자열을 자르지 않을 때의 문자열의 길이이므로 해당 값으로 초기화 해준다.
- 가장 바깥쪽 반복문은 자르는 단위를 1부터 하나씩 증가시키는 반복문.
안쪽 반복문은 압축을 진행하기 위해 가리키는 인덱스를 증가시키는 반복문.
가장 안쪽 반복문은 동일한 부분 문자열이 몇 개 있는지 카운트하기 위한 반복문.
총 3가지 중첩 반복문으로 이뤄진다.
- 자르는 단위로 자른 뒤 비교하려는 두 부분 문자열의 경우의 수는 다음 2가지다.
- 두 부분 문자열이 같은 경우 (압축 가능)
count변수를 하나 증가시킨다.- 현재 위치 이후에 같은 부분 문자열이 더 있는지 탐색한다. (가장 안쪽 반복문)
- 이때 이동하는 인덱스 단위는 자르는 문자열 단위이다.
(자르는 단위가2라면 인덱스도 2칸씩 옮긴다는 뜻)
- 두 부분 문자열이 다른 경우 (압축 불가능)
- 만일
count변수가0이상이라면 압축할 수 있다는 뜻이므로count의 자릿수를 파악하고 '정답 문자열 길이'에 추가시킨다.
(count가1~9라면1을 추가,count가10~99라면2를 추가해줘야 한다!) - 압축할 수 없는 경우이므로 그냥 부분 문자열 길이(자르는 단위 길이)만큼 '정답 문자열 길이'에 더해주고 다음 칸으로 이동한다.
- 이때 이동하는 인덱스 단위는 자르는 문자열 단위이다.
- 만일
- 두 부분 문자열이 같은 경우 (압축 가능)
- 반복문이 끝난 뒤에는 남는 문자가 있는지 확인하고 있다면 그 길이만큼 '정답 문자열 길이'에 추가시키고 최소길이인지 판단 후 정답을 갱신한다.
- 남는 문자가 있는 확인하는 방법은 (3)번에서 계속 이동시켰던 인덱스 변수가 문자열 끝에 도달했는지 아닌지 여부로 판단할 수 있다.
코드
#include <string>
using namespace std;
int solution(string s) {
int maxTrial = s.length() / 2; // 최대 가능 분할 회수
int answer = s.length(), tempAnswer = 0;// 분할하지 않은 경우로 초기화
int idx, cnt; // idx는 가리키는 인덱스, cnt는 반복되는 부분문자열 개수
for (int trial = 1; trial <= maxTrial; ++trial) {
idx = 0, tempAnswer = 0, cnt = 0;
while (idx + 2 * trial <= s.length()) { // 압축 가능한 최대 위치까지 진행
while (s.substr(idx, trial) == s.substr(idx + trial, trial)) {
// 압축이 가능하다면 idx 옮기면서 카운팅한다.
idx += trial;
cnt++;
}
// 카운트 변수에 따라 추가해줘야 하는 문자열의 길이가 다르다.
// [주의]: cnt가 1~9 : 길이 1, 10~99: 길이 2, 100~999: 길이 3 임을 고려.
if (cnt > 0) tempAnswer += (trial + to_string(cnt + 1).length());
else tempAnswer += trial;
idx += trial; // idx를 옮겨서 다음 loop로
cnt = 0; // cnt를 초기화한다.
}
tempAnswer += (s.length() - idx); // 남는 문자가 있다면 추가시켜준다.
answer = min(answer, tempAnswer); // 정답을 갱신한다.
}
return answer;
}Q.04 - 자물쇠와 열쇠
문제
https://programmers.co.kr/learn/courses/30/lessons/60059
MxM으로 주어진key배열,NxN으로 주어진Lock배열이 주어졌을 때,key배열을 이동하거나 회전시켜서Lock배열을 완전히 채울 수 있는지 판단하시오.
문제접근
- 첫 문제풀이는 매개변수로 입력받은 2차원 배열을 상하좌우로 이동시키는
moving함수와 오른쪽으로 90도 회전시키는rotating함수를 만들어서 풀었다. 그러나 이 문제의 가장 걸림돌이 되는 부분은 바로 인덱스 범위 문제였다. 본 풀이법으로는 이 문제를 해결하기 까다로웠으며 풀이과정이 복잡해서 최적화가 필요하다고 판단했다. rotating함수는 놔두고moving함수는 제거하자.moving함수를 사용하지 않고도key배열을 움직일 수 있는 방법을 떠올리는 것이 이 문제의 핵심이다.Lock배열의 가로 3배, 세로 3배만큼의 2차원 배열을 만들고Lock배열을 가운데에 넣는다.Lock배열의 가장 좌측, 가장 위칸에서 부터 시작해서Key배열을 이동시키면서Lock배열과 겹치지는 않는지(비정상, false), 빈 칸은 없는지(비정상, false) 혹은 모든 칸을 잘 채우는지(정상, true) 확인하는 방법을 사용한다.
- 위 그림에서
key배열은S포인트부터 시작해서 가로로E포인트, 세로로E포인트까지 이동시키면서Lock배열을 모두 채우는지 확인한다. - 매 이동마다 4번씩 회전시키는것도 잊지말자.
코드
#include <vector>
using namespace std;
static int lockSize, keySize;
// 배열을 오른쪽으로 90도 회전시키는 코드.
void rotating (vector<vector<int>>& vec) {
vector<vector<int>> temp = vec;
for (int y = 0; y < keySize; ++y)
for (int x = 0; x < keySize; ++x)
temp[y][x] = vec[keySize - 1 - x][y];
vec = temp;
}
bool checkValid(vector<vector<int>> map, vector<vector<int>> key, int y, int x) {
// key의 시점부터 시작해서 값을 증가시킨다.
for(int i = y; i < y + keySize; ++i)
for (int j = x; j < x + keySize; ++j)
map[i][j] += key[i - y][j - x];
// 겹치는 칸은 2가 되고, 비어있는 칸은 0이 된다. 발견 시 false 반환한다.
for (int i = lockSize; i < 2 * lockSize; ++i)
for (int j = lockSize; j < 2 * lockSize; ++j)
if (map[i][j] == 2 || map[i][j] == 0) return false;
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
lockSize = lock.size(), keySize = key.size();
// lock의 가로, 세로가 3배만큼 큰 배열 생성 후 lock을 가운데에 넣는다.
vector<vector<int>> map(3 * lockSize, vector<int>(3 * lockSize, 0));
for (int y = 0; y < lockSize; ++y)
for (int x = 0; x < lockSize; ++x)
map[lockSize + y][lockSize + x] = lock[y][x];
// key의 시점, 종점을 계산한다. (그림을 그려서 확인하면 이해 쉬움)
int newStartPos = lockSize - (keySize - 1);
int newEndPos = 2 * lockSize - 1;
// key를 한 칸씩 이동시키면서 4번 회전시키고 열쇠가 들어가는지 확인한다.
for (int y = newStartPos; y <= newEndPos; ++y)
for (int x = newStartPos; x <= newEndPos; ++x)
for (int cnt = 0; cnt < 4; ++cnt)
if(checkValid(map, rotating(key), y, x)) return true;
return false;
}Q.05 - 뱀
문제
https://www.acmicpc.net/problem/3190
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
문제접근
문제 풀이 전 고려사항
- 삼성에서 사랑하는 전형적인 게임 시뮬레이션 문제다.
- 놀랍게도 문제에서 많은 힌트를 구할 수 있다!
- 뱀은 (1, 1)에서 시작하고 첫 길이는
1이다. - 머리가 먼저 이동하고 사과의 존재 여부에 따라 꼬리가 이동한다는 점이 힌트다!
- 주어진 힌트대로 코드를 구현하면 된다.
- 뱀은 (1, 1)에서 시작하고 첫 길이는
- 이동 방향에 따라 같은
L,D명령도 다른 방향으로 전환된다는 점을 고려하자. - 게임 종료 조건은 자신의 몸에 닿거나 맵 범위를 나가는 경우다.
문제 풀이
- 명령은
queue에 저장해둔 뒤 정해진 시간이 되면 명령을 수행하고pop()해서 다음 명령까지 기다린다. - 사과는 맵에서
2로 표시하고, 뱀은1로 표시하고, 빈칸은0으로 표시한다. - 뱀을 표현하는 방법은 여러가지가 있을 것이다.
그러나 이 문제에서 가장 걸림돌이 되는 것은 "꼬리를 어떻게 이동시킬 것이냐?"이다. - 단순히 머리를 이동시킨 자리를
1로 만들고, 꼬리가 있던 자리를0으로 만드는 것은 옳은 방법이 아니다. 왜냐하면 단 한 번이라도 방향전환이 이뤄졌을 경우 꼬리가 그 방향전환을 따라갈 방법이 없기 때문이다.- 가능하긴 하다. 방향전환이 이뤄질 때마다 현재 뱀 길이와 방향전환정보를
pair<int, int>구조로 어딘가에 저장한 뒤 매 초마다 모든 요소의.first를 하나씩 차감한 뒤0이 되면 꼬리도 방향을 전환하도록 하면 되긴하다. - 너무 복잡하다는게 문제!
- 가능하긴 하다. 방향전환이 이뤄질 때마다 현재 뱀 길이와 방향전환정보를
- 따라서 본 문제에서는
deque자료구조를 이용해서 머리는push_front()하며 전진하고, 꼬리는pop_back()해주는 식으로 꼬리를 바꿔나가는 방법을 사용한다.
과정
- 초기화 및 뱀의 초기위치를 할당해준다.
- 기저조건(뱀이 범위를 벗어나는 경우)을 명시하고 무한 loop를 돌린다.
- 매 loop마다 명령 queue의
front()를 확인해서 수행할 시간인지 아닌지 판단한다.- 명령을 수행할 시간이 아니라면 현재 방향대로 전진한다.
- 명령을 수행할 시간이라면 방향을 바꿔주고 명령을
pop()해서 제거한다. (FIFO)
- 초(second)를 증가시킨다.
- 머리를 움직인다.
- 머리가 몸에 닿았다면 반복문을 탈출한다. (GAME OVER)
- 사과가 없는 곳이라면 꼬리 위치를
0, 빈칸으로 바꿔주고pop_back()한다. - 사과가 있는 곳이라면 꼬리 위치를 바꿔줄 필요가 없다.
- 머리가 늘어난 부분을
1로 만들어주고push_front()해서 새로운 머리로 만들어준다.
코드
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
static int N, K, L, board[102][102];
void changeDir(int& offsetY, int& offsetX, char c) {// 90도 회전
if (offsetY == 0) {
if (offsetX == 1) offsetY = (c == 'L') ? -1 : 1;// 오른쪽->위쪽
else offsetY = (c == 'L') ? 1 : -1; // 왼쪽->아래쪽
offsetX = 0;
} else {
if (offsetY == 1) offsetX = (c == 'L') ? 1 : -1;// 아래쪽->오른쪽
else offsetX = (c == 'L') ? -1 : 1; // 위쪽->왼쪽
offsetY = 0;
}
}
int solve(queue<pair<int, char>> command) {
int sec = 0, dirY = 0, dirX = 1; // 초기 시간: 0, 최초 방향: 오른쪽
deque<pair<int, int>> snake;
snake.push_back({1, 1}); // 초기 Head = Tail = (1, 1)에 위치함.
board[snake.front().first][snake.front().second] = 1; // 뱀의 위치 = 1
while (true) {
int headY = snake.front().first, headX = snake.front().second;
// [기저조건]: 범위를 벗어나는 경우 게임이 종료된다.
if (headY < 1 || headY > N || headX < 1 || headX > N) break;
// 정해진 시간에 명령을 수행한다. 수행한 명령은 제거한다.
if (command.front().first == sec) {
changeDir(dirY, dirX, command.front().second);
command.pop();
}
sec++;
headY += dirY; headX += dirX; // 정해진 방향대로 머리가 먼저 움직인다.
if (board[headY][headX] == 1) break; // 만일 뱀의 몸통과 닿으면 게임 종료.
if (board[headY][headX] == 0) { // 빈칸인 경우 tail을 0으로 바꿔준다.
board[snake.back().first][snake.back().second] = 0;
snake.pop_back(); // tail을 다음 칸으로 갱신해준다.
}
board[headY][headX] = 1; // 머리가 늘어난 부분을 1로 만들어주고,
snake.push_front({headY, headX}); // 새로운 head를 snake 배열 맨 앞에 추가해준다.
}
return sec;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> K;
for (int i = 0; i < K; ++i) {
int y, x; cin >> y >> x;
board[y][x] = 2; // 빈칸: 0, 뱀: 1, 사과: 2 표시.
}
cin >> L;
queue<pair<int, char>> command;
for (int i = 0; i < L; ++i) {
int s; char c; cin >> s >> c;
command.push(make_pair(s, c));
}
cout << solve(command) << '\n';
}- 맵을
102x102칸으로 만든 이유?- 상하좌우 맵의 범위를 넘어가면 인덱스 범위 오류가 날 수 있기 때문에 한 칸씩 여유를 줬다.
Q.06 - 기둥과 보
문제
https://programmers.co.kr/learn/courses/30/lessons/60061
문제접근
- 문제 조건이 복잡하므로 정리하면서 문제를 파악해야 한다.
- 기둥을 놓을 수 있는 조건
- 기둥이 바닥에 있는 경우
- 기둥이 보 한쪽 끝에 있는 경우
- 다른 기둥 위에 있는 경우
- 보를 놓을 수 있는 조건
- 보의 한 쪽 끝이 기둥에 있는 경우
- 보의 양쪽 끝이 다른 보에 연결되어 있는 경우
- 설치하는 경우
- 일단 설치한다.
- 가능한지 아닌지 검사하고 아니라면 다시 뺀다.
- 삭제하는 경우
- 일단 해체한다.
- 가능한지 아닌지 검사하고 아니라면 다시 설치한다.
- 기둥을 놓을 수 있는 조건
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct Component {
int x, y, thing, op;
Component(const vector<int>& vec) {
if (vec.size() == 3) x = vec[0], y = vec[1], thing = vec[2];
else x = vec[0], y = vec[1], thing = vec[2], op = vec[3];
}
}Component;
// 현재 answer 구조가 가능한지 불가능한지 판단한다.
bool isPossible(const vector<vector<int>>& answer) {
for (int i = 0; i < answer.size(); ++i) {
Component comp(answer[i]);
bool check = false;
if (!comp.thing) { // [1]: '기둥'을 검사한다.
if (comp.y == 0) check = true; // [기저]: 기둥이 바닥에 있는 경우 = 정상
for (int j = 0; j < answer.size(); ++j) {
Component temp(answer[j]);
// 기둥이 보 위에 있는 경우, 다른 기둥 위에 있는 경우 = 정상
if (comp.x - 1 == temp.x && comp.y == temp.y && temp.thing) check = true;
else if (comp.x == temp.x && comp.y == temp.y && temp.thing) check = true;
else if (comp.x == temp.x && comp.y - 1 == temp.y && !temp.thing) check = true;
}
if (!check) return false;
} else { // [2]: '보'를 검사한다.
bool leftCheck = false, rightCheck = false;
for (int j = 0; j < answer.size(); ++j) {
Component temp(answer[j]);
// 보의 한 쪽 끝이 기둥 위에 있는 경우 = 정상
if (comp.x == temp.x && comp.y - 1 == temp.y && !temp.thing) check = true;
else if (comp.x + 1 == temp.x && comp.y - 1 == temp.y && !temp.thing) check = true;
// 양쪽이 다른 보에 연결되어 있는 경우 = 정상
if (comp.x - 1 == temp.x && comp.y == temp.y && temp.thing) leftCheck = true;
if (comp.x + 1 == temp.x && comp.y == temp.y && temp.thing) rightCheck = true;
if (leftCheck && rightCheck) check = true;
}
if (!check) return false;
}
}
return true;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
for (int i = 0; i < build_frame.size(); ++i) {
Component comp(build_frame[i]);
if (comp.op) { // [1]: 설치하는 경우
vector<int> temp {comp.x, comp.y, comp.thing};
answer.push_back(temp); // answer 배열에 추가(설치)하고 가능한지 여부 판단한다.
if (!isPossible(answer)) answer.pop_back(); // 불가능 하다면 다시 뺀다.
} else { // [2]: 해체하는 경우
int idx = 0; // 해체하려는 물건(기둥 또는 보)이 answer의 몇 번째 인덱스에 있는지 우선 찾는다.
for (int j = 0; j < answer.size(); ++j)
if (comp.x == answer[j][0] && comp.y == answer[j][1] && comp.thing == answer[j][2]) idx = j;
vector<int> temp = answer[idx];
answer.erase(answer.begin() + idx); // 해체할 물건을 찾았으니 answer에서 지우고, 가능한지 여부 판단한다.
if (!isPossible(answer)) answer.push_back(temp); // 불가능하다면 다시 넣는다.
}
}
sort(answer.begin(), answer.end()); // 오름차순으로 정렬 후 반환한다.
return answer;
}Q.07 - 치킨 배달
문제
https://www.acmicpc.net/problem/15686
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.
이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
문제접근
N은 50까지,M은 13까지이므로 충분히 모든 경우를 탐색할 수 있다.- 임의의 집으로부터 모든 치킨집까지의 거리를 나열한다.
- 치킨집을
M개 고를 때 최소 거리 합을 구하면 된다.
예제 분석
- 집이 4개, 치킨집이 3개 있으므로 총 12개의 길이가 나온다.
- 총 치킨집을 3개 선택할 수 있으므로 그냥 최소 합이 나오는 경우를 고르면 된다.
- 위 경우에서는
{1, 2, 1, 1}이므로 합이5가 나온다.
- 집이 6개, 치킨집이 5개 있으므로 총 30개의 길이가 나온다.
- 총 치킨집을 2개 선택할 수 있으므로 5개 중 2개를 고르고, 최소 합을 구한다.
- 모든 조합의 최소 합 중에서 가장 작은 합을 구한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
static int N, M;
static vector<pair<int, int>> home, chicken;
inline int getDistance(pair<int, int> lhs, pair<int, int> rhs) {
return abs(lhs.first - rhs.first) + abs(lhs.second - rhs.second);
}
int solve() {
// 임의의 i번째 집으로부터 모든 치킨집까지의 거리를 구하고 i행에 저장한다.
vector<vector<int>> memoSum(home.size(), vector<int>(chicken.size(), 0));
for (int i = 0; i < home.size(); ++i)
for (int j = 0; j < chicken.size(); ++j)
memoSum[i][j] = getDistance(home[i], chicken[j]);
// 모든 치킨집에서 M개 조합을 고르기 위해 마스킹을 사용할 것이다.
vector<bool> mask(chicken.size(), true);
for (int i = 0; i < M; ++i) mask[i] = false;
int ret = INT16_MAX; // 절대 나올 수 없는 큰 값으로 초기화한다.
vector<int> tempSum(home.size(), 0); // 각 집의 최소 '치킨거리'값 저장
do {
for (int i = 0; i < home.size(); ++i) {
int temp = INT16_MAX;
for (int j = 0; j < chicken.size(); ++j)
if (mask[j] == 0) temp = min(temp, memoSum[i][j]);
tempSum[i] = temp;
}
ret = min(ret, accumulate(begin(tempSum), end(tempSum), 0));
tempSum.assgin(home.size(), 0) // 다음 조합을 위해 초기화.
} while (next_permutation(begin(mask), end(mask))); // 다음 조합을 구한다.
return ret;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> M;
for (int y = 1; y <= N; ++y)
for (int x = 1; x <= N; ++x) {
int input; cin >> input;
if (input == 1) home.push_back({y, x});
else if (input == 2) chicken.push_back({y, x});
}
cout << solve() << '\n';
}Q.08 - 외벽 점검
문제
https://programmers.co.kr/learn/courses/30/lessons/60062
레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.
외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.
문제접근
- 두 가지 접근 방식이 있다.
- 원형 큐를 구현하고 풀이하는 방법. (직관적이지만 구현이 어려운 방법)
- 원형 레스토랑을 직선으로 바꾸고 풀이하는 방법 (떠올리기 어렵지만 효율적인 방법)
- 한 가지 확실한 것 - 친구를 외벽 약점에 위치시킨 뒤 출발시키는게 가장 유리하다.
- 즉, 원형 레스토랑을 직선으로 바꾼 뒤, 모든 친구 조합에 대해 모든 약점 위치에서 출발시켜서 보완이 가능한 최소 친구 수를 구하는 것이 풀이법이다.
코드
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> weak, vector<int> dist) {
int cntWeakSpot = weak.size();
for (int i = 0; i < cntWeakSpot; ++i)
weak.push_back(weak[i] + n);
int answer = dist.size() + 1; // 초기값: (최대 친구 수 + 1)
for (int i = 0; i < cntWeakSpot; ++i) { // 시작 위치를 변경해주며 탐색한다.
do {
int cntFriend = 1; // 첫 번째 친구가 i번째 시작 위치에서 이동한다.
int pos = weak[i] + dist[cntFriend - 1];
for (int j = i + 1; j < cntWeakSpot + i; ++j) {
if (pos < weak[j]) { // 이전 사람이 j번째 약점 검사 못했으므로 친구 더 필요함.
cntFriend++; // 필요한 친구 수 추가해준다.
if (cntFriend > dist.size()) break; // 더 부를 친구 없다면 반복문 탈출.
pos = weak[j] + dist[cntFriend - 1]; // 방금 부른 친구가 j번째 시작 위치에서 이동한다.
}
}
answer = min(answer, cntFriend); // 최소 친구 수 갱신한다.
} while (next_permutation(begin(dist), end(dist))); // 모든 친구 조합에 대해서 테스트 하기 위해 순열 사용.
}
if (answer > dist.size()) return -1; // [예외]: 현재 인원으로 약점을 모두 검사할 수 없는 경우.
return answer;
}
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.
구현 문제 모음 잘봤습니다! 감사합니다!