본문 바로가기

알고리즘/백준

 (263)
[백준] 2473번 : 세 용액 2473번: 세 용액 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 🤔 문제분석 한 용액을 선택한뒤에 투포인터를 활용하여 해당 용액과 더했을때 0과 가까운 수를 찾으면된다. 이것도 마찬가지로 더했을때 0보다 크다면 right값을 감소시키고 0보다 작다면 left값을 증가시키면서 값을 찾아나아가면 된다. 아래의 두 용액 문제를 풀면 세 용액도 위의 설명한대로 문제를 해결 할 수 있다. 2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 1..
[백준] 2470번 : 두 용액 2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 🤔 문제분석 정렬 + 투포인터 문제로 pleft, pright를 두고 data[pleft] + data[pright]를 더한 값이 0보다 클경우 pright값을 줄이고 0보다 작을 경우 pleft값을 줄여가며 최대한 0에 가까운 수를 찾는다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) data = list(map(int, input().spli..
[백준] 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값이 중복된 값을 카운팅 해..

티스토리툴바