언제쯔음

https://www.acmicpc.net/problem/2579https://koolreview.tistory.com/180 설탕배달, DP 기본 지식 1일차DP 문제임을 알고 풀며, DP 문제 풀이 방식에 익숙해지기 위해 해당 글을 씁니다. 해당 문제는 수학적으로도 해결이 가능하기도 합니다. 다만 완전 탐색(브루토포스)으로 해결이 가능하다는 점을koolreview.tistory.com DP 2일차, 사실 이 문제도 옛날에 풀었던 문제이지만, 그 당시에는 너무 어려워서 꽤나 괴로웠다. 그리고 정답 코드를 보고 너무 간단해서 좌절감을 느꼈었던 것 같다.지금의 나는 이전보다 많이 달라졌으니, 시작해보자.문제 위와 같은데 눈 여겨 볼만한 점은 3가지다.1. 1단계씩 올라가기, 2단계씩 올라가기2. 연속된 세..

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/16236상어가 사이즈가 1인 경우, 위 쪽 1과 아래쪽 1을 갈 수 있다. 이 때 문제에서 장애물에 대한 정의를 말하지 않았다.그렇기 때문에, BFS 문제라고 말했지만, 장애물이 없다는 사실에 착안해서 좌표끼리의 차이를 계산해서 거리를 계산했다.하지만 물고기가 장애물이라 사실을 몰랐다. 물고기가 좌표 사이에 있어서 무시하고 지나갈 수 있는 조건이 없기 때문에, 피해서 가야 한다. 그렇다면 피하기 위해서는 결국 해당 값을 확인해야 한다. 그렇기 때문에 좌표를 통해 직접 이동하지 않고 구할 수 있는 방법이 없었다.결국 BFS로 문제를 풀어야 하는 시뮬레이션 문제이다. 다시 BFS로 풀어야 겠다.

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을 하게 된다.인접 리스트는 다른 방법을 생각해보야 하는데, 이 문제는 트리 구조를 입력 값으로 주지 않기 때문에 위 ..