종난아! 공부하자!

문제 문제 링크: https://www.acmicpc.net/problem/14500 DFS로 문제를 푸는 것은 인지를 하였으나, 직접적으로 코딩을 하지는 못하였습니다.오늘도 많은 부족함을 느끼는 날입니다. 열심히 하다보면 자연히 늘겠죠...? 문제에 대해 검색해보니 많은 분들이 DFS를 사용하여 풀었습니다. 혹시 문제를 보고 바로 오...하나가 이상하네? 라고 찾으신 분은 DFS에 대해서 정확히 이해 하셨을꺼라 생각됩니다.저는 검색을 하고나서야 알게 되었네요...ㅎㅎㅎ;; ㅗ 모양은 DFS로 탐색이 불가능합니다. 따라서 ㅗ 모양만 다른 방법으로 찾아야합니다.살짝 문제를 꼬아낸것 같습니다. 도형을 탐색 하면서 해당 칸의 수를 더해가면서 최댓값을 구하면 되는 문제였습니다.찾아보면 또..은근 쉬워 보입니다...

문제문제 링크: https://www.acmicpc.net/problem/14501 문제를 보면 DP로 풀 수 있다는 것을 알 수 있습니다.검색을 해본 결과 DFS로도 풀 수 있다는 것을 알게되었습니다.문제를 풀때 꼭 한 방법만이 아닌 다른 방법도 생각하는 습관을 들이는 것이 좋을것 같습니다.ㅎㅎ;; 이 문제는 상담을 하거나 안하거나 둘중 하나를 고르는 것이 관건인 문제입니다. DP의 경우는 점화식을 세워서 문제를 풀며, 점화식은 max(dp(day+1), dp(day+T[day])+P[day]) 입니다.전자 의 경우는 상담을 안 하였을때의 식이며, 후자의 경우는 상담을 하였을 때의 식입니다.T[day]는 해당 날짜의 상담을 했을 경우 걸리는 시간이며, P[day]는 그에 따른 보수입니다. DFS 경우에..

문제문제 링크: https://www.acmicpc.net/problem/14502문제를 보자마자 "아! 이거는 DFS나 BFS로 풀면 되겠다!" 라고 생각이 들어서 무작정 풀었다가 큰코를 다쳤습니다....해당 문제를 푸는 과정은 다음과 같습니다.연구소 상황을 입력 받는다.받은 연구소 상황을 다른 배열에 복사한다.복사한 연구소에서 안전구역인 곳에 3개의 벽을 세운다.벽을 세운 상태에서 바이러스를 퍼트린다.다 퍼트린 후, 안전 구역의 수를 센다.구역의 수를 기존의 저장값과 비교하여 최대인지 확인한다.모든 벽을 세울 수 있는 경우를 계산 할 때까지 3번과정부터 반복한다.해결 방식을 세우는것은 간단 하였으나... 3번 과정에서 많은 시간을 투자하게 되었습니다... 3개의 벽을 세울때, 입력 받는 연구소의 크기..

문제문제 링크: https://www.acmicpc.net/problem/2667 문제 링크: https://www.acmicpc.net/problem/4963위 두 문제는 해결하는데 있어 많이 유사하기 때문에 같이 포스팅을 하게되었습니다. 두 문제 전부 DFS 혹은 BFS를 사용하여 해결 할 수 있습니다. 저의 경우는 DFS 방법으로 문제를 해결하였습니다. 문제 푸는데 있어 핵심은 움직임에 있습니다. 2667번의 경우, 상·하·좌·우로만 움직일 수 있습니다. 따라서 움직일 수 있는 방향을 먼저 지정을 해주어야 합니다.4963번의 경우에는 상·하·좌·우 뿐만아니라 대각선까지 움직일 수 있습니다. 8개의 방향 모두 지정해주어야 합니다. 또, 중요한 것은 주어진 지도를 벗어나면 안된다는 것입니다. 범위를 주..

문제문제 링크: https://www.acmicpc.net/problem/1707이분 그래프란?☞모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을포함하도록 색칠 할수 있는 그래프.출처: https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 ▼ 이분 그래프의 예시해당 문제는 주어지는 그래프가 이분 그래프인지를 확인하는 문제입니다. 예시를 보면 "하나의 정점에서 연결된 다른 정점들의 색상은 다르다" 인 것을 확인 할 수 있습니다. 이분 그래프의 특징을 이용하여 문제를 푸는 것이 핵심입니다. DFS 혹은 BFS로 그래프를 탐색을 하여 이미 방문했던 정점을 확인할 때, 만약 자신과 같은 색상을 가지고 있다..

문제문제 링크: https://www.acmicpc.net/problem/11052 해당 문제의 경우는 다이나믹 프로그래밍으로 생각하는 것이 가장 중요합니다.저 또한 문제를 보았을때, 아직까지는 정확히 어떤것을 먼저 해야되고 어떠한 식으로 접근을 해야되는지 감이 오질 않아 많이 힘든 부분도 있습니다. 하지만 언젠가는 익숙 하겠지요? D[i]를 붕어빵 i개를 팔아 얻을 수 있는 최대 수익, P[i]는 붕어빵 i개로 이루어진 세트메뉴의 가격이라고 합시다. 총 i개의 붕어빵 중에서 1개를 P[1]에 판다면 남은 붕어빵의 개수는 i-1개이며 얻을 수 있는 최대 이익은 D[i-1] 입니다.→ 총 수익 : P[1] + D[i-1] 총 i개의 붕어빵 중에서 2개를 P[2]에 판다면, 남은 붕어빵의 개수는 i-2개이며..

문제문제 링크: https://www.acmicpc.net/problem/1463 이 문제의 경우, 입력값에 대해 2로 나누어지는 값이라면 2로 나누고, 3으로 나누어 지는 값이라면 3으로 나눕니다. 두가지에도 포함이 되지 않는다면, 1을 빼어 1이 될 때 까지 연산을 합니다. 이때, 연산을 최소한으로 하는 방법을 구하는 문제로, 다이나믹 프로그래밍을 사용하면 간단히 풀 수 있습니다. 저의 경우는 Top-Down 방식으로만 풀어 올렸지만, Bottom-Up 방식으로도 해보는 것을 추천합니다. 다이나믹 프로그래밍에서는 점화식을 찾아내는것이 가장 중요합니다.해당 문제의 점화식의 경우는 3가지로 나눌 수 있으며, 선택지가 많을 경우 저장된 값을 확인 후에 저장 된 값보다 새로운 값이 작다면이를 저장하는 방식으..

문제 이 문제는 스택을 이용하여 푸는 문제이다. 문제의 핵심은 ')'를 만났을 때 레이저인지 막대기의 끝인지 구별해 내는 것이다. 먼저 '('를 만났을 때는 스택에 push를 해준다. ')' 를 만났을 때는 스택에서 pop을 해준다. ')'은 막대기의 끝을 나타낼 수도 있고, 레이저를 나타낼 수도 있다.이 2가지의 경우를 나누는 방법은 레이저는 바로 직전의 문자가 '('이라는 것이다. 따라서 이전의 문자를 보면서 이 둘을 구별할 수 있다. 잘려진 막대기의 개수를 구하는 방법은 레이저를 만났을 때는 스택에 쌓여있는 '('의 개수만큼 더해주고, 막대기의 끝을 만났을때는 1만큼만 더해준다.레이저를 만났을 때 막대기가 몇개가 있는가에 따라서 잘려나간 막대기의 수가 정해지며, 막대기의 끝을 만났을 때에는 해당 막..