백준

1. 문제 설명 링크 : https://www.acmicpc.net/problem/11672. 풀이과정문제 해결의 흐름  트리에서 임의의 두 점 사이의 거리에 대하여 가장 긴 거리를 찾는 문제이기에 임의의 두 점 사이의 거리를 모두 구해 가장 긴 거리를 찾는 방법을 떠올렸습니다. 즉, 완전탐색과 BFS를 결합하여 문제를 풀고자 하였습니다. 하지만 아래와 같은 트리 구조를 예로 들어봤을 때, 굳이 완전탐색을 적용하여 모든 점을 탐색할 필요 없이 더 간단하게 풀 수 있는 방법이 있지 않을까 고민했습니다. 1 / \ 2 3 / \ 4 5 \ 6    3. BFS는 특정 노드에서 출발하여 모든 노드를 ..

1. 문제 설명링크 : https://www.acmicpc.net/problem/15042. 풀이 과정문제 해결의 흐름 제목, 입력값, 요구사항을 파악해보면 최단 경로 문제, 그중에서도 가중치 그래프에서 특정 시작점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 '다익스트라 알고리즘'을 활용하는 문제 유형임을 쉽게 파악 가능합니다. 따라서 이 문제는 다익스트라 알고리즘을 사용하며 다음 2가지 조건을 만족시키는 경우의 최단 경로를 구해야 합니다. 조건 1 : 1~N까지 이동할 때 반드시 두 정점 v1, v2를 거쳐야 한다.조건 2 : 한 번 이동하였던 정점과 간선은 다시 이동할 수 있다.위 2가지 조건을 만족하는 최단 거리는 다음 2가지 경우뿐이라고 생각되었습니다.경우 1 : 1 -> v1 -> v2..

1. 문제 설명링크 : https://www.acmicpc.net/problem/11492. 풀이 과정문제 해결의 흐름  우선, 문제 설명을 읽고 나서 DP 문제일 거 같다는 느낌이 강하게 들었습니다. 동적계획법, DP(Dynamic Programming)이란?중복되는 계산 결과를 저장하여 복잡한 문제를 더 작은 하위 문제들로 나누어 해결하는 기법입니다.이 기법은 다음 2가지 특징을 가진 문제에서 주로 사용됩니다!최적 부분 구조 : 문제를 작은 부분 문제들로 나누어 부분 문제들의 최적해를 구하여 최종적으로 전체 문제의 최적해를 구할 수 있는 구조 중복 부분 문제 : 동일한 부분 문제가 여러 번 반복되어 나타나는 구조 이 문제를 DP로 접근해야하는 이유는 이웃한 집의 색깔은 서로 달라야하는 조건 하에 모든..

1. 문제 설명링크 : https://www.acmicpc.net/problem/117232. 풀이 과정문제 해결의 흐름  처음에는 문제 제목처럼 집합 STL (std::set)을 사용하는 문제라고 생각하고 풀었더니 시간 초과로 문제가 자꾸 틀렸습니다! 입출력 시간도 줄여보고 여러 시도를 해봤지만, 이 방법은 정답이 아닌듯 보였습니다. 그래서 배열로 해결할까 고민하던 중 알고리즘 분류를 까보니 비트마스킹으로 풀어야하더라구요! 한번도 풀어본 적 없는 풀이법이라 많이 당황하였지만 CS 과목을 들으며 비트 연산에 익숙해졌기에 도전해보았습니다. 비트마스킹이란? 이진수 비트들을 활용하여 데이터를 효율적으로 저장하고 조작하는 기법메모리 절약, 속도 측면에서 엄청난 장점이 있음 비트마스킹을 통해 특정 비트를 1, 0..

1. 문제 설명링크 : https://www.acmicpc.net/problem/15829 문제에서 주어진 해시 함수 식과 주어진 문자열을 바탕으로 해시값을 계산해내는 간단한 문제였습니다!2. 풀이 과정문제 해결의 흐름 우선, 입력 문자열의 각 문자를 정수값으로 변환하는 과정을 거쳤습니다. 처음엔 int(str[i]) - 96과 같은 방식으로 변환하였는데 아래 코드와 같이 변환하는 것이 더욱 깔끔하다고 느껴 바꿨습니다. 이후 pow 함수를 사용하여 해시 함수식을 정확히 계산해 낸 거 같았는데 자꾸 50점에서 그치더라구요 ㅠㅠ. 원인은 2가지로, 입력 크기와 오버플로우 때문이었습니다. 입력 문자열의 길이 L이 최대 50으로 짧아 보였지만, r**i 값은 기하급수적으로 커져 연산 범위를 초과할 가능성이 있었..

1. 문제 설명링크 : https://www.acmicpc.net/problem/27982. 풀이 과정문제 해결의 흐름 보통 1초의 제한은 약 1억회 연산을 수행할 수 있는 기준이며, N(카드의 개수)가 최대 100개이므로 3중 for문을 사용할 경우 최대 백만회의 연산을 수행하므로 주어진 시간 내에 해결 가능하다고 판단하였습니다. 세 수의 합이 M을 초과하는 경우에는 break문을 사용하여 탐색을 중단하도록 효율을 높였습니다.#include #include using namespace std;int main() { // 0. 입력 받기 int N, M; // N(3 > N >> M; int num_lst[N]; for (int i = 0; i > num_lst[i]; } ..

1. 문제 설명문제 바로가기2. 풀이 과정문제 해결의 흐름     1. 2493 탑 문제와 굉장히 비슷하지만 이 문제는 이전에 추가된 자료가 아닌 새롭게 추가된 자료에 대해 조건을 걸어주어야할듯 하다!    2. 새롭게 추가되는 빌딩의 높이가 직전에 추가된 빌딩의 높이보다 높거나 같다면 이전에 추가된 빌딩의 관리자는 새롭게 추가된 빌딩을 보지 못한다.    3. 쉽게 생각해본다면 이전에 추가된 빌딩들보다 낮은 높이의 빌딩이 추가된다면 계속 빌딩을 볼 수 있다.    4. 반면, 이전 빌딩보다 높이가 높거나 같은 빌딩이 추가된다면 이전 빌딩의 관리자는 더 이상 추가되는 빌딩을 볼 수 없기에 삭제해주어야 한다.    5. 이 문제 역시 새롭게 추가되는 자료와 이전에 추가된 자료에 대해 관심이 깊으니 후입후출..

1. 문제 설명문제 바로가기2. 풀이 과정문제 해결의 흐름     1. 탑의 높이가 하나씩 추가되는 형태군!! 추가될 때마다 출력할지 한 번에 결과를 출력할지 생각해봐야겠다.     2. 음.. 탑의 높이가 추가될 때마다 바로 직전에 추가된 탑의 높이와 비교하는게 어떨까? 만약 추가된 탑의 높이가 더 크다면 바로 직전 탑이 수신을 절대 받지 못할 것이고, 이전에 추가된 탑의 높이가 더 크다면 수신을 받을 수 있겠군!!!     3. 이를 다음과 같이 구체화하여 조건문으로 나타내면 쉽게 풀 수 있을듯! 아래 조건문에 맞지 않는 높이는 수신을 받을 수 없기 때문에 삭제 처리해면 될듯 if (새로 추가되는 높이     4.  후입선출의 자료에 관심이 크기에 stack을 사용하여 풀어보자!! 코드 #includ..