국밥 개발자

백준-1806 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀의 입력 받은 값의 구간합 배열을 만든다. 투포인터를 이용하여 왼쪽은 구간합 시작점 오른쪽은 구간합의 끝점으로 사용한다. 구간합의 값이 S 보다 작을 경우 오른쪽 포인터를 이동 목표 합 보다 크고 길이가 짧은 경우 정답을 갱신 구간합의 값이 S 보다 클 경우 왼쪽 포인터를 이동 한다. 구간 합을 못찾을 경우 0을 반환 코드 (Python) import sy..

백준-9251 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀의 두 문자를 글자마다 비교할 2차원 배열을 생성한다. 문자 하나를 기준을 잡는다. 두번째 문자열과 비교하면서 값을 업데이트 한다. 문자열이 동일한 경우 : 이전 dp의 1을 더한값을 저장한다. 문자열이 다른 경우 : 이전 좌표의 값들중 큰값을 저장한다. 코드 (Python) import sys def input(): retu..

백준-1915 : 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀의 1 되어있을 경우 좌, 우, 좌상 값중 가장 작은 값에 1을 더한 값으로 메트릭스 수정한다. 갱신 후 결과값보다 크면 결과 값을 갱신한다. 놓쳤던 부분 1행 1열 부터 확인하여 0행과, 0열에 1의 값이 있고 그외에 값이 0일때의 케이스를 놓쳤었음 코드 (Python) import sys def input(): return sys.stdin.readline().rstrip() n, m = map(int, input().spli..

백준-11000 : 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀의 입력 받은 강의 정보들을 시작 시간 기준으로 정렬한다. 우선순위 큐에 강의 정보의 첫번쨰 값의 끝나는 시간을 넣어준다. 강의 리스트를 순회하며 우선순위 큐의 첫번째 값보다 작다면 해당 강의실에서 강의 가능한 값이므로 끝나는 값으로갱신한다. 우선순위 큐의 첫번째 값보다 크다면 강의실을 하나더 추가해야 함으로 끝나는 값을 우선순위 큐에 넣어준다. 코드 (Python) import sys import heapq ..

백준-2473 : 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀의 투 포인트 알고리즘을 사용하기 위해 입력 받은 ph 정보를 정렬을 한다. 앞에서부터 기준을 하나씩 잡고 기준이 되는 음수값의 합을 구하기위해 투 포인트 알고리즘을 사용한다. 코드 (Python) import sys def input(): return sys.stdin.readline().rstrip() size = int(input()) ph_..

백준-20551 : Sort 마스터 배지훈의 후계자 https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 풀의 입력 받은 숫자들을 오름차순으로 정렬한다. 2진 탐색을 활용하여 가장 먼저 찾은 index를 반환하고 없으면 -1 을 반환 코드 (Python) import sys import bisect def input(): return sys.stdin.readline().rstrip() n, m = map(int, input(..

백준-2109 : 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 풀이 입력 받은 정보를 날짜 순으로 정렬을 한다. 정렬한 데이터를 꺼내면서 우선순위 큐에 넣으며 우선순위 큐의 크기가 날짜보다 클경우 가장 작은 비용의 값을 꺼낸다. 코드 (python) import sys import heapq def input(): return sys.stdin.readline().rstrip() n = int(i..

백준-15173 : 점프왕 쩰리 (Small) https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 풀이 0,0에서 시작해서 해당 이동할수 있는 값 만큼 이동을하여 우측과 , 아래쪽을 확인하면서 DFS를 실행항 주의사항 좌표의 값이 0인 값도 있기 때문에 해당 부분은 제외해줌 코드 (python) import sys read = sys.stdin.readline n = int(read()) graph = [list(map(int, read().split..