영원 웹 개발과 일상

백준 16234 인구이동 문제 해설

30 Sep 2020

#[백준🔉][16234] 인구이동 문제 해설

👓 문제 요약

1 x 1 모양의 사각형이 n x n 만큼 펼쳐진 땅이 있다고 가정한다. 각 사각형은 나라를 지칭하며 그 안에는 백성들의 숫자가 있다.

매우 자유로운 이 대륙의 특정한 나라는 다른 나라의 인구수와 비슷하다면 연합을 하여 연합국 간 인구는 같은 숫자로 유지하기로 법을 제정했다.

위 법을 완전히 수행하기 위해 필요한 일 수를 구하여라.

라고 생각 하면 됨

자세한 문제 설명과 제한 사항은 백준 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

중요!!! 필요한 일 수이다. 이동한 횟 수가 아니다. 다시 말해 동일한 날에 연합이 여러개 발생한다 해도 하루에 일어났기 때문에 답을 추가할 때는 1을 추가해야한다

각 칸별로 BFS를 수행하면 풀 수 있는 문제.

🥽 소스코드 및 소스해석

백준 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 코드에는 테스트 코드가 존재합니다.

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
struct Point {
	int x;
	int y;
};

vector<vector<Point>> group;
vector<vector<int>> myBoard;
vector<vector<bool>> checked;

void dfs(int pre, int x, int y, int low, int high, vector<vector<int>>& myBoard, vector<vector<bool>> &checked);
void flatting(vector<vector<int>>& myBoard);
int main() {

	int boardSize;
	cin >> boardSize;
	int low, high;
	cin >> low >> high;
	myBoard.assign(boardSize, vector<int>(boardSize,0));

	for (int i = 0; i < boardSize; i++)
		for (int j = 0; j < boardSize; j++)
			cin >> myBoard[i][j];

	int answer = 0;
	while (true) {
		group.clear();
		checked.clear();
		group.push_back(vector<Point>(0));
		checked.assign(boardSize, vector<bool>(boardSize, false));
		for (int i = 0; i < boardSize; i++)
		{
			for (int j = 0; j < boardSize; j++)
			{
				if (checked[i][j] == true) continue;
				dfs(myBoard[i][j], j + 1, i, low, high, myBoard, checked);
				dfs(myBoard[i][j], j - 1, i, low, high, myBoard, checked);
				dfs(myBoard[i][j], j, i + 1, low, high, myBoard, checked);
				dfs(myBoard[i][j], j, i - 1, low, high, myBoard, checked);
				if (group[group.size() - 1].size() != 0)
					group.push_back(vector<Point>(0));
			}
		}
		flatting(myBoard);
		if (group[0].size() == 0) break;
		answer++;
	}
	cout << answer;
}
void dfs(int pre, int x, int y, int low, int high, vector<vector<int>>& myBoard, vector<vector<bool>> &checked) {
	if (y < 0 || y >= myBoard.size() || x < 0 || x >= myBoard.size()) return;
	if (checked[y][x] == true) return;

	int diff = abs(myBoard[y][x] - pre);
	if (diff >= low && diff <= high) {
		checked[y][x] = true;
		group[group.size() - 1].push_back({ x,y });
		dfs(myBoard[y][x], x + 1, y, low, high, myBoard, checked);
		dfs(myBoard[y][x], x - 1, y, low, high, myBoard, checked);
		dfs(myBoard[y][x], x, y + 1, low, high, myBoard, checked);
		dfs(myBoard[y][x], x, y - 1, low, high, myBoard, checked);
	}
}
void flatting(vector<vector<int>>& myBoard) {
	for (int i = 0; i < group.size(); i++)
	{
		if (group[i].size() == 0) continue;
		int flat = 0;
		for (int j = 0; j < group[i].size(); j++)
			flat += myBoard[group[i][j].y][group[i][j].x];
		flat /= group[i].size();
		for (int j = 0; j < group[i].size(); j++)
			myBoard[group[i][j].y][group[i][j].x] = flat;
	}
}

🔨 문제 후기

불필요한 동작도 많은 것 같지만 풀었다는 것에 만족하고 다른 사람의 코드를 보았다. 역시 세상에는 천재는 많고 나는 바보다.

프로그래머스 2020 KAKAO 가사 검색 문제 풀이

29 Sep 2020

#[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이

👓 문제 요약

너 TRIE 자료구조 아냐?

자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

트리가 아니다 T.R.I.E. 다. TRIE 자료구조는 단어의 각 글자를 Node 로 보고 자료를 저장하는 자료구조입니다. 자세한건 🛴 보러가기

Trie를 쓰기만 해서 풀 수 있는게 아니다.?가 등장하면 자료를 검색할 수 없다. 따라서 글자의 길이 마다, 그리고 각 노드에 이 노드를 지나간 놈이 몇명이냐를 저장해서 들어오는 인풋을 양쪽으로 검색할 필요가 있는 아주 미친듯한 문제다.

🥽 소스코드 및 소스해석

프로그래머스 사이트에서 풀고 직접 가져온 코드 입니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Trie {
    int data;
    Trie *node[26];
};

bool makeTree(string& word, Trie &node, int idx, bool mode); //if exist then true, else false
int findWord(string& word, Trie &node, int idx);
Trie head[10020];
Trie tail[10020];


vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;

    for (size_t i = 0; i < words.size(); i++)
    {
        int length = words[i].size();
        if (!makeTree(words[i], head[length], 0, true)) {
            head[length].data++;
        }
    }

    for (size_t i = 0; i < words.size(); i++)
    {
        int length = words[i].length();
        if (!makeTree(words[i], tail[length], length - 1, false)) {
            tail[length].data++;
        }
    }
    for (size_t i = 0; i < queries.size(); i++)
    {
        int length = queries[i].size();
        int count = 0;
        while (queries[i][count] == '?') count++;
        if (count == length) {
            answer.push_back(head[count].data);
        }
        else if (queries[i][0] == '?') {
            reverse(queries[i].begin(), queries[i].end());
            answer.push_back(findWord(queries[i], tail[length], 0));
        }
        else {
            answer.push_back(findWord(queries[i], head[length], 0));
        }
    }
    return answer;
}
bool makeTree(string& word, Trie& node, int idx, bool mode){
    //node[alphabet] = 자식
    if (mode && word.length() <= idx) return false;
    if (!mode && idx < 0) return false;
    if (node.node[word[idx] - 'a'] == NULL) {
        node.node[word[idx] - 'a'] = new Trie();
    }
    else if (mode && idx == word.length() - 1 && node.node[word[idx] - 'a'] != NULL) {
        return true;
    }
    else if (!mode && idx == 0 && node.node[word[idx] - 'a'] != NULL) {
        return true;
    }
    if (mode == true) {
        if (!makeTree(word, *node.node[word[idx] - 'a'], idx + 1, mode)) {
            node.node[word[idx] - 'a']->data++;
            return false;
        }
        else {
            return true;
        }
    }
    else {
        if (!makeTree(word, *node.node[word[idx] - 'a'], idx - 1, mode)) {
            node.node[word[idx] - 'a']->data++;
            return false;
        }
        else {
            return true;
        }
    }


    return false;
}
int findWord(string& word, Trie& node, int idx) {

    if (&node == NULL) {
        return 0;
    }
    if (node.node[word[idx] - 'a'] == NULL && idx == word.length() - 1) {
        return node.data;
    }
    else if (node.node[word[idx] - 'a'] == NULL && idx != word.length() - 1) {
        return 0;
    }
    if (word.length() == idx - 1) {
        return node.node[word[idx] - 'a']->data;
    }
    if (word[idx + 1] == '?') {
        return node.node[word[idx] - 'a']->data;
    }
    return findWord(word, *node.node[word[idx] - 'a'], idx + 1);
}

🔨 문제 후기

제 소스코드 보다 더 잘 만든 사람 많으니 찾아보시는 거 추천합니다. 저도 어려운건 잘 못해요. (●’◡’●)

이 정도 난이도의 문제를 시간내에 풀 수 있다면 당신은 최고의 실력자! 한 번 풀어보고 다시 풀어보자!

프로그래머스 2020 kakao 기둥과 보 설치 문제 해설

29 Sep 2020

#[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설

문제 요약

죠르디 는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우려고 한다. 2차원 벽면 n x n 의 격자칸이 주어지고, 기둥과 보를 설치하고 제거하는 명령어가 주어 질 때 해당 명령어가 실행 가능하다면 실행하라.

자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

문제 풀이

  • 보는 오른쪽으로, 기둥은 위로 설치, 제거한다.
  • 보는 양쪽 끝 아래에 기둥이 존재하거나 양쪽으로 보가 존재해야 한다.
  • 기둥은 아래에 기둥이 있거나 아래에 보가 있어야 한다.
  • 어떤 기둥 또는 보를 제거했을 때 모든 기둥과 보가 유지될 수 있어야만 제거를 진행한다.

소스코드 및 소스해석

프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.

#include <string>
#include <vector>

using namespace std;
//https://programmers.co.kr/learn/courses/30/lessons/60061

vector<vector<int>> solution(int n, vector<vector<int>> build_frame);
void myadd(int x, int y, bool iscol);
void myremove(int x, int y, bool iscol);
bool check(int x, int y, bool iscol);
bool checkEvery();

int board[128][128][4]; //4방향 top 부터 시계방향.
int g_n;

int main() {
	vector<vector<int>> answer;
	vector<vector<int>> input = { {1,0,0,1} ,{1,1,1,1},{2,1,0,1},{2,2,1,1},{5,0,0,1},{5,1,0,1},{4,2,1,1},{3,2,1,1} };
	vector<vector<int>> input2 = { {0, 0, 0, 1} ,{2, 0, 0, 1},{4, 0, 0, 1},{0, 1, 1, 1},{1, 1, 1, 1},{2, 1, 1, 1},{3, 1, 1, 1},{2, 0, 0, 0},{1, 1, 1, 0},{2, 2, 0, 1} };
	answer = solution(5, input2);
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
	vector<vector<int>> answer;
	g_n = n;
	for (int i = 0; i < build_frame.size(); i++) {
		if (build_frame[i][3] == 1) {
			myadd(build_frame[i][0], build_frame[i][1], !build_frame[i][2]);
		}
		else {
			myremove(build_frame[i][0], build_frame[i][1], !build_frame[i][2]);
		}
	}
	for (int i = 0; i <= n; i++) {
		//i = x, j = y, x 오름차순, x가 같으면 y좌표 기준
		for (int j = 0; j <= n; j++) {
			if (board[j][i][0] == 1) {
				answer.push_back(vector<int>({ i, j, 0 }));
			}
			if (board[j][i][1] == 1) {
				answer.push_back(vector<int>({ i, j, 1 }));
			}
		}
	}
	return answer;
}
void myadd(int x, int y, bool iscol) {
	if (iscol && check(x, y, true)) {
		board[y][x][0] = 1;
		board[y + 1][x][2] = 1;
	}
	else if (!iscol && check(x,y, false)) {
		board[y][x][1] = 1;
		board[y][x + 1][3] = 1;
	}

}
void myremove(int x, int y, bool iscol) {

	//!(board[y][x + 1][0] && check(x + 1, y, iscol)) ||
	if (iscol) {
		board[y][x][0] = 0;
		board[y + 1][x][2] = 0;
		if (!checkEvery()) {
			board[y][x][0] = 1;
			board[y + 1][x][2] = 1;
		}
	}
	else {
		board[y][x][1] = 0;
		board[y][x + 1][3] = 0;
		if (!checkEvery()) {
			board[y][x][1] = 1;
			board[y][x + 1][3] = 1;
		}
	}
}
bool check(int x, int y, bool iscol) {
	if (iscol && (y == 0 || (board[y][x][1] == 1 || board[y][x][3] == 1 || board[y][x][2] == 1))) return true;
	else if (!iscol && (board[y][x][2] == 1 || board[y][x + 1][2] == 1
		|| (board[y][x + 1][1] == 1 && board[y][x][3] == 1))){ return true;}
	return false;
}

bool checkEvery() {
	for (int i = 0; i <= g_n; i++) {
		//i = x, j = y, x 오름차순, x가 같으면 y좌표 기준
		for (int j = 0; j <= g_n; j++) {
			if (board[j][i][0] ? !check(i, j, true) : false) { return false;}
			if (board[j][i][1] ? !check(i, j, false) : false) { return false; }
		}
	}
	return true;
}

문제 후기

인풋값이 크지 않으므로 전수조사를 수행하길 권한다. 사실 나도 제거 할 때 모든 조건을 어째 고려해야하나 싶다가 전수조사 하니까 답이 떠버렸다.

헿

프로그래머스 2020 kakao 자물쇠와 열쇠 문제 풀이

29 Sep 2020

#[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이

👓 문제 요약

고고학자로 위장한 도굴꾼 튜브는 고대 유적지에서 자물쇠를 발견했습니다. 가지고 있는 열쇠가 이 자물쇠에 맞는지 사방으로 끼워보고 돌려서도 끼워보고 해서 자물쇠를 열어 발굴할 수 있는지 확인하려고 합니다. 문제를 푸시오.

자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

20x20의 크기의 board에 열쇠가 맞는지 모든 케이스를 맞춰보는 겁니다. 여러분 이건 어려운게 아니라 귀찮은 문제 입니다.

이 녀석을 혼쭐 내줍시다.

🥽 소스코드 및 소스해석

해당소스는 프로그래머스에서 풀고 바로 가져온 코드 입니다.

키를 만들고 사방으로 끼우고 돌려서도 끼우고 다 해봅니다. 노동은 컴퓨터가 하잖아요?

#include <string>
#include <vector>

using namespace std;
void makeMyKey(vector<vector<int>>& key);
void makeMyTempKey(vector<vector<int>>& tempKey, int dir, int x, int y, int keysize, int locksize);
bool check(vector<vector<int>>& tempKey, vector<vector<int>>& lock);
int mykey[4][32][32];
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	makeMyKey(key);
	vector<vector<int>> tempKey(lock.size(), vector<int>(lock.size(), 0));
	for (int i = 0; i <= key.size() + lock.size(); i++) {
		for (int j = 0; j <= key.size() + lock.size(); j++) {
			for (int k = 0; k < 4; k++) {
				makeMyTempKey(tempKey, k, j, i, key.size(), lock.size());
				if (check(tempKey,lock)) {
					return true;
				}
			}
		}
	}
	return false;
}
void makeMyKey(vector<vector<int>>& key)
{
	int length = key.size();
	for (int i = 0, _i = 0; i < length; i++, _i++)
		for (int j = 0, _j = 0; j < length; j++, _j++)
			mykey[0][i][j] = key[i][j];
	for (int i = 0, _i = 0; i < length; i++, _i++)
		for (int j = 0, _j = length - 1; j < length; j++, _j--)
			mykey[1][i][j] = key[_j][_i];
	for (int i = 0, _i = 0; i < length; i++, _i++)
		for (int j = 0, _j = length - 1; j < length; j++, _j--)
			mykey[2][i][j] = mykey[1][_j][_i];
	for (int i = 0, _i = 0; i < length; i++, _i++)
		for (int j = 0, _j = length - 1; j < length; j++, _j--)
			mykey[3][i][j] = mykey[2][_j][_i];
}
void makeMyTempKey(vector<vector<int>>& tempKey, int dir, int x, int y, int keysize, int locksize) {
	int keyX = keysize - x;
	int keyY = keysize - y;

	for (int i = 0,_i = keyY; i < locksize; i++, _i++) {
		for (int j = 0, _j = keyX; j < locksize; j++, _j++)
		{
			if (_j >= keysize || _j < 0 || _i >= keysize || _i < 0) {
				tempKey[i][j] = 0;
			}
			else {
				tempKey[i][j] = mykey[dir][_i][_j];
			}
		}

	}
}
bool check(vector<vector<int>>& tempKey, vector<vector<int>>& lock) {
	int length = lock.size();
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length; j++)
		{
			if (lock[i][j] + tempKey[i][j] == 0 || lock[i][j] + tempKey[i][j] == 2)
				return false;
		}
	}
	return true;
}

🔨 문제 후기

Depth가 깊은거 같다구요? 네 맞습니다. 여러분이 짜실 때는 가능한 많이 줄여서 써주세요.

카카오는 구현능력을 많이 물어보는 것 같다. 하지만 많이 풀어본다면 너도 할 수 있다구!. 우리 사랑스러운 튜브 그림을 보는데 너무 귀엽다.

프로그래머스 2019 kakao 후보키 문제 해설

29 Sep 2020

#[프로그래머스][2019 kakao] 후보키 문제 해설

문제 요약

  • input 으로 들어오는 릴레이션의 정보를 토대로 후보키 를 생성할 수 있는가에 대한 문제
  • 최소성과 유일성을 만족해야한다
  • 유일성 : 해당하는 릴레이션에 대해 유일하게 식별 가능해야한다.
  • 최소성 : 키를 구성하는 속성 중 하나라도 제외 하는 경우 유일성이 사라지는 것을 의미한다. 즉 필요하지 않은 속성은 후보키에 포함되지 않아야 한다는 것.

    자세한 설명과 제한사항은 프로그래머스에서 확인바랍니다.

문제 풀이

가능한 모든 속성들의 조합을 만들고, 최소성과 유일성을 만족하는 조합만 추려내야한다. DFS, BFS, bit 등을 이용한 방법을 통해 유일성을 만족하는 부분집합을 만들고 각 조합들의 최소성과 검사하면 풀어나갈 수 있다.

예를 들면 속성(1 ,3)과 속성 (1, 2, 3) 후보키 집합이 존재한다면 후자는 최소성을 만족하지 못한다.

소스코드 및 소스해석

프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.

  • DFS 방법으로 먼저 유일성을 만족하는 모든 조합을 추려냅니다.
  • 각 속성의 상태를 저장한 ansVec 을 검사해 최소성을 만족하는 조합만 카운트 합니다.

    추가설명 : ansVec은 flag 용도로 쓰입니다. 0번 인덱스에 몇개의 속성을 가지고 있는지를 저장하고 각 1번 ~ 15번 인덱스에는 조합에서 사용하는 속성에 1의 값을 넣어 다른 조합들과 비교합니다. ansVec은 속성 수를 기준으로 한번 정렬을 했기 때문에 순서대로 비교하면 최소성을 만족하는 조합들만 카운트 할 수 있습니다.

#include <string>
#include <vector>
#include <algorithm>

//https://programmers.co.kr/learn/courses/30/lessons/42890

using namespace std;
void DFS(vector<vector<string>>& relation, vector<int> col);
bool check(vector<vector<string>>& relation, vector<int> col);
int solution(vector<vector<string>> relation);
bool comp(vector<int> a, vector<int> b) { return a[0] < b[0]; }
bool colChecked[16];
vector<vector<int>> ansVec;

int main() {
    //각각 2, 1, 2, 1 ,5 가 나와야함
    vector<vector<string>> relation = { {"100","ryan","music","2"},{"200","apeach","math","2"},{"300","tube","computer","3"},{"400","con","computer","4"},{"500","muzi","music","3"},{"600","apeach","music","2"} };
    vector<vector<string>> relation2 = { {"a","b","c"}, {"1","b","c"}, {"a","b","4"}, {"a","5","c"} };
    vector<vector<string>> relation3 = { {"a","1","4"}, {"2","1","5"}, {"a","2","4"} };
    vector<vector<string>> relation4 = { {"a","aa"}, {"aa","a"}, {"a","a"} };
    vector<vector<string>> relation5 = { {"b","2","a","a","b"},
{"b","2","7","1","b"},
{"1","0","a","a","8"},
{"7","5","a","a","9"},
{"3","0","a","f","9"} };
    solution(relation4);
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    for (int i = 0; i < relation[0].size(); i++) {
        colChecked[i] = true;
        DFS(relation, vector<int>(1,i));
        colChecked[i] = false;
    }
    //check overlapping element
    sort(ansVec.begin(), ansVec.end(), comp);
    for (int i = 0; i < ansVec.size(); i++) {
        for (int j = i + 1; j < ansVec.size(); j++)
        {
            int count = 0;
            for (int k = 1; k < 16; k++) {
                if (ansVec[i][k] == 1 && ansVec[j][k] == 1 ) count++;
            }
            if (count == ansVec[i][0] && count != 0)
                ansVec[j][0] = 0;
        }
    }
    for (int i = 0; i < ansVec.size(); i++) {
        if (ansVec[i][0] != 0)
            answer++;
    }
    return answer;
}
void DFS(vector<vector<string>> &relation, vector<int> col) {
    //col check implement
    if (col.size() > relation[0].size())
        return;
    if (check(relation, col))
        return;

    for (int i = col.back() + 1; i < relation[0].size();i++) {
        if (colChecked[i] == true) continue;
        colChecked[i] = true;
        col.push_back(i);
        //checked out and add new col
        DFS(relation, col);
        colChecked[i] = false;
        col.pop_back();
    }
}
bool check(vector<vector<string>> &relation, vector<int>col) {
    //check if relation with selected col could be primary key
    vector<string> myVec;
    for (int i = 0; i < relation.size(); i++) {
        string strtemp ="";
        for (int j = 0; j < col.size(); j++) {
            strtemp += relation[i][col[j]] + " ";
        }
        auto iter = find(myVec.begin(), myVec.end(), strtemp);
        if (iter == myVec.end())
            myVec.push_back(strtemp);
        else
            return false;
    }
    vector<int> temp(16, 0);
    temp[0] = col.size();
    for (size_t i = 0; i < col.size(); i++)
        temp[col[i] + 1] = 1;
    ansVec.push_back(temp);

    return true;
}

문제 후기

최소성에 대한 부분을 여러번 고쳤다. 다른 사람들의 풀이를 보면 대부분의 실패 원인은 최소성에 관한 코드에서 발생한다. 카카오는 전반적으로 문제 설명이 깔끔하고 예제를 잘 보여주며, 구현능력을 상당히 중요하게 생각한다는 느낌을 받았다.