프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 그리디 문제다.그리디는 정말... 풀이가 딱 떠오르지 않으면 푸는데 한참 걸리거나 못 푸는 것 같다.그래서 많이 풀어보는 게 중요하다는 생각이 든다. 풀이를 계속 생각해봤지만, 계속 아니더라..결국 구글링을 참고해서 풀었다. def solution(number, k): answer = '' stack = [] for num in number: while k > 0 and stack and stack[-1] 0: stack = stack[:-k] ..
그리디
https://www.acmicpc.net/problem/1461 그리디 문제다.처음 문제를 보고, 음수와 양수를 나눠서 풀어야겠다는 생각이 들었다.그리고, 음수, 양수 중 절댓값이 큰 수에 마지막으로 도착하도록 해야겠다는 생각도 해냈다.왜냐하면 갔다가 다시 책을 가지기 위해 원점으로 돌아와야 하는데, 가장 큰 값에 도착했다가 다시 돌아온다면절대 최솟값이 될 수 없기 때문이다. 이런 아이디어는 어떻게든 생각해내니 거의 1시간이 지나있었다.구현해보다가 잘 안되어서 결국 풀이를 약간 참고해서 풀었다. # 1461번: 도서관# 음수와 양수를 나눠서 계산한다.import sysinput = sys.stdin.readlinen, m = map(int, input().split())arr = list(map(int..
https://www.acmicpc.net/problem/1689 그리디 문제다.여러 선분의 시작점과 끝점이 주어졌을 때, 겹치는 선분의 최대 개수를 출력하는 문제다. 처음에는 각 선분의 좌표가 .5를 지나가는 경우 1을 더해주는 방식으로 구해보려고 했다.예를 들어 선분의 시작점, 끝점 좌표가 (3, 6)인 경우에는 3.5, 4.5, 5.5를 지나가는 것이다.그러므로 리스트를 선언해 전체 좌표에 대해 지나가는 선분의 개수를 저장하려고 해봤는데,생각해보니 선분의 개수가 100만개이고, 선분의 좌표의 절댓값이 10억 이하이므로 무조건 시간초과가 나기 때문에 구현하지 않았다. 그 다음 아이디어로, 입력받은 좌표들을 정렬한 후에, 조건을 넣어줘서 선분 개수의 최댓값을 갱신해주면 되지 않을까?라는 생각이 들어서 ..
https://www.acmicpc.net/problem/1946 이번에도 그리디 문제다.바로 전 문제인 회의실 배정 문제와 거의 비슷한 문제라고 볼 수 있다. 그리고 문제 설명이 살짝 헷갈렸던 문제기도 하다.지원자의 (서류심사 성적, 면접시험 성적)이 주어지는데, 둘 중 적어도 하나가 다른 지원자보다 떨어지지 않는 사람만이 선발 될 수 있다.즉, A라는 인원의 (서류심사 성적, 면접시험 성적)이 임의의 인원 B의 (서류심사 성적, 면접시험 성적)보다 둘 다 떨어지는 경우가 하나라도 있다면, A는 뽑힐 수가 없는 것이다. 결국 정렬이 필요하다.문제를 풀다 보니 그리디는 정렬과 항상 붙어 있는 느낌이다. 서류심사 성적 기준으로 오름차순 정렬한다.그리고 면접시험 성적을 반복문을 돌면서 비교하면 된다. 만약..
https://www.acmicpc.net/problem/1931 그리디 문제다. 그리디 문제는 주로 정렬과 관련되어 있다.이 문제도 N이 최대 10만이고, 시간 제한은 2초이므로 O(NlogN)까지 가능하다. 회의를 최대한 많이 넣어야 한다.그러므로, 회의의 종료시간을 기준으로 오름차순 정렬한다. 그리고 여기서 주의할 점은, 두번째 정렬 기준으로 회의의 시작시간 기준으로 오름차순 정렬해야한다는 것이다.왜냐하면 이런 경우 때문이다. 예를 들어6 1013 1312 1311 13이렇게 회의 시간이 있다고 해보자.만약, 회의의 종료시간만을 기준으로 오름차순 정렬했다면, 반복문을 돌며 들어가는 회의는(6, 10) - (13, 13)이 될 것이다.하지만, 이렇게 회의를 넣으면, 회의의 최대개수가 나오지 않는다.(..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전형적인 그리디 문제. 구명보트 리스트를 정렬한 후, left, right를 통해 리스트를 순회하면서 필요한 구명보트 개수의 최솟값을 구해주면 된다. 내 풀이 코드 def solution(people, limit): people.sort() # 오름차순 정렬 left = 0 right = len(people) - 1 answer = 0 # 구명보트 최솟값 while left limit: right -= 1 # 오른쪽 사람 혼자 탄다. answer += 1 # 두 명 무게의 합이 limit보다 작거나 같은 경우..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그리디로 풀면 되는 문제다. 체육복이 있어야 체육 수업을 들을 수 있는데, 체육복이 있는 학생 수의 최댓값을 출력하는 문제. 체육복이 없는 i번째 학생은 i-1번이나, i+1번 학생에게만 체육복을 받을 수 있다. 여기서 만약, i번째 학생이 i-1번째 학생에게 빌리든, i+1번째 학생에게 빌리든 체육복이 있는 학생 수는 변하지 않는다. -> 그리디 그래서 나는 만약 i번째 학생이 체육복이 없다면, i-1번째 학생에게 먼저 빌리고, 안되면 i+1번째 학생에게 빌리게 구현했다. 중간에 테스트 케이스 2개 정도가 ..
2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 그리디 또는 DP로 풀 수 있는 문제다. 1. 그리디 n = int(input()) total = 0 while True: if n % 5 == 0: total += n // 5 print(total) break elif n % 5 != 0: total += 1 n -= 3 if n < 0: print(-1) break 2. DP n = int(input()) dp = [5001] * 5001 dp[3] = 1 dp[5] = 1 for i in range(6, n+1): ..
주어진 볼링공의 개수(N)이 1,000 이하고, 시간 제한은 1초였다. 그러므로 O(N^2)의 시간복잡도로 충분히 풀 수 있다. 그래서 처음에는 단순하게 1번~N번의 볼링공까지 for문을 돌면서 자기 다음 번호 ~ N번까지의 공들을 확인해서 자기 자신과 같은 값 빼고 +1을 해주면 답이 나온다고 생각했다. 좀 더 생각해보니 더 간단한 로직이 있었다. 각 볼링공 무게를 인덱스로 하는 리스트를 만들어서 볼링공 무게마다 볼링공이 몇개 있는지 저장한다. 그 후 특정 볼링공 무게에 해당하는 볼링공의 개수가 0이 아닌 경우, 특정 볼링공 무게의 볼링공 개수 개수 * (전체 볼링공 개수 - 특정 볼링공 무게의 볼링공 개수) 를 무게마다 구해서 더해준 다음에 2로 나눠주면 답이 나온다. 내 풀이 # Q_05_볼링공 고..
동빈이는 N개의 동전을 가지고 있다. 이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라. 예를 들어 N=5이고, 각 동전이 각각 3, 2, 1, 1, 9원이라고 하면 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 문제의 시간제한이 1초이고, 동전의 개수가 1000개 이하이므로 O(N^2)도 되겠구나 라는 생각을 했다. 그리고 동전의 단위도 1,000,000이하의 자연수라서 동전의 단위로 반복문을 돈다면 O(NlogN)도 가능하겠다는 생각을 했다. 처음에는 동전들을 오름차순 정렬해서 1부터 가장 큰 동전의 값까지 반복문을 돌려서 1 ~ 동전의 최댓값까지 동전을 만들 수 있는 경우를 확인해보려고 했다. 하지만 그럴 경우 동전의 단위가 서로 나..
