Diary

https://www.acmicpc.net/problem/3020

문제 이해

동굴에는 종유석과 석순이 자랍니다. 석순은 밑에서 부터, 종유석은 위에서 부터 자랍니다. 개똥벌레는 이 장애물들을 피하지 않으며 뚫고 지나갑니다. 개똥벌레가 최소한의 장애물들을 부수며 갔을 때 부순 갯수와 그러한 루트가 몇개나 있는지 구하는 문제였습니다.

입출력 조건

시간초 제한은 1초, 동굴의 크기가 200,000 x 500,000이 최대크기라 절대 단순반복으로는 풀 수 없었습니다.

풀이

생각하느라 오래 걸렸었습니다.

입력을 받을 때 석순 혹은 종유석이 몇번높이까지 가있는지를 확인하여 저장하고 종유석은 끝나는 지점부터 위로, 석순은 끝나는 지점부터 아래로 누적합을 구해주었습니다. 한번 그려보면 쉽게 알 수 있습니다.

이렇게 구한 누적합을 가지고 높이별로 개똥벌레를 이동시켜 보고 정답을 구할 수 있었습니다.

에러 및 느낀 점

풀이 방법을 생각해 내기 어려운 문제였습니다.

처음에는 이분탐색인가 하였지만 누적합으로 문제를 해결하였습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/3020_%EA%B0%9C%EB%98%A5%EB%B2%8C%EB%A0%88.cpp

https://www.acmicpc.net/problem/1803

문제 이해

두개의 줄이 주어지고 해당 줄에는 사람들이 서있습니다.

각각의 사람들은 반대편 줄의 한 사람을 노려보고 있으며 노려보는 사람을 활로 쏘려고 합니다.

하지만 아무도 다치면 안되서 맞지않게 어떠한 사람은 방패를 들어야 합니다.

누가 방패를 들고 누가 활을 들어야 하는지 구하는 문제였습니다.

입출력 조건

시간초 제한은 2초, 각 중에는 최대 5만명의 사람이 있을 수 있었습니다.

풀이

당연히 위상정렬 문제로 생각을 하고 풀었습니다.

배열을 하나만 쓰기위해 두번째 줄의 사람은 n만큼 더해서 숫자를 부여해 주었습니다.

여기서 문제는 이 위상정렬 그래프에 싸이클이 존재한다는 것이였습니다.

만약 서로가 서로를 마주보는 상황이 생긴다면 일반적인 위상정렬로는 문제를 해결할 수 없었습니다.

그래서 저는 위상정렬을 수행하고, 만약 q가 비었는데 아직 탐색이 남은 정점이 남았다면, 그 정점들을 다시금 q에 넣어주었습니다.

에러 및 느낀 점

싸이클을 생각 못하고 문제를 해결하려다가 시간을 많이 뺏겼습니다. 결국 싸이클이 존재함을 인지하고 문제를 해결할 수 있었습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1803_%EB%AC%B4%EC%88%A0%20%EC%97%B0%EC%8A%B5.cpp

https://www.acmicpc.net/problem/16946

문제 이해

벽과 길로 이루어진 공간이 주어지고 벽을 허물었을 때 해당 지점에서 갈 수 있는 공간들의 크기를 구하는 문제였습니다.

입출력 조건

시간 제한은 2초, 공간의 크기는 최대 1,000x1,000 이였습니다.

풀이

처음에는 단순하게 벽인 지점마다 그냥 bfs 돌리면 되겠다 라는 생각을 했습니다.

그리고 그렇게 짰더니 시간초과가 떴습니다..1000x1000x1000을 하면 약 10억이 나오더군요

시간초과가 날만 한가..? 라는 생각이 들었습니다..

그래서 메모이제이션을 생각했습니다.

우선 0인 공간들을 먼저 탐색해서 해당 공간이 몇칸이지 확인하고, 이후에 1에서 bfs를 돌때 해당 이미 몇칸이 이어붙어있는 것인지 알고 있는 벽을 만나게 되면 queue에 넣지 않고 바로 더하면 되는 것이였습니다.

그렇게 풀었더니 중간 중간 시행착오는 많았지만 어찌어찌 해결할 수 있었습니다.

에러 및 느낀 점

시간을 많이 단축했다 생각을 했음에도 쓷레없이 visit를 처리하거나 이를 초기화 해주는 것에 시간을 많이 써서 시간초과가 여러번 더 났었습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16946_%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0%204.cpp

https://www.acmicpc.net/problem/1967

문제 이해

가중치가 있는 하나의 트리가 주어지면, 해당 트리에서 두 노드의 사이가 가장 긴 것을 찾아 그 값을 구하는 문제였습니다.(트리의 지름 구하기)

입출력 조건

시간제한은 2초, 노드의 최대 갯수는 10,000개 였습니다. dfs로 풀면 되겠다 싶었습니다.

풀이

비슷한 문제를 한번 푼 경험이 있어서 빨랐습니다.

하나의 노드에서 가장 멀리 있는 노드를 하나 찾으면, 그 노드는 트리의 지름의 2개의 노드 중 하나일 것입니다.

그렇게 하나의 노드를 찾고 나면 그 노드에서 가장 멀리 있는 노드를 찾으면 되는 문제였습니다.

에러 및 느낀 점

아마 방법을 생각하지 못했다면 시간이 꽤 걸렸을 것 같습니다..

쉽게 떠오르지 않는 해법이였습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1967_%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%A7%80%EB%A6%84.cpp

https://www.acmicpc.net/problem/14676

문제 이해

영선이와 영우가 게임을 하고 있습니다. (스타크래프트를 안다면 문제 이해가 쉬웠습니다) 게임에서는 건물을 만들거나 부술 수 있고 건물을 만들기 위해서는 사전에 만들어야 하는 건물이 있는 경우도 있습니다. 게임에는 치트키가 있는데 치트키를 쓰게 되면 건물을 마음대로 만들 수 있습니다. 영우가 게임에서 계속 이겨 영선이는 영우의 건물 건축 및 파괴 순서를 가져왔고(치트키로 만든 건물은 드러나지 않음) 이를 분석해 영우가 치트키를 썼는지 확인해야 하는 문제 였습니다.

입출력 조건

시간초 제한은 1초, 건물은 최대 10만개였으며 위상정렬 문제라는 것이 바로 알 수 있었기에 시간초과는 크게 신경쓰지 않았습니다.

풀이

전형적인 위상정렬 문제였습니다. queue대신 건물이 있는지의 여부를 따지는 배열을 하나 두었습니다.

한가지 주의할 점은 이미 있는건물을 또 여러개 만들 수 있다는 점이였습니다.

건물을 만들고 부숨에 따라 in_degree 배열을 더하거나 줄여주었고 건물의 갯수들도 신경 써 주었습니다.

에러 및 느낀 점

잘 짰는데..마지막에 j 대신 i를 넣는 멍청한 실수를 해서 에러가 한번 떴었습니다..

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/14676_%EC%98%81%EC%9A%B0%EB%8A%94%20%EC%82%AC%EA%B8%B0%EA%BE%BC%3F.cpp

https://www.acmicpc.net/problem/1043

문제 이해

진실과 과장을 섞어서 말하는 지민이가 있고 이미 진실을 알고 있는 사람의 번호가 주어집니다. 또 여러 파티가 있는데 해당 파티에 참여하는 인원들은 지민이가 거짓말을 하는지 안하는지를 공유할 수 있습니다. 진실을 알고 있는 사람들과 파티에 참여하는 사람들의 정보가 주어졌을 때 지민이가 과장해서 말할 수 있는 파티의 갯수를 구하는 문제였습니다.

입출력 조건

시간초 제한은 2초, 인원의 최대 수는 50명 이였기에 시간에 크게 구애받지 않는 문제였습니다.

풀이

문제를 보고 가장 먼저 떠오른 것은 유니온 파인드였습니다. 문제를 보면 결국 끝까지 모르는 한 집단과 결국 어떻게든 진실을 알게되는 집단, 이렇게 두개의 집단으로 나뉘어 지는 것을 알 수 있습니다. 그래서 유니온 파인드를 쓰고 파티에 참석하는 사람들이 진실을 알고 있는 집단과 함께 있는지만 확인해 주면 되었습니다.

에러 및 느낀 점

유니온 파인드 문제를 오랜만에 풀어봐서 구현하는 것에 조금 버벅임이 있었습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1043_%EA%B1%B0%EC%A7%93%EB%A7%90.cpp

https://www.acmicpc.net/problem/17143

문제 이해

RxC 크기의 격자 판이 주어지고 해당 격자에는 상어들이 존재 합니다. 상어들은 각각의 이동방향으로 움직이고 벽을 만나게 되면 진행방향을 반대로 돌려 이동합니다. 이동이 끝났을 때 겹치는 상어가 있다면 더 큰 상어가 작은 상어를 잡아먹게 되고, 낚시왕이 한칸씩 이동할 때마다 y열에서 가장 가까운 상어 하나씩을 잡을 수 있습니다. 낚시왕이 잡은 상어들의 크기의 합을 구하는 문제였습니다.

입출력 조건

시간초 제한은 1초였고, 격자 크기는 최대 100x100 입니다.

풀이

처음에는 단순히 구현하였습니다. 최대 1만 마리의 상어가 있고 마리당 최대 1000칸 이동할 수 있으니 반복문을 돌려도 1000만 이면 수행이 완료될거라 생각했습니다. 하지만 낚시왕도 최대 100칸까지 이동할 수 있어 1000만 * 100이 되어 10억이 되어 시간초과가 뜰 수 있었습니다. 그래서 규칙상 상하는 (R-1) * 2, 좌우는 (C-1) * 2이면 원상태로 복귀되기에 그것들로 나누어 해결하였습니다.

단순 구현이므로 아래 전체코드를 확인해 주시면 감사하겠습니다.

에러 및 느낀 점

시간 복잡도 계산을 좀 잘해야 할 거 같습니다..

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/17143_%EB%82%9A%EC%8B%9C%EC%99%95.cpp

https://www.acmicpc.net/problem/11909

문제 이해

2차원 배열이 주어지고 시작점에서 도착점까지 이동을 해야합니다. 이동의 오른쪽 혹은 아래로만 갈 수 있으며 이전칸에 있는 숫자보다 다음칸의 숫자가 크다면 이전칸이 더 커지도록 +1씩 올려줘야 한다. +1씩 올려주는 것을 최소로 하는 경로로 갔을 때 몇번 +1 했는지를 구하는 문제였습니다.

입출력 조건

시간제한은 2초였고 배열은 최대 2222x2222 까지였습니다.

풀이

pq를 사용하여 다익스트라와 비슷한 느낌으로 문제를 해결하였습니다. 여기서 놓쳤던 점은 굳이 넣지 않아도 되는 지점들을 중복적으로 넣어줘서 시간초과가 났었습니다. 이를 잘 배제해주는게 주요했던 것 같습니다.

에러 및 느낀 점

앞서 말했듯이 답에 문제는 없지만 쓸모없이 반복적으로 중복되는 값들을 계속 넣어줘서 시간초과가 났었습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/11909_%EB%B0%B0%EC%97%B4%20%ED%83%88%EC%B6%9C.cpp