풀이 과정 1. 어떠한 값을 특정 범위 안에서 탐색하면서 최대, 최소값을 구하는 문제이므로 이분탐색을 생각함. 2. left , right를 설정하고 mid가 최종 내가 잘라야하는 나무 높이로 설정하여 문제를 해결. 헷갈렸던 부분. - mid 값의 갱신 위치가 left , right보다 위에 있게 된다면 해당 값의 결과 반영이 while 조건문에 들어갈때 반영이 안되므로 1칸씩 밀리게 된다 따라서 mid값의 초기화는 left와 right의 결과값에 따라 반영해야 하고 아니면 answer 로 right 값을 내보내야 한다. 코드#include #include #include using namespace std; bool Cut_Tree_Result(vector& _vecTree, int cut_he..

-------------------------------------------------------------------------------------------------------------------------------------------------- 문제 풀이 1. 해당 문제는 주어진 데이터를 바탕으로 이진 트리를 구성하고, 각 노드를 Depth(깊이)별로 나누어 층(Level)을 구성하는 문제로 판단했다. 2. depth 별로 나누면서 계속 층을 나누면서 탐색하기 위해서는 dfs 알고리즘을 떠올랐고 재귀 함수를 통해 이진 트리를 구현했다. ------------------------------------------------------------------------------..

------------------------------------------------------------------------------------------------------------------------------------------- 문제풀이 1. 문제를 풀 수 있는 방법은 DFS 알고리즘과 DP 알고리즘이 떠올랐다. 하지만 이 문제는 최종 최댓값만을 원하므로 DP 알고리즘이 시간복잡도 면에서 더 좋다 생각하여 DP 알고리즘으로 풀게 되었고, 또한 DP 알고리즘 특성상 이전 값의 계산한 결과를 저장해두고 동일한 부분 문제가 다시 등장할 때 재 사용함으로써 중복 계산을 제거할 수 있기 때문인 이유도 있다. 2. 즉, 이전 메모리 값을 활용하면 좋은 문제임을 알아서 다음 단계로..

------------------------------------------------------------------------------------------------------------------------------------------------ 문제 접근 방법 1. 최단 경로를 찾으면서 모든 경로를 탐색해야 하므로 BFS 알고리즘을 사용하였습니다. 2. 문제 풀이 중 각 인덱스 초과의 경우 및 갔던 곳은 재방문 하지 않도록 해야 최단경로 이므로 길을 지나갈 때 마다 이전 "경로 비용 + 1" 을 하여 경로 비용을 계산하였습니다. -----------------------------------------------------------------------------------..

--------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 처음에 문제를 접했을 때 문제를 해결 방식을 소분화 하여 생각했다. 어떻게 검사를 시작할지 ( ex 모든 색종이가 파란색 or 하얀색 / 색종이를 어떻게 분할 할지 등) 2. 계속 생각하던 중 색종이가 계속 자기 분열 즉 재귀적으로 계속 분할하는 것을 볼 수 있어서 DFS 알고리즘이 생각났다. 3. 따라서 DFS 알고리즘을 사용하며 해당 색종이가 분할하면 4개의 색종이가 생기므로 ..

----------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서 1. 해당 문제를 처음 볼 때 이해가 잘 안되었다. 감소하는 수? 천천히 문제를 이해해 보니 각 자리수의 가장 맨 앞에서 오름차순으로 내려가는 987654321 이렇게 형태를 갖춰야 하는것이 감소하는 수의 정의 이다. 2. 해당 문제 접근 방법으로는 첫 번째 string을 이용하여 모든 자리수를 구분하여 비교하는 방법이다. 이 방법은 965821의 경우 965까지 가서 8..

----------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 문제를 보면 경우의 수가 여러가지인 경우인 문제이다. 처음에는 각 집마다 색을 선택하는 경우가 2가지씩 생기므로 계속해서 완전 탐색한다면 ( 2^n) 복잡도 경우의 수가 기하급수적으로 증가하게 되므로 이 문제에 옳치 않은 풀이 방법이라 생각했습니다. 2. 따라서 이전의 결과값을 저장하고 재활용하는 Dynamic Programming을 사용하여 각 집을 특정 색으로 칠했을 때..

-----------------------------------------------------------------------------------------------------------------------------------------------------------------접근 순서 1. 해당 문제는 서로 연결되었는지를 BFS 알고리즘으로 생각하여 풀이를 시작함. 2. 입력에서 띄어쓰기가 없는 하나의 숫자로 들어오므로 string으로 받고 해당 문자를 char 형태로 접근하여 해당 문자를 2차원 배열로 접근 3. 다녀간 곳은 visited vector를 사용하여 기록하여 갔던 곳과 안갔던 곳을 구별함. ------------------------------------------..

----------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 해당 문제는 시간제한이 0.25초로 빡빡한 문제로 일반적인 DFS 구조를 사용해서 재귀함수를 호출 하면서 O(2^n)씩 해당되므로 c++ 1초당 계산이 약 10^8인 것을 계산하면 해당 방법으로는 문제를 해결할 수 없음을 알 수 있다. 2. DP 방법을 이용하는데 DP는 이전에 구한 값을 미리 저장해 두고 재사용하여 불필요한 함수 호출과 중복 계산을 제거하는 방식이다. ----------..

--------------------------------------------------------------------------------------------------------------------------------------------------------------- 문제 접근 순서. 1. 어떠한 원소를 찾아야 하는 문제이므로 hash 자료형을 이용할 생각. 2. hash에서 rehash(재해싱)에 관한 문제가 생길수 있으므로 반드시 미리 공간을 확보한 다음 사용하기 ( 안할 시 N=100000 기준 으로 O(N) 리해싱 복잡도가 14번 나오므로 시간 초과를 유발함) -----------------------------------------------------------..