https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그리디 문제이다 사실 문제 자체는 2중 for문을 쓰면 금방 풀리긴 하는데, 그렇게 호락호락 할리가 없지 ㅎㅎ 조건이 백만까지 주어져서, 2중 for문을 쓰면 시간초과가 뜰 것이다. 이 문제는 주어진 숫자들을 정렬해서 푸는 문제가 아니므로, 앞에서부터 작은 수들을 지워나가야 한다. 키포인트는 stack을 이용한 풀이이다. 숫자들을 스택에 넣다가, 만약 스택의 top보다 큰 수가 나오면 스택의 to..
https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제의 포인트는 2가지이다. 1. A에서 해당 알파벳으로 가는 최소 횟수 구하기 2. 현재 위치에서 왼쪽과 오른쪽 어디로 갈 것 인지 정하기 1번은 사실 정해져있다 아스키코드를 이용해 풀이하면, 중간 인덱스를 기준으로 A에서 출발하는 것이 빠른지 아니면 Z로 이동해서 거꾸로 가는 것이 빠른지 알 수 있기 때문이다. 그렇다면 중요한 것은 2번인데 어떻게 풀지 생각해보면, 가장 중요한 포인트는 "..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 점수가 큰 과제를 많이 먹어야하는데, 마감 기간을 잘 고려해서 스켸쥴을 짜면 된다. 우선 점수가 큰 순으로 정렬한 뒤, 이제 스켸쥴 표를 하나씩 채워나가면 된다. 해당 위치에 이미 값이 있으면 (= 그날 할 과제, 즉 계획이 있으면) 앞으로 날짜를 당기면서 빈 곳에 계획을 채워넣는다. 결국, 1 ~ m일차까지의 스켸쥴 표를 작성한다고 생각하면 쉽다! (여기서 m은 과제 마감일 중 제일 큰 값, 코드에서 cnt값) import sys sys...
https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 티어에 비해 쉽게 풀렸던 문제이다. 이 문제의 핵심 알고리즘은 "갯수 당 가격"이 가장 큰 3원을 사용하는 연산의 횟수를 최소화하고, 그 경우 중에서도 5원을 사용하는 횟수를 최소화하는 것과 arr[i+1]번째 값과 arr[i+2]번째 값의 비교이다! -> 만약 [1,2,1,1] 과 같이 주어졌다고 하자. 당연히 3개씩 묶어서 사는게 이득이므로 1번째와 2번째, 3번째에 있는 라..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 문제가 한번에 이해가 안될수도 있으니,, 꼼꼼히 읽어보셔야 한다. 우선, 이 문제는 누가봐도 정렬과 그리디 알고리즘이다. 이 문제를 풀 때 3가지 key point가 있다고 생각한다. 1. 음수부분과 양수부분을 구별 (음수의 개수 세기) 2. m개의 책을 들고 다닐 수 있으므로 m칸씩 이동 3. 맨 끝 값(제일 작은 음수, 제일 큰 양수) 중 절댓값이 더 큰 것을 마지막에 방문 (= 되돌아올 필요 없으..
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 이 문제는 문제를 읽기 조차 조금 힘들다.. 간단히 설명부터 하자면, 1 3 6 6 7 9가 있을 때 기지국이 2개라고 주어진다면 기지국 1이 [1~3]을 수신하고 기지국2가 [6~9]를 수신할 때 수신가능영역이 최소가 된다! 이제 이 문제를 푸는 방법에 대해 알아보자. 우선 입력으로 주어진 값을 정렬해주자. 1 6 9 3 6 7 이라는 예제가 주어졌다고 하면 이를 정..
