https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 점수가 큰 과제를 많이 먹어야하는데, 마감 기간을 잘 고려해서 스켸쥴을 짜면 된다. 우선 점수가 큰 순으로 정렬한 뒤, 이제 스켸쥴 표를 하나씩 채워나가면 된다. 해당 위치에 이미 값이 있으면 (= 그날 할 과제, 즉 계획이 있으면) 앞으로 날짜를 당기면서 빈 곳에 계획을 채워넣는다. 결국, 1 ~ m일차까지의 스켸쥴 표를 작성한다고 생각하면 쉽다! (여기서 m은 과제 마감일 중 제일 큰 값, 코드에서 cnt값) import sys sys...
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 중복조합 또는 dp로 해결가능한 문제인데, dp로 풀어보았다. 우선, k가 1일 경우엔 n으로 어떤 수가 와도 경우의 수는 1이다. 그러나 n이 1일 경우, 경우의 수는 k값을 따라간다. dp 테이블 k = 1 k = 2 k = 3 n = 1 1 2 3 n = 2 1 3 n = 3 1 n = 4 1 n = 5 1 이제 위 dp 테이블을 채워나가면 된다. n=2이고 k=2일 때 가능한 경우는 0+2, 2+0, 1+1 총 3가지 이다. 이는 (2,1)의 경우인 2와 (1,2)의 경우인 0+1, 1+0를 합한 것이라고 볼 수 있..
https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그리디 문제이다. 예제 풀이를 따라 코드를 작성하면, 아마 시간초과가 발생할 것이다. n이 최대 100,000까지므로 n^2의 시간복잡도로는 문제를 풀 수 없다. 우선, 한번에 최대한 멀리가서 멀리 있는 곳들의 작업을 먼저 끝내야지 이동횟수를 최소한으로 만들 수 있으므로 입력받은 배열들을 역순으로 뒤집어준다. 가장 먼 곳부터 탐색을 시작하는데, 배달해야 하거나 픽업해와야 할 것들이 하나라도 있으..
https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 꼼꼼히 읽고 그대로 구현만 하면 되는 문제이다. 입력의 형태가 정해져있어 슬라이싱을 이용한 하드 코딩 형태로 문제를 풀어보았다. 아니면 연,월,일을 모두 day로 변환해서 푸는 방법도 있다. 어느 쪽을 선택하던지 연/월/일을 다루는 문제는 본인이 헷갈리지 않는 방법이 최고인 것 같다! def solution(today, terms, privacies): answer = [] nyear =..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소신장트리(MST)를 만드는 알고리즘을 약간 응용한 문제이다. 우선 주어진 입력을 바탕으로 MST를 생성한다.(프림 또는 크루스칼 이용) 문제에서 요구하는 조건을 만족하기 위해서는, 생성된 최소신장트리에서 간선의 비용이 가장 큰 것을 하나 찾은 뒤 그곳을 기점으로 잘라주면(=간선을 제거하면) 문제의 조건을 충족시킬 수 있다. #include using nam..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2467번 용액, 2470번 두 용액, 2473번 세 용액으로 이어지는 시리즈 문제이다. 전체적인 맥락은 비슷하므로 한 문제만 포스팅하겠다. 투포인터, 이분탐색의 활용문제이다. 총 3개의 포인터가 필요한데 약간의 테크닉이 필요하다. 우선 개략적인 방법은 흔한 투포인터를 이용한 이분탐색과 동일하다. 여기에 하나의 포인터를 추가하는데, 포인터 하나를 고정해서 이용한다! 맨 앞을 ..
