[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

[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

💣 문제 이해 문자열 처리를 필요로 하는 문제이다. 주어진 문자열에서 1개 단위, 2개 단위, 3개 단위, 등으로 문자열을 자를 때, 연속된 문자열을 2a2ba3c와 같이 압축한다. 연속된 문자가 1 자리인 경우, 앞에 숫자를 생략하고 문자만 기입한다. 💭 풀이 과정 작성 언어: Python3 def solution(s): answer = 9999 size = len(s) # 한 자리 문자열의 경우 바로 결과 출력 if size == 1: return 1 for i in range(1, size // 2 + 1): temp = s[:i] count = 0 compressed = '' for x in range(0, size, i): if s[x:x + i] == temp: count += 1 else: ..

→2020.09.01

[BOJ] 백준 7576 토마토 / 너비 우선 탐색(BFS)

💣 문제 이해 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성한다. 너비 우선 탐색(BFS) 기법으로 풀이했다. 💭 풀이 과정 작성 언어: Python from collections import deque def bfs(t_m, t_n, t_box): day = -1 mx = [-1, 1, 0, 0] my = [0, 0, -1, 1] while riped_index: # 하루 씩 증가 day += 1 queue_size = len(riped_index) for _ in..

→2020.08.31

[2018 KAKAO BLIND RECRUITMENT] 다트 게임

💣 문제 이해 문자열 처리를 필요로 하는 문제이다. 카카오에서는 정말 빠질 수 없나봄... 총 3번의 게임이 있고 각 게임마다 0~10점의 정수형 점수, S/D/T로 각 1제곱, 2제곱 3제곱을 하는 영역 점수, 옵션으로 * 또는 #이 주어진다. *는 해당 점수와 바로 전에 얻은 점수를 각 2배로 만들고, #는 해당 점수를 마이너스로 만든다. 첫 번째 기회에서 *가 나온 경우, 이전 점수가 없으므로 해당 점수만 2배가 된다. 정규표현식을 사용해서 언급된 규칙에 따라 문자열을 나눠 처리했다. 💭 풀이 과정 작성 언어: Python3 import re def solution(t_dartresult): score_list = [1, 1, 1] groups = re.findall(r'\d{1,2}[SDT][*#..

→2020.08.29

[2019 KAKAO BLIND RECRUITMENT] 실패율

💣 문제 이해 정렬을 이용하는 게 포인트인듯한 문제이다. 딕셔너리를 사용했고, Key 값은 1~N까지의 스테이지 번호, Value 값은 각 스테이지의 실패율을 담는다. 딕셔너리의 Value 값인 실패율을 key 로 하여 내림차순 정렬을 수행한다.정렬된 딕셔너리의 Key 값이 문제에서 요구하는 순위가 된다. 💭 풀이 과정 작성 언어: Python3 import operator def solution(t_n, t_stages): answer = [] user_left = len(t_stages) stages_dict = {num: 0 for num in range(1, t_n + 1)} # 실패율 계산 for key in stages_dict.keys(): if user_left != 0: user_cnt ..

→2020.08.29