언제쯔음

DP 문제임을 알고 풀며, DP 문제 풀이 방식에 익숙해지기 위해 해당 글을 씁니다. 해당 문제는 수학적으로도 해결이 가능하기도 합니다. 다만 완전 탐색(브루토포스)으로 해결이 가능하다는 점을 눈 여겨 봐야 합니다.주먹구구식 방식으로 해결이 가능하다는 점과 문제를 재귀로 해결이 가능하다는 점을 보았을 때 중첩된 하위 구조의 특징을 가지고 있다는 점을 알 수 있고, 이를 통해 DP로 해결이 가능하다는 점을 알 수 있습니다.중첩된 하위 구조를 가지고 있다는 것을 어떻게 알 수 있을까요? 재귀를 타고 내려감에 따라 호출된 똑같은 값이 있다면 이전에 계산된 값을 쓰면 되기에 최적화가 가능합니다. DP의 첫번째글이니까 더 적어 보려 합니다. 이름이 왜 DP일까요?, 흔히 말하는 DP 테이블, 메모제이션이 있다고 ..

https://www.acmicpc.net/problem/2493해당 문제는 뒤에 있는 탑에서 앞에 있는 탑 중 자신과 가까운 제일 큰 탑을 찾는 문제이다.위 그림을 토대로 정답을 보자면 다음과 같다.0 0 2 2 4나도 그랬고, 다른 사람도 다음과 같이 생각하지 않았을까?  1. 백준에서 스택을 활용하는 문제이니까, 스택을 어디다 쓰지? 어디다 쓸까?   1-1. 스택의 특징이 무엇이지? FILO, LIFO이지? 2. 반복문을 통해서 뒤에서 앞으로 이동하며 큰 탑을 찾아볼까? 먼저 2번부터 본다면, 해당 입력 값의 크기가 N은 1 이상 500,000이하임으로 N^2 만 되도 약 10억번을 넘어간다는 사실을 알 수 있기에 이중 포문 이상으로는 사용하지 못한다. 그렇다면 해당 문제를 어떻게 풀어야 할까? ..

https://www.acmicpc.net/problem/17144문제 읽고, 생각해보기문제를 읽어보다면, 특별한 점은 기존의 BFS에 공기 청정기가 하나 추가되고, 배열 내 값이 이동한다는 점이다.해당 사항의 대해 순서대로 어떻게 진행되는지도 친절하게 되어 있다.해당 문제에서 요구하는 기술은 BFS와 배열 회전이라고 생각된다.다만 해당 글을 쓰는 이유는 그 2가지를 제대로 못해서, 참회하고자, 기억하고자 적는다.먼저 문제에서는 공기 청정기에 대한 정의가 있다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 해당 내용을 통해 이후 회전 방법에 대해 고민될 부분이 조금 적어진다.그 다음은 미세먼지가 확산되는 방법은 기존 토마토? 관련되어 비슷하니 넘어가도 좋을 것 같다.(어차피 아..

https://www.acmicpc.net/problem/12851시간 복잡도 계산=>  현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다N이 10^5  임으로  O(N^2) 해결할 수 없고, 그 하위로 풀어야 한다.BFS는 정점의 개수 10^5, 간선의 수 3개 O(V) 안에 해결 가능하다.visisted를 while 안과, for문 안 탐색할 때 처리가 가능한데, 이에 대한 이유를 알 수 있었던 문제라고 생각된다.#include#include#includeusing namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; c..

https://www.acmicpc.net/problem/30805문제는 백준에서 읽을 수 있습니다.해당 문제는 solved.ac에서 4 클래스 문제를 다 풀기 위해서 문제를 해결하려고 했으나, 너무 오래 걸렸다.문제에서는 해당 부분을 주의 깊게 보면 좋다. 처음에 봤을 때 무슨 말인지 감이 안 왔다.예제 값과 문제의 설명을 함께 본다면, 무조건 큰 값이 앞에 오면 된다는 내용을 이해할 수 있다.그러니까 크게 문제의 시간 복잡도도 그렇게 높지도 않기 때문에 DP까지 갈 필요가 없는 문제이기도 하고, 무조건 공통 값 중 큰 값이 앞으로 오면 된다는 점을 착안해서 문제를 풀 수 있다.내가 오래걸린 문제일단 다른 사람들의 해결 방법을 보았을 때 살짝 어지러웠다. 문제에서는 공통 값 중 큰 값 순으로 나열하면 ..

https://www.acmicpc.net/problem/5639이 문제를 해결하기 위해서는 이진 트리의 특징과 전위 순회 특징에 대한 이해가 있어야 해결할 수 있는 문제이다.=> 즉, 트리의 특징을 제대로 이해했는지 확인하는 기본적인 문제이다.먼저 이진 트리의 특징을 간단하게 생각해보자.1. 2개의 자식 노드를 가진다.이 특징으로 인해 실제 자료구조를 구현 시 배열, 인접 리스트, 포인터 등을 고려해볼 수 있게 된다.또한 배열로 구현하게 된다면 Root 노드는 기본적으로 인덱스 1에 두는 방식을 사용하고 왼쪽 자식 노드는  2 * root index, 오른쪽 노드는 2 * root +1을 하게 된다.인접 리스트는 다른 방법을 생각해보야 하는데, 이 문제는 트리 구조를 입력 값으로 주지 않기 때문에 위 ..

https://www.acmicpc.net/problem/15686생각의 흐름1.최대 M개를 고르라는 말의 의미는 무엇이지?=> 최대 M개를 안 고르는 경우도 있나?2. 치킨집을 제거한다고 하는 경우, 다른 치킨집의 거리에 영향이 가는가?=> 좌표로 계산하기 때문에 영향이 없음.=> 1번은 모르겠으나, 2번의 특성을 본다면, 모든 경우의 수를 탐색해서 계산하면 그만이겠다는 생각이 들었다.=> 조금 느릴 것 같은데, 빠르게 하는 방법은 없을까? => 그리디?근데 N이 50이라 워낙 수가 작아서 총 칸이 250이고, 집은 커봐야 2N이라 100 밖에 안 된다는 생각에 모든 경우의 수를 구하려고 했다.=> 마음에 걸리는 요소는 1번, M개 이건 뭐지?조합.. 😑 👍조합을 구현하고, 계산의 요소를 추가한 문..

https://www.acmicpc.net/problem/14442 문제 설명보다는 키포인트를 짚어보겠다. 1. 벽을 부수고 이동한다는 의미기본: 2차원 배열에서 상하좌우로 이동하며 최단 경로를 찾아간다. 응용: k번 만큼 막혀있는 길인 1을 뚫고 지나갈 수 있다. => K번 만큼 길을 뚫고 가는 상태를 visited 배열 상에 나타내야 한다. 어느 분의 말에 따른다면 뚫고 간 상태와 안 뚫고 간 상태를 나타내기 위해서는 차원이 늘어야 한다고 말을 한다. 말이 어렵긴 한데, 자연스럽게 생각해보면 좋을 것 같다.2. Enum 사용enum RoadType { ROAD, BLOCK }; 회사에 취직하기 전엔 코테에서 사용하지 않았던 문법인데 더 알아보기 쉽지 않나 싶어서 써보았다.3.배열의 크기를 미리 선언 ..