pseong

Good Bye 2022: 2023 is NEAR 본문

알고리즘/알고리즘 문제풀이

Good Bye 2022: 2023 is NEAR

pseong 2023. 1. 4. 02:45

번은 코포에 자주 등장하는 배열 조작 문제였다. 그냥 가장 작은 것을 바꿔주면 된다는 생각에 우선순위 큐 풀이가 생각났고 그렇게 풀었더니 맞았다. 추 후 답지를 보니 좀 더 깔끔하게 푼 풀이가 있었지만 어차피 시간 복잡도는 똑같으니까 그냥 넘어가는 게 나을 것 같다.

B번은 구성적 문제인데 주어진 수식을 만족하는 순열을 하나 찾아서 출력하는 문제였다. 정말 문제 그대로 주어진 수식대로 구성만 하면 되었다.

C번은 5틀 하고 맞아서 250점이나 깎였다. 처음에는 굉장히 단순하게 생각해서 차이가 짝수인지 홀수인지만 판별해서 제출했는데 알고 보니 아니었다. 그래서 좀 더 생각해 보다가 공약수라는 것의 특징에 대해서 생각해 봤다. 공약수는 생각해 보면 두 수의 차이가 존재하고 두 수의 공약수는 항상 그 차이보다 커질 수가 없다. 그리고 두 수의 공약수는 두 수의 차이의 약수만 공약수가 될 수 있다. 따라서 두 수의 최대공약수가 1이 되려면 두 수가 두 수의 차이의 1을 제외한 모든 약수의 배수가 되면 안 된다. 여기까지 생각하는데 쫌 오래 걸렸다. 이유는 방금 설명한 공약수의 특징에 대해 생각을 못했기 때문이다. 아무튼 이 것을 구현하는 데에는 맵을 사용 했지만 답지 코드를 보니 좀 더 간단했다. 아직 해석은 안 했지만 조만간 다시 제대로 읽어봐야겠다. 그리고 처음에 굉장히 풀이 방향을 잘못 생각하고 제출을 했는데 이제부턴 꼭 증명까지 하고 제출을 해야겠다. 그리고 정수론 너무 끔찍하다.

D번은 시간 내에 못 풀었는데 사실 문제 방향을 굉장히 잘못 잡았다. 일단 순열을 만들게 한다는 것에서 한 원소가 정해지면 다른 쪽에서는 그 원소가 나오면 안 된다는 사실을 왜인지는 모르겠으나 간과하고 있었다. 이 문제는 풀이를 보고 이해했지만 순열이라는 특징을 좀 더 잡아냈었으면 풀었을지도 모를 문제였다. 풀이를 간략하게 적어 보면 먼저 두 개의 노드를 양방향으로 추가해 준다. 1부터 차례대로 확인하면서 방문하지 않은 노드가 있다면 그 노드부터 탐색을 시작하는데 만약 탐색한 노드들의 개수와 그 노드 들과 연결된 간선이 1 : 2 비율이 되지 않는다면 해가 존재하지 않는다는 것이고 탐색한 노드들에 셀프 노드가 있다면 정답에 n을 곱해주고 셀프 노드가 없다면 정답에 2를 곱해준다. 아무튼 순열이 나온다면 어찌 댔건 그래프 풀이는 한 번쯤 꼭 생각해 봐야 된다.

Comments