Diary

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

문제 이해

문제의 난이도가 존재하며 정렬되어 나타납니다. 해당 문제사이에는 먼저 풀면 좋은 문제들이 있고 이들의 관계가 주어집니다. 난이도가 쉬운것 부터 푸는 것이 좋으며 가장 효율적으로 문제를 푸는 순서를 구하는 문제였습니다.

입출력 조건

시간초 제한은 2초, 문제의 최대 갯수는 32,000개 문제사이의 관계의 갯수는 최대 100,000개 였습니다. 

풀이

먼저 풀어서 좋은 것이 있다는 것은 결국 순서가 정해진다는 것이고 이는 결국 위상정렬을 뜻함을 쉽게 알 수 있었습니다.

또 문제들이 쉬운 순서대로 풀어야 한다는 점에서 pq를 써서 문제 번호가 작은 것 부터 나오게 한다면 해결할 수 있는 쉬운 문제였습니다.

에러 및 느낀 점

위상정렬 짱

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1766_%EB%AC%B8%EC%A0%9C%EC%A7%91.cpp

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

문제 이해

단방향 그래프가 주어지고 한 정점에서 파티를 합니다. 다른 정점들에서 해당 파티에 참여하기 위해 파티를 하는정점으로 이동하고, 다시 돌아가는 경로(가중치)가 가장 큰 값을 구하는 문제였습니다.

입출력 조건

시간 제한은 1초였으며 정점의 갯수는 1천개, 간선의 갯수는 1만개 까지였습니다.

풀이

다익스트라를 아는 사람이라면 최단거리라는 조건을 봤을 때 다익스트라를 쉽게 떠올릴 수 있으리라 생각합니다.

주의할 점은 양방향이 아닌 단방향 그래프이기 때문에 오고 가는 거리가 다를 수 있다는 점입니다.

이에 저는 각 정점에서 파티가 벌어지는 정점까지 다익스트라를 수행한 후, 파티를 하는 정점에서 다시 원래의 정점으로 다익스트라를 수행하여 해당 값을 더해주어 문제를 해결하였습니다.

에러 및 느낀 점

왜인지 memset이 먹히지 않아 틀렸었습니다...왜지..

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1238_%ED%8C%8C%ED%8B%B0.cpp

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

문제 이해

하나의 양방향 그래프가 주어지고, 한점에서 한점까지의 경로는 반드시 존재한다. 또 한 경로에서 가장 작은 비용을 기준점으로 잡게된다.

일정 값과 시작점이 주어졌을 때 해당 값을 넘는 값을 가지고 다른 점으로 이동할 수 있는 곳이 몇개인지를 구하는 문제였습니다.

입출력 조건

시간초 제한은 2초였고 최대 정점은 5000개 까지였습니다.

풀이

생각보다 쉽게 풀었습니다.

문제 이해가 어렵다 뿐이지 풀이는 어렵지 않았습니다.

잘생각해 보면, 시작정점에서 외부로 가는 정점의 가중치가 기준치보다 크다면 당연히 원하는 answer 값이 하나 커지는 것이고, visit 처리를 해주면서 이동한 정점에서 또 이동을 할 때 가중치가 기준치보다 크다면 +1을 해주면 되는 문제였습니다...

문제를 너무 어렵게 적어놨어요..

에러 및 느낀 점

문제를 잘 이해하면 참 쉬운 문제도 있구나 싶었습니다ㅏ

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/15591_MooTube%20(Silver).cpp 

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

문제 이해

최대 50x50 크기의 숲의 지도가 주어지고 시작점과 도착점, 그리고 쓰레기가 표시되어 있습니다. 시작점에서 도착점까지 가야하며 쓰레기를 최대한 안거쳐서 가야하고, 또 쓰레기를 어쩔수 없이 거치게 된다면, 같은양의 쓰레기를 거친 경로중 쓰레기와 인접한 길을 최소한으로 해서 갔을 때 쓰레기를 거치는 것과, 인접한 쓰레기를 거치는 것이 최소로 되게 도착하였을 때의 횟수들을 구하는 문제였습니다.

입출력 조건

시간제한은 2초였으며, 숲의 좌우 넢이는 최대 50x50 이였습니다.

풀이

처음에는 단순 무식하게 bfs로 풀었습니다

큰 배열 2개를 잡고, 하나는 해당 좌표까지 이동할 때 거친 쓰레기의 갯수를, 또하나의 배열에는 해당 좌표까지 이동할 때 거친 주변 쓰레기의 갯수를 저장하며 bfs를 돌았습니다. 이렇게 구현하다가 잘 안되서 바람 좀 쐬고 왔는데 문득, 이럴거면 그냥 pq에 두개다 집어넣어서 저절로 나오게 하면 되지 않나..? 라는 생각을 하게 되었고 여태 했던거 싹 지웠습니다 ㅡㅡ^;;

pq에다가 쓰레기 갯수, 주변 쓰레기 갯수, y좌표, x좌표 를 넣어주면 쓰레기 갯수가 같을 때 주변 쓰레기 갯수를 비교해서 저절로 작은 값부터 나오게 되어 편하게 풀 수 있겠다 생각했고 그렇게 풀었습니다!

에러 및 느낀 점

구현력이 부족했던 것인지 첫번째 방법으로 잘 해결이 되지 않았었습니다.

그리고 두번째 방법으로는 마지막에 도착지점은 횟수에서 제외한다라는 조건을 제대로 인지하지 못해 계속 틀렸었습니다..

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1445_%EC%9D%BC%EC%9A%94%EC%9D%BC%20%EC%95%84%EC%B9%A8%EC%9D%98%20%EB%8D%B0%EC%9D%B4%ED%8A%B8.cpp

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

문제 이해

주어지는 배열에서 연속하는 숫자들의 최대 합을 구하는 문제였습니다. 특이한 점은, 그중 한개의 숫자까지는 뺴버려도 된다는 것이였고, 또 주의할 점은 "1개의 숫자는 최소한 선택해야한다" 라는 점이였습니다.(여기서 꽤 틀림)

입출력 조건

시간초 제한은 2초였으며 최대 배열의 크기는 100,000개 였습니다. 여기서 한개씩 빼면서 탐색을 하게되면 100,000 * 100,000 으로 100억이 넘어가며 시간초과가 날 것이였기에, DP를 써야한다고 짐작할 수 있었습니다.

풀이

DP를 써야함을 알았지만 시간이 굉장히 오래 걸렸습니다. 식을 찾는데 오래걸렸고 이리저리 쓰다보니 결국 결과에 다다랐습니다.

문제에서 요구하는 i번째까지의 수 중 역속합이 최대가 되는 경우는 다음과 같이 3가지였습니다.

1. i번째 지금 한개의 값이 가장 큰 경우

2. i번째 지금 한개의 값을 빼고 앞선 값을 다 더한 경우

3. 이미 앞에서 한개를 빼고 i번째 값을 포함하며 가장 큰 경우

이렇게 설명하니 말이 조금 어려운데,

우선 dp배열을 dp[2][100001] 로 잡았고 dp[0][i]는 아무것도 빼지 않았을 때 i번째 까지 배열의 최대 연속합을 구한 값을 넣고 dp[1][i]는 한개를 뺐을 때 i번째 까지 배열의 최대 연속합을 구하였습니다.

dp[0][i] = max(dp[0][i-1] + now[i], now[i]) 로 생각을 할 수 있었고

dp[1][i]가 문제였습니다.

여기서 이제 저 앞선 3가지가 비교되게 됩니다.

이해하기 힘드실 수 있지만 제가 풀었던 노트입니다..

저렇게 생각하고 한번더 예시를 반복해 보니 확신이 생겼고 이후 코드를 작성하였습니다.

에러 및 느낀 점

1. 첫번째 놓쳤던 점은 문제에서 얘기한 최소 한개의 값을 가져야 한다는 것입니다. 만약 테스트케이스로 n=1, -1 이 주어졌다면 해당 값을 포함하지 않는 0이 가장 크게 나올 수 있는데 이는 명백히 문제에 반하는 내용이였습니다.

2. 최소값을 0으로 잡으면 안되었습니다. 최대값은 1억이구나 하고 int로 되겠네라고 생각하고 말았었는데, 최소값 또한 -1억 까지 갈 수 있어서 더 작은 값을 최초의 최소로 잡아 줄 필요가 있었습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/13398_%EC%97%B0%EC%86%8D%ED%95%A9%202.cpp

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

문제 이해

최대 10x10 크기의 게임판이 있고 해당 게임판에는 파란 구슬과 빨간 구슬이 있습니다. 또 빠져나올 수 있는 공간이 주어지며 파란구슬이 빠져나가지 않으면서 빨간 구슬이 빠져나가게 하는 문제였습니다. 게임판은 상하좌우 한쪽으로 쭉 이동할수만 있으며 10번안의 이동으로 게임을 클리어 할 수 있는지 묻는 문제였습니다.

입출력 조건

시간초 제한은 2초였으며 최대 게임판 크기가 10x10 크기임을 감안하면 dfs를 돌려도 괜찮겠다 생각하였습니다.

풀이

시간이 굉장히 많이 소모되었습니다.

첫번째로는 정말 하드코딩을 하였습니다. 상하좌우 끝까지 가는 함수들을 각각 하나씩 만들고 구슬들을 이동시키며 조건을 따져주었습니다. 결론적으로 굉장히 비효율적이고 코드도 더러웠으며 성공적인 구현도 하지 못했습니다.

다시 원점으로 돌아와(몇시간 걸린 코드들을 싹 지우고) 다시 천천히 dfs로 구현을 시작하였습니다. 이전의 상태를 유지하기 위해 원래의 게임판을 유지하는 배열을 뒀었지만, 몇줄 짜다보니 이럴 필요 없이 해당 시점의 빨간 구슬과 파란 구슬의 위치만 유지하면 된다는걸 깨달았습니다.(새삼 비효율적으로 산다 느낌) 그래서 구슬의 이동횟수와 빨간 구슬, 파란 구슬의 위치를 유지하며 dfs를 돌리되, 한쪽방향으로 끝까지 이동시켜 주었습니다.

초기에는 빨간 구슬과 파란구슬을 모두 조건에 넣어주며 일일이 비교했었지만, 그림을 그려 경로를 보던 와중, 빨간 구슬과 파란구슬을 신경쓰지 않고 이동시켜 준 후 두 구슬이 겹쳤을 때, 초기 모습에 빗대어 한칸 이동시켜 주면 되었습니다!

그래서 끝까지 이동시켜준 후, 해당 구슬 두개가 겹치면 조건을 걸어 또 한칸 이동하게끔 하였습니다.

전체 코드는 아래를 참고해 주시면 감사하겠습니다.

에러 및 느낀 점

하드코딩을 했음에도 구현하지 못해 구현력이 부족하였고, 길을 찾아는 갔지만 시간이 너무 오래걸렸다는 점이 아쉬웠습니다..

또한가지...영어 대문자 O를 0으로 착각하여 if문에 걸리지 않아 삽질을 꽤나 했었습니다...ㅡ^ㅡ

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/13459_%EA%B5%AC%EC%8A%AC%20%ED%83%88%EC%B6%9C.cpp

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

문제 이해

나라를 세운 건국자가 있고 그 자식들이 표현이 되어있습니다. 해당 자식은 한세대를 거칠 수록 부모의 혈통의 1/2을 이어 받게 됩니다.

만약 건국자와 건국자와 관련  없는 인물 사이에서 태어난 인물의 혈통은 1/2가 되는 것이고, 1/2의 혈통을 가진 인물과 아무런 관계없는 인물 사이에서 아이가 태어나면 1/4 + 0 으로 1/4의 혈통을 가진 아이가 태어나게 되는 것입니다.

건국자와 아이와 부모의 관계가 주어질 때 자신이 왕위를 계승해야 한다고 주장하는 인물 중 가장 높은 혈통을 가진 인물을 찾는 문제였습니다.

입출력 조건

시간 제한은 1초, 3명의 인물 씩 총 50줄 주어질 수 있으므로 최대 인물의 수는 150명 정도가 가능했습니다.

또 주어지는 자식조건이 50줄이라는 뜻과 같으므로 depth는 최대 50이라고 생각하였습니다.

풀이

첫번째로 문제를 풀때 너무 쉽게 생각했었습니다.map에 <string,long long>으로 잡아주고 건국자는 2^50을 넣어줬습니다.(최대 depth가 50이였기에 자연수 단위로 해결하기 위해) 이후 입력을 받음과 동시에 해당 인물이 이미 나왔던 인물인지를 확인하고 자식에게는 부모의 절반의 숫자를 더 더해주는 식으로 문제를 해결하였습니다. 우연찮게 테스트케이스도 모두 맞아 떨어지며 문제를 해결한 것 처럼 보였지만 게속 5%에서 틀렸다고 하였습니다...

알고보니, 뒤늦게 나오는 정보에서 앞선 인물의 정보가 나오는 경우가 있었습니다. 그래서 앞선 방법은 바로 폐기처분 해버렸습니당

먼저 입력을 다 받고, 인물을 정점으로, 관계를 간선으로 생각하기로 했습니다. 그렇게 되었을 때 자식에게는 2개의 in_degree가 추가가 되게 되고 in_degree가 0인 부모 노드부터 처리하며 해당 부모의 value의 1/2만큼 씩 자식에게 추가되도록 코드를 구현해 주었습니다.

알고보니 위상정렬 문제였던 것입니다..!

에러 및 느낀 점

역시 처음에는 방법이 잘못되어 많은 에러를 발생시켰습니다.

두번째로 제대로 된 방법을 이용했을 때는, 최대 50줄이 설명됨으로 단순히 최대 50명까지 나올 수 있구나 라고 생각하여 배열의 크기가 부족한 문제가 있었습니다.

또 두번째는 테스트 용으로 2^10으로 잡아뒀던 것을 고치지 않아 틀렸습니다가 발생했었습니다...^^;;

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/5021_%EC%99%95%EC%9C%84%20%EA%B3%84%EC%8A%B9.cpp

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

문제 이해

1000이하의 숫자 N이 주어졌을 때 N자리의 숫자 중에 오르막 수로만 된 수의 갯수를 찾는 문제였습니다.

오르막 수란 앞에서부터 뒤로 갈때 앞의 숫자가 뒤의 숫자보다 같거나 작은 숫자를 말합니다.

입출력 조건

시간 제한은 1초였으며 숫자의 크기는 굉장히 커지지만 문제의 조건 중 10007로 나눈 숫자를 나타내라 하였기에 그대로 int를 사용해 주었습니다.

풀이

생각보다 오래 걸렸습니다.

제가 DP를 잘 못하는 것도 있었지만 바로 도식화를 하려고 했던게 더 오래 걸렸던 이유라고 생각합니다.

규칙은 어느정도 감이 왔었지만 이를 수식화 하려니 생각보다 머리가 안돌아 갔었습니다.

해당 문제는 N이 3일 때 까지의 경우를 직접 해보고 나서 제대로 수식화 할 수 있었습니다.

dp[i][j]로 배열을 잡았고 j는 j자리 수를 뜻하며, i는 앞자리 수를 나타내었습니다. 또 해당 값은 그까지의 경우의 수를 넣어줬습니다.

예를 들어 dp[1][2]는 앞자리 수가 1이고 길이가 2인 경우의 수를 뜻합니다.

앞자리 수 가 0 이면 해당 숫자 뒤에는 0~9까지 10개의 경우의 수가 있을 수 있고, 앞자리 수가 1이면 1~9까지 총 9개의 경우의 수가 뒤에 올 수 있습니다. 이를 표로 채워 본다면 

위와 같이 나오게 됩니다

이를 수식으로 하여 코드로 구현하게 되면 아래와 같은 모습이 나옵니다.

에러 및 느낀 점

DP문제라는 확신은 문제를 보자마자 가질 수 있었지만, 간단한 문제였음에도 규칙을 찾아내고 수식화하는 것에 어려움을 느꼈습니다.

DP문제를 많이 풀어볼 필요가 있겠습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/11057_%EC%98%A4%EB%A5%B4%EB%A7%89%20%EC%88%98.cpp