본문 바로가기

알고리즘

 (305)
[백준] 2212번 : 센서 2212번: 센서 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 🤔 문제분석 센서데이터를 그룹핑 하는 문제로 각각의 센서를 그래프로 생각하고, 양 옆에 이웃하는 센서끼리의 거리를 구한뒤, 가장 긴 거리를 k-1 개를 제거한다면 k개의 그룹이 생성되고 가장 긴 거리를 제거 했기때문에 남은 나머지의 간선을 모두 더한다면 수신가능한 영역의 길이의 합이 나온다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) K = int(inpu..
[백준] 1461번 : 도서관 1461번: 도서관 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 🤔 문제분석 가장 큰 수는 마지막에 돌아가지 않아야함으로, 제일 마지막에 방문한다. 제일 작은수부터 쌍으로 방문해나아간다. 거리에는 마이너스 값과 플러스값이 있는데 둘이 구분을 해주어야한다. 마이너스 위치에서 플러스 위치로가려면 0을 지나가야하기때문에 구분해서 문제를 풀어도 상관이 없다. 저는 마이너스와 플러스를 구분하여 배열을 생성하였고, 마지막에 도착지점으로부터 첫번째 도착지점까지를 거꾸로 순회하게 문제를 해결하였습니다. search 함수는 마..
[백준] 13904번 : 과제 13904번: 과제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 🤔 문제분석 서로소 집합, 우선순위 큐 두가지로 문제를 해결하였다. 서로소 집합으로 문제를 해결할때에는 과제의 가중치를 기준으로 내림차순 정렬하였고, 우선순위큐는 과제 걸리는 시간 기준으로 오름차순 정렬하여 문제를 해결 하였다. 서로소 집합 문제는 과제를 완료한뒤에, 현재 날짜와 현재 날짜 -1 를 유니온하여, 다음 리터레이션에서 현재날짜를 파인드 하였을때 0이게 된다면 과제를 할 수 없는 상황임으로 과제를 해결 할 수 없는 상황이다. 그 상황을 제외하고는 과제를 해결 할 수 있으므로 정..
[백준] 2457번 : 공주님의 정원 2457번: 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 🤔 문제분석 시작날짜, 끝나는 날짜 오름차순으로 정렬하여 순회하면서, 현재의 시작시간에서 다음의 가장 끝나는시간이 긴 날짜를 선택하여 문제를 해결 할 수 있다. 두개의 케이스로 문제를 해결하였는데 배열을 순회하는 방식과, 스택을 활용하는 방식 두가지로 문제를 해결하였다. 두가지 모두 현재의 시작 날짜에서 가장 늦게 끝나는 날짜를 선택하는 해야한다. 💻 코드 배열 순회 방식 import sys input = sys.s..
[백준] 8980번 : 택배 8980번: 택배 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 🤔 문제분석 정렬문제로, 정렬을 도착지점 기준으로 정렬하면 된다. 도착지점을 정렬하는 이유는 도착지점이 이른 곳일수록 짐을 빠르게 내릴 수 있기때문이다. 💻 코드 import sys input = sys.stdin.readline N, C = map(int, input().split()) M = int(input()) delivery = [] house = [C for _ in range(N+1)] for _ in range..
[백준] 7453번 : 합이 0인 네 정수 7453번: 합이 0인 네 정수 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 🤔 문제분석 투포인터 및 정렬문제로, A,B,C,D를 입력받고, A배열과 B배열을 합하여 AB배열을 만들고, C배열과 D배열을 합하여 CD배열을 만듭니다. 만든 배열을 정렬을하고, AB는 왼쪽으로부터 오른쪽으로 CD는 오른쪽으로부터 왼쪽으로 순회해 가면서 두개의 값이 0보다 클경우, 작을경우, 0과 같을 경우로 분기하여 문제를 해결합니다. 여기서 중요한점은 0이 되었을때 AB 혹은 CD값이 중복된 값을 카운팅 해..
[백준] 1253번 : 좋다 1253번: 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🤔 문제분석 N이 2000보다 작거나 같기때문에 시간복잡도는 O(n^2)으로 생각 할 수 있고 정렬 + 투포인터로 문제를 해결 할 수 있다. 입력받은 배열을 정렬한뒤 배열을 오름차순으로 순회하면서 해당수가 좋은 수인지 아닌지 판단한다. 좋은 수 인지 아닌지 판단하는 방법을 투포인터를 활용하여 해결한다. left = 0, right = len(arr)- 1로 둔다. arr[left]와 arr[right]를 더하여 현재 값과 비교를하고, 만약 값이 더 크다면 right값을 감..
[백준] 2109번 : 순회강연 2109번: 순회강연 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 🤔 문제분석 두가지의 방식으로 문제를 풀어보았습니다. 처음에 제가 풀은 방식은 유니온-파인드를 응용하여 문제를 해결하였고, 정답 판정을 받은뒤에 다른사람은 어떻게 풀었을까 풀이를 참조해보니, 우선순위큐를 활용하여 문제를 해결하신분이 있어서 풀이를 참조하였습니다. 유니온-파인드 유니온-파인으로 문제를 해결할때에는 정렬을 p의 내림차순을 정렬한뒤에 순회합니다. 파인드 : 문제에서 이야기한 d일안에 강연을 만족..

티스토리툴바