[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] 백준 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

[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

[BOJ] 백준 11055 가장 큰 증가 부분 수열 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 앞의 문제 11053번 가장 긴 증가하는 부분 수열 과 거의 유사하다. 동적 계획법 풀이 작성 언어: C++ #include int biggestIncreasingSeq (int arr[][1010], int size) { int sumMax = 0, l_result = 0; for (int i = 0; i < size; ++i) { for (int j = 0; j < i; ++j) { if (arr[..

→2020.04.27

[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 수열 A = {10, 20, 10, 30, 20, 50}인 경우 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 생각보다 풀이과정은 간단했다. 계속해서 DP 문제를 풀이하며 풀이 접근 방식 감을 잘 잡는 게 중요한 것 같다. 동적 계획법 풀이 작성 언어: C++ #include using namespace std; int longestSeqLength(int (*dpArr)[1010], int arrSize) { int max = 0, longest = 0; for (int i = 0; i < arrSize; ++i) { for (int j = 0; j..

→2020.04.24

[BOJ] 백준 9251 LCS / 동적 계획법(Dynamic-Programming)

💣 문제 이해 많이 알려진 Longest Common Sequence(LCS) 문제이다. 두 문자열이 입력으로 주어질 때, 이 두 문자열의 공통되는 부분 중 가장 긴 문자열의 길이를 출력하는 문제이다. 이 외국 유튜버의 풀이 를 참고하며 3가지 풀이로 접근해보았다. 1. 재귀 (Recursion) 2. 메모이제이션 (Memoization) 3. 동적 계획법 (Dynamic Programming) 💭 풀이 과정 1. 재귀 방식의 풀이 작성 언어: C++ #include // c 표준 입출력 #include // std::max char str1[1001], str2[1001]; int LCS_recurs(int index1, int index2){ if (str1[index1] == '\0' || str2..

→2020.03.14