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을 하게 된다.인접 리스트는 다른 방법을 생각해보야 하는데, 이 문제는 트리 구조를 입력 값으로 주지 않기 때문에 위 ..
보호되어 있는 글입니다.
https://www.acmicpc.net/problem/1967문제의 초점을 트리보다는 직관적인 부분을 고려해서 문제를 설명해보려고 한다.증명보다는 이미 알고 있는 지식, 직관으로부터 문제를 해결해보자.문제에서는 정점끼리의 가장 긴 길이를 물어보고 있다.위 그림에서 가장 긴 선은 무엇인가? A와 C를 잇는 선이다.왜? AC 선분이 제일 길까? 그냥 제일 길어서다.긴 선분보다 정점의 관점에서 다시 바라보자.가장 멀리 있는 정점 2개를 고르면 가장 긴 길이를 갖는 선분을 가지게 된다.그렇다면 가장 멀리있는 정점 2개를 어떻게 고를까?A에서 C가 가장 멀다.B에서 C가 가장 멀다. D에서 C가 가장 멀다. C에서 D가 가장 멀다.가장 먼 정점은 어느 정점을 골라도 2개로 좁혀진다.이에 대한 설명을 귀류법으로..
https://www.acmicpc.net/problem/1043지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일..
https://www.acmicpc.net/problem/17070문제를 읽다보면 입력 값에 N(3 ≤ N ≤ 16)란 정보를 알 수 있다. 해당 정보에 따라 무언가 백트래킹으로 해결이 가능함을 엿볼 수 있다.그도 그럴게 파이프는 계속 오른쪽으로 옮겨지니, 경우의수가 적지 않을까 싶은 생각도 있었다.다만 이전과 다르게 해당 문제는 파이프가 2개의 칸을 차지 하고 있는 이미지로 인해 어떻게 백트래킹을 구현할 수 있을지 고민이 된다.=> 2개의 좌표로 인해 백트래킹이 어렵다면, 일단 하나의 좌표로 백트래킹을 구현할 수 없는지 고민해보았다.결국 다음 좌표를 결정하는 것은 오른쪽, 아래 등 이동한 좌표의 지점이다. 그렇기 때문에 해당 좌표만 가지고 백트래킹을 구현해보면 간단하게 해결 가능하다.그리고 백트래킹을 ..
https://www.acmicpc.net/problem/15686생각의 흐름1.최대 M개를 고르라는 말의 의미는 무엇이지?=> 최대 M개를 안 고르는 경우도 있나?2. 치킨집을 제거한다고 하는 경우, 다른 치킨집의 거리에 영향이 가는가?=> 좌표로 계산하기 때문에 영향이 없음.=> 1번은 모르겠으나, 2번의 특성을 본다면, 모든 경우의 수를 탐색해서 계산하면 그만이겠다는 생각이 들었다.=> 조금 느릴 것 같은데, 빠르게 하는 방법은 없을까? => 그리디?근데 N이 50이라 워낙 수가 작아서 총 칸이 250이고, 집은 커봐야 2N이라 100 밖에 안 된다는 생각에 모든 경우의 수를 구하려고 했다.=> 마음에 걸리는 요소는 1번, M개 이건 뭐지?조합.. 😑 👍조합을 구현하고, 계산의 요소를 추가한 문..