국밥 개발자

백준-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..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀의 진입 차수를 담아줄 리스트를 초기화한다. 진출 정보를 담아줄 리스트를 초기화한다. 진입 차수가 0인 것들을 큐에 담아준다. 큐에 값을 꺼내면서 결과 리스트에 큐의 값을 넣어준다. 해당 큐의 값에 진출 정보를 담는 리스트에서 진출 정보를 꺼내면서 해당 진출 정보와 관련된 진입 차수를 줄여준다. 진입 차수가 0이라면 큐에 담아준다. 코드 (Python)..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 진입 차수 : 특정한 노드로 들어오는 간선의 개수 진출 차수 : 특정한 노드에서 나가는 간선의 개수 풀의 진입 차수를 담아줄 리스트를 초기화한다. 진출 정보를 담아줄 리스트를 초기화한다. 진입 차수가 0인 것들을 큐에 담아준다. 큐에 값을 꺼내면서 해당 큐의 값에 진출 정보를 담는 리스트에서 진출 정보를 꺼내면서 해당 진출 정보와 관련된 진입 차수를 줄여준다. 큐의 값 이후에 진행되야 하므로 해당값의 결과보다 1보다 작다면..

https://www.acmicpc.net/problem/11558 11558번: The Game of Death 첫 줄에는 테스트 케이스의 숫자 T가 주어지며, 이어서 T번에 걸쳐 테스트 케이스들이 주어진다. 매 테스트 케이스의 첫 줄에는 플레이어의 숫자 N(1 ≤ N ≤ 10,000)이 주어진다. 이어서 N줄에 걸쳐 www.acmicpc.net 풀의 각 플레이어가 가리키는 정보를 담을 테이블에 각플레이어가 가리키는 정보를 담아준다. 각 플레이어의 부모 테이블을 자기 자신으로 초기화 한다. 1번 플레이어부터 가리키는 플레이어를 체크한다. 마지막 플레이어를 발견하기 전에 사이클이 발생하면 사이클이 발생함으로 0을 리턴한다. 마지막 플레이어를 발견하면 이동하 횟수를 리턴한다. 코드 (Python) impo..

백준-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..

백준-14767 : Flow Shop https://www.acmicpc.net/problem/14767 14767번: Flow Shop There is only one test case in each file. It begins with a single line containing N and M (1 ≤ N, M ≤ 1000), the number of swathers and stages (respectively). Following this are N lines, each with M integers. The j’th integer of the i’th line is Pi www.acmicpc.net 문제 n개의 스웨터 주문과, m개의 공정을 과정을 입력 받는다. 각 공정마다 기계는 한개씩 존재하고 ..

백준-2206 : 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 풀의 시작 점 부터 BFS 를 진행한다. BFS 를 진행하며 벽일 경우 벽을 아직 부수지 않았으면 벽을 부수고 진행한다. 벽을 부순 유물를 3차원으로 관리 코드 (Python) import sys from collections import deque read = sys.stdin.readline n, m = map(int, read().split(" ")) matrix = [list(map(int, read().rstrip())) for _ in range(n)] visited = [[[0] * 2 for _ in range(m)] for _ in range(n)] # 상 하 좌 우 dx = [0, 0..

백준-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_..