BOJ
-
[Python 3] BOJ - 2933 "미네랄"BOJ 2021. 8. 3. 21:46
# 문제 링크 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net # 풀이 개인적으로 이 문제에서의 핵심은 문제에서 제시한 공중에 떠있는 클러스터의 처리라고 생각한다. 물론 BFS가 필요하나, 단순한 BFS이기 때문에 그것보다는 공중에 떠있는 클러스터가 내려오는 경우에 해당하는 다양한 조건이 좀 더 복잡했다. 단순하게 접근하면 어떤 클러스터의 가장 밑부분의 미네랄이 최초로 닿는 지점까지 움직이는 것이다 위 그림 1에서 반례를 볼 수 있다. 이 경우에는 굳이 빨간..
-
[Python 3] BOJ - 14395 "4연산"BOJ 2021. 8. 2. 14:27
# 문제 링크 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net # 풀이 개인적으로 문제의 핵심은 그래프로 모델링을 하는 것이라 생각한다. 현재 수를 노드라고 본다면, 각각의 연산은 간선이며, 이어지는 노드는 현재수에 연산을 한 결과가 된다. 따라서 가중치가 모두 1인 무향 그래프와 같고, 이 때 연산의 최소값, 즉 최단거리를 구하라고 하였으므로 BFS를 통해 정답을 구할 수 있다. 또한 여러개가 답인 경우 사전순으로 앞서는 것을 출력하라..
-
[Python 3] BOJ - 9663 "N-Queen"BOJ 2021. 7. 1. 22:47
# 문제 링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 각 열(행)과 대각선을 효율적으로 처리하는 것이라 생각한다. 우선적으로 퀸이 어떻게 움직이는 지 알아보자 위 그림과 같이 퀸이 존재하는 칸을 기준으로 해당 행,열, 4방향 대각선에는 다른 퀸을 놓을 수 없다. 따라서, 만일 행을 기준으로 생각한다면, i번째 행에 하나의 퀸을 놓는다면 (이 때 어느 열인지는 중요하지 않다) i번째 행에 또다른 퀸을 놓는 것..
-
[Python 3] BOJ - 1744 "수 묶기"BOJ 2020. 9. 16. 17:54
# 문제 링크 : https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 0, 1의 처리라고 생각한다. 만일, 0, 1이 쿼리 내에 들어오지 않는다면 음수와 양수의 두 리스트로 나누어 음수는 오름차순으로, 양수는 내림차순으로 정렬 후 짝수개 씩 묶어준 후 곱한다. 이후 쌍으로 묶이지 않는 음수와 양수를 모두 더해주면 된다. 그런데 0, 1이 쿼리 내에 들어오지 않는다는 가정이 없기 때문에, 각각의 경우에 대하..
-
[Python 3] BOJ - 1722 "순열의 순서"BOJ 2020. 9. 15. 00:19
# 문제 링크 : https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지�� www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 분할정복이라고 생각한다. 물론 분할정복 없이도 풀 수 있다. 구현해야 함수가 2개인데, 이 중 어떤 순열이 몇번째 순열인지 판별하는 것은 쉽다. 그러나 개인적으로는 특정 위치의 순열을 구하는 것이 조금 더 어렵다고 생각한다. 현재 n = 4인 순열의 경우를 고려한다고 가정하자. 그런데 가장 앞자리만 놓고 본다면, 그 수..
-
[Python 3] BOJ - 1707 "이분 그래프"BOJ 2020. 7. 8. 15:55
# 문제 링크 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 BFS/DFS라고 생각한다. 조금 더 구체적으로는 정점을 방문했는지 체크하는 배열의 응용이라고 생각한다. 이분 그래프란 어떤 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프이다. 그림 1에서 세 그래프 모두 이분 그래프이다. 세 그래프 모두 (1,2) / (3,4)의 ..
-
[Python 3] BOJ - 1701 "Cubeditor"BOJ 2020. 7. 8. 14:30
# 문제 링크 : https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net # 풀이 : 이 문제의 핵심은 failure 배열의 이해이다. 우선 failure 배열이 무엇인지 알기전에 문제의 설명에 대해 예시를 통해 이해해보자. 문제의 설명의 골자는 현재 어떤 문자열 s에서 2번 이상 나타나는 부분문자열 중 길이가 가장 긴 것의 길이를 출력하라는 것이다. 현재 그림 1은 길이가 1이고 최소 2번 이상 출현하는 부..
-
[Python 3] BOJ - 1697 "숨바꼭질"BOJ 2020. 6. 25. 10:42
# 문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 BFS라고 생각한다. 비록 문제에 직접적으로 그래프는 없지만 BFS형식으로 풀 수 있다. BFS/DFS의 핵심은 정점을 한번만 방문하는 것이다. 그런데 이 문제에서 만일 2초 후 위치가 7이 된다고 가정하자. 그런데 또 5초 후 위치가 7이라면 이는 방문하지 않아도 된다. 왜냐하면 만일 동생의 위치가 7이라면 2..