Algorithm
-
백준 2252 - 줄 세우기Algorithm/Sorting 2024. 2. 16. 09:12
2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 오늘 포스팅 해볼 문제는 백준 2252 - 줄 세우기 문제이다. 이 문제의 경우 전형적인 위상정렬 문제인데, 그렇다면 위상정렬이란 무엇일까? ※ 위상정렬이란? - 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미한다. 특정한 노드로 들어오는 간선의 개수를 진입차수라 한다. 1. 진입차수가 0인 노드를 큐에 담는다. 2. 큐가 비어있을 때까지 다음..
-
백준 1082 - 방 번호Algorithm/Dynamic Programming 2024. 1. 25. 09:44
1082번: 방 번호 (acmicpc.net) 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 이번주에 알고리즘 공유 문제는 방 번호 문제이다. 이 문제는 dynamic programming과 Greedy Algorithm을 모두 떠올려야하는 문제로 점화식 작성을 할 때 Greedy를 생각하지 않으면 쉽사리 작성할 수 없는 문제이다. 문제를 먼저 이해해보자. 예제 입력 1 복사 3 6 7 8 21 예제 출력 1 복사 210 이렇게 6 7 8 을 입력받게 될 때 방 번호는 각각 0 1 2가 될 것이다. 방 가격 : 6 7 8 방 번호 : 0 1 2 이런 모습이 나오게 되는데 여기서 ..
-
백준 1052 - 물병Algorithm/Greedy 2024. 1. 16. 09:29
1052번: 물병 (acmicpc.net) 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 요즘 근래 너무 골드3 문제에 치여서 좀 쉬운 문제를 풀면서 다시 코테 흥미를 높여볼까 생각하면서 실버1 문제를 건드려보았다. 근데 이게 뭔가 싶은데... 누가봐도 그리디 문제인데, 뭐 도통 이해가 안되는 문제를 만나서 한참을 헤메게 되었다. 이 문제를 스터디원들과 꼭 공유해보고자 블로그를 작성한다. ※ 문제의 규칙성 이 문제는 규칙을 발견하면 사실상 문제가 끝난다고 보면된다. 코드도 정말 간단하기 때문에... 충격적이었다...
-
백준 1174 - 우주신과의 교감Algorithm/Graph 2024. 1. 14. 11:29
1774번: 우주신과의 교감 (acmicpc.net) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제를 살펴보면서 "새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자." 이 문장과 좌표들을 입력받는 것을 통해 거리의 합을 구하고, 최소가 될 수 있는 통로를 만들어주어야 한다고 생각했다. 문제를 보면 예전에 풀어보았던 최소 스패닝 트리 문제가 떠오르게 되어, 전체적인 알고리즘을 최소 스패닝 트리 문제와 동일하게 가져갔다. ..
-
백준 1956 - 운동Algorithm/Graph 2024. 1. 7. 13:02
1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 이 문제를 처음보고 solved.ac에서 본 그래프 문제들과 굉장히 유사한 문제라는 생각이 들게 되었다. 그 문제들도 cost, start, end를 설정해서 list 형태로 append 시켜놓고, 알고리즘을 사용하게 되는데, 이 때 graph 알고리즘이라면 BFS, DFS 등이 있을 수 있겠지만, 나의 첫번째 접근은 "도로의 길이의 합이 최소"라는 지점에 착안하여 다익스트라 알고리즘을..
-
수학(유형정리) - 백준 1747Algorithm/Math 2023. 6. 29. 09:43
1747번: 소수&팰린드롬 (acmicpc.net) 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 첫째 줄에 조건을 만족하..
-
그리디(유형정리) - 백준 20300Algorithm/Greedy 2023. 6. 28. 11:23
20300번: 서강근육맨 (acmicpc.net) 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 문제 로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다. 헬스장에 있는 �$N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지..
-
그리디(유형정리) - 백준 13305Algorithm/Greedy 2023. 6. 28. 10:31
13305번: 주유소 (acmicpc.net) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마..