[BOJ] 백준 2887 행성 터널 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 x, y, z 좌표로 행성의 위치가 주어지고(노드), 그 행성들 사이의 거리가 가중치가 된다(간선). 행성과 행성 사이의 거리는 문제에 주어진 조건처럼 min(abs(x1-x2), abs(y1-y2), abs(z1-z2))가 된다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include #include using namespace std; class Planet { public: int x, y, z, index; Planet(int x, int y, int z, int index) { this->x = x; this->y = y; this->z = z; this->index = index; } }; class Tunne..

→2020.11.21

[프로그래머스] 가장 먼 노드 / 최단 경로, 다익스트라

💣 문제 이해 한 출발 정점에서 다른 모든 정점으로의 최단 경로 이동 비용을 계산하는 문제였다. 각 노드로 이동하는 최소 비용을 계산하여 그중 최대를 구한 후, 동일한 비용을 지불하는 경로의 수를 카운트 했다. 이 문제는 다익스트라 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; const int MAX = 20001; const int INF = 1e9; int dist[MAX] = {0, }; int solution(int n, vector edge) { int max_cost = 0; int result = 0; priority_queuepq; // 비용, 노드번호 vectornodes[n+1]; // 각..

→2020.11.21

[BOJ] 백준 1647 도시 분할 계획 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 최소 신장 트리를 구한 뒤, 마을을 두 개로 분할할 수 있도록 도로를 제거하여 총 유지비가 최소가 되도록 하면 된다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; class Road { public: int start, dest, weight; Road(int start, int dest, int weight) { this->start = start; this->dest = dest; this->weight = weight; } }; const int MAX = 1001; int home_cnt, road_cnt; vector roads; vector survived_lin..

→2020.11.20

[BOJ] 백준 1922 네트워크 연결 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 컴퓨터를 노드로, 선 연결을 간선으로 보고 주어진 그래프에서 최소 신장 트리(MST)의 합을 구하는 문제였다. 틀은 바뀌었지만 1197번 최소 스패닝 트리 와 그냥 동일하게 풀리는 문제이다. 크루스칼 알고리즘/프림 알고리즘 두 가지 방법으로 풀 수 있다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; class Line { public: int start, dest, weight; Line(int start, int dest, int weight) { this->start = start; this->dest = dest; this->weight = weight; } }; co..

→2020.11.19

[BOJ] 백준 14503 로봇 청소기 / 구현

💣 문제 이해 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 ..

→2020.11.06

[BOJ] 백준 2606 바이러스 / 너비 우선 탐색(BFS)

💣 문제 이해 1번 컴퓨터에 바이러스가 감염되면 이와 연결되어 바이러스에 감염되는 컴퓨터의 수를 구하는 문제이다. 1번 컴퓨터(노드)에 연결된 컴퓨터(노드) 개수를 구하면 된다. 너비 우선 탐색(BFS) 기법으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; int visited[101] = {0, }; int bfs(deque nodes) { int virused = 0; deque queue; // 1번 컴퓨터에서 시작, 방문 처리 queue.push_back(1); visited[1] = 1; while (!queue.empty()) { int now_node = queue.front(); queue.pop_fron..

→2020.11.05

[BOJ] 백준 1935 후위 표기식2 / 스택(Stack)

💣 문제 이해 후위 표기식과 각 피연산자에 대응하는 값들이 주어질 때, 그 식을 계산하는 문제이다. 스택(Stack)을 활용하여 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include using namespace std; int main() { string operation = ""; int numCnt = 0; int alphabet[30] = {0, }; stack oper_Stack; // 입력의 수와 후위 표기식 입력받기 cin >> numCnt >> operation; // 피연산자에 대응하는 값 입력받기 for (int i = 0; i > alphabet[i]; } for (int i = 0; i < operation.length()..

→2020.07.27

[BOJ] 백준 1918 후위 표기식 / 스택(Stack)

💣 문제 이해 후위 표기법(postfix)은 연산자가 피연산자 뒤에 위치하는 방법이다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다. 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성한다. 스택(Stack)을 활용하여 풀이했다. 💭 풀이 과정 C++ Stack 라이브러리를 참조하여 중위 표기법을 구현하였다. 작성 언어: C++ #include #include using namespace std; int main() { string expression = ""; stack s1; cin >> expression; for (int i = 0; i = 60) { // 피연산자 출력(모든 ..

→2020.07.18

[BOJ] 백준 10828 스택 / 스택(Stack)

💣 문제 이해 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성한다. 명령은 push, pop, top, size, empty로 총 다섯 가지이다. 스택(Stack) 단순 구현 문제이다. 💭 풀이 과정 C++ template을 활용하여 Linked-List로 스택을 구현하였다. 작성 언어: C++ #include using namespace std; template class Node { public: T value; Node *next; Node(): next(nullptr){} Node(T tValue, Node *tNext): value(tValue), next(tNext){} }; template class Stack { public: int size; Nod..

→2020.07.17

[2019 카카오 개발자 겨울 인턴십] 불량 사용자

💣 문제 이해 이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇 가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해야 한다. 💭 풀이 과정 먼저 banned_id 와 길이가 동일한 user_id 를 찾고, * 문자를 제외한 모든 문자가 동일하다면 같은 아이디라고 가정하고, 그 아이디의 인덱스를 저장한다. 각 banned_id 별로 가능한 user_id 후보가 한 개 이상이므로, 모든 조합의 수를 구하는 것이다. 동일한 조합의 중복이 가능하다면 곱하면 되지만, 중복을 허락하지 않으므로 체크해줘야 한다. 방법을 고민하다, 다른 풀이를 찾아보며 비트마스..

→2020.05.01