9. 1105 팔 9.1. 유형파악 그리디 그리디 유형은 정렬과 함께 출제될 확률이 높다. 문제 유형을 한 번에 파악하기 어려울 경우 그리디를 의심해볼 것 종종 DP, Graph 알고리즘과 함께 출제된다. 그리디는 반드시 최적의 해를 구할 수 있는 지 의심해봐야한다. 9.2. 해결과정 주어진 l, r 사이에서 8을 가장 적게 포함하는 횟수를 구하는 문제이다. 수의 범위가 20억이므로, 순차탐색으로 해결할 수 없다. 8의 최소 개수만 세면 된다는 것에 초점을 맞춰 풀어야한다. l과 r의 첫번째 자리수부터 비교하되 일치하면서 8이라면 개수를 카운트하고, 다르다면 stop한다. 만약 자리수의 값이 다르다면, (8이 아닌 다른값으로 설정해버리면 개수가 0이된다.) 바로 stop하는 이유는, 이미 앞 자리수가 다..

7. 1826 연료 채우기 7.1. 유형파악 Greedy 그리디는 정렬과 같이 나올 확률이 높다. 바로 문제 유형이 보이지 않는다면 그리디를 의심해 볼 것 DP, Graph 알고리즘과 함께 나오는 경우도 있다. 그리디 문제는 항상 최적의 해를 구할 수 있는지 의심해봐야 한다. 7.2. 해결과정 현재 연료로 도달할 수 있는 주유소를 추린다. 추린 장소 중 가장 멀리 떨어진 주유소로 방문해본다. 해당 주유소에서 주유 후 다시 1-2번을 거친다. 만약 방문할 수 있는 장소가 없다면 -1을 출력한다. 7.3. 소스코드 import heapq n = int(input()) heap = [] for _ in range(n): heapq.heappush(heap, list(map(int, input().split()..

5. 17609 회문 5.1. 유형파악 Greedy 그리디 유형은 정렬과 세트로 출제된다 바로 문제 유형을 파악하기 어렵다면 그리디를 의심해볼 것 그래도 파악이 어렵다면 DP, Graph 알고리즘을 고려할 것 📌 그리디로 해법을 찾을 때는 항상 정당한 해법인지 의심해봐야 한다. 5.2. 해결과정 문자를 최대 하나 삭제할 수 있으므로 그리디 유형임을 파악. 단, 모든 문자열을 검토할 경우 시간초과 발생. 따라서 유사 회문은 투 포인터 방식으로 구현. 투 포인터로 양 끝에서 같은지 탐색 후, 다를 경우 check_pseudo() 호출. check_pseudo는 왼쪽 삭제, 오른쪽 삭제 2번 호출 왼쪽, 오른쪽 호출된 값 중 하나라도 True라면 1. 아니라면 2 반환 5.3. 소스코드 # val == val..

3. 1946 신입사원 3.1. 문제유형 그리디, 정렬 3.2. 해결과정 그리디 문제지만 지원자가 10만명이므로 2중 for문으로 접근 시 10^10 연산 횟수가 필요하다. 따라서 O(n^2)이하의 복잡도로 문제를 해결해야 한다. 힌트는 서류나 면접점수 둘 중 하나로 정렬하면, 1명은 무조건 합격이라는 것을 알 수 있다. 이를 활용하여 서류로 정렬 후 합격자보다 면접점수가 높은 지원자를 카운트한다. 이전 합격자보다 면접점수가 높은 지원자가 나오면 면접 점수를 갱신한다. 3.3. 소스코드 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): n = int(input()) apply = [list(map(int,input().sp..

1. 1931 회의실 배정 1.1. 문제유형 그리디 1.2. 해결과정 해당 문제는 (종료시간, 시작시간)을 기준으로 정렬한 후 카운트해야한다. 회의를 가장 많이하려면, 빨리 끝나는 회의 먼저 시작한다. 끝나는 시간이 동일하다면, 시작 시간이 빠른 회의를 먼저 시작한다. 현재 종료된 회의시간

🔸 문제 접근 방식 가장 무거운 사람을 먼저 태운다. 가장 가벼운 사람부터 보트에 태워나간다. 보트 무게가 limit를 초과하면, 가벼운 사람을 한 명 내리고 1번으로 돌아간다. ❗ 주의 사항 처음에 리스트의 원소가 남아있을 때까지 While문을 반복하였다. 하지만 리스트 삭제 연산 수행 시 시간초과가 발생했다. 리스트 원소 최대값이 50,000임에도 비효율적인 알고리즘으로 판명되었다. 따라서 리스트를 삭제하는 대신, left, index 포인터를 두고 indexing하였다. 💧 Source Code def solution(people, limit): ''' https://programmers.co.kr/learn/courses/30/lessons/42885 Notes: 1. 가장 무거운 사람을 먼저 태..

🔸 문제 접근 방식 stack에 값이 없거나, 더 작은 경우 넣는다. top에 위치한 값이 더 작으면 해당 값을 배내고, k를 감소시킨다. k가 0이되면 남은 값들을 스택에 넣는다. 스택이 꽉 찼는데, k가 남아있다면 맨 위에서 k개를 꺼낸다. 💧 Source Code def solution(number, k): ''' Notes: 1. stack에 값이 없거나, 더 작은 경우 넣는다. 2. top에 위치한 값이 더 작으면 해당 값을 빼내고, k를 감소시킨다. 3. k가 0이되면 남은 값들을 스택에 넣는다. 4. 스택이 꽉 찼는데, k가 남아있다면 맨 위에서 k개를 꺼낸다. Args: number (str) : 주어진 숫자 (문자열로 주어짐) k (int) : 삭제할 숫자 개수 Returns: answe..

🔸 문제접근방식 'A' 문자가 아닌 곳으로 이동하기까지 왼쪽, 오른쪽 이동 횟수를 계산 후 최소값을 더한다. 왼쪽 or 오른쪽 이동 후, 문자 완성을 위해 'A'에서부터 문자까지, 'Z'에서부터 문자까지 횟수를 계산 후 최솟값을 더한다. 모든 위치를 다 방문하여 문자열을 완성 시 종료한다. 파이썬에서 리스트는 음수로도 indexing이 가능하다. 가운데 중간 지점에서부터 계산하는 것이 아닌 주어진 조건 'A'부터 혹은 뒤에서 'Z'부터 계산할 것 💧 Source Code def solution(name): ''' Programmers 조이스틱 문제풀이 - Greedy Notes: 1. 'A' 문자가 아닌 곳으로 이동하기까지 왼쪽, 오른쪽 이동 횟수를 계산 후 최소값을 더한다. 2. 왼쪽 or 오른쪽 이동..

🔸 문제 접근 방식 체육복 여벌은 자신 기준 앞, 뒤로만 빌려줄 수 있다는 건 유의 체육복 여벌이 있는데 도난 당한 경우를 먼저 고려할 것. 예외 처리 발생 💧 Source code def solution(n, lost, reserve): ''' 프로그래머스-체육복 문제 풀이 (Greedy) Notes: 1. 체육복 여벌은 자신 기준 앞, 뒤로만 빌려줄 수 있다는 것 주의 2. 체육복 여벌이 있는데 도난 당한 경우를 먼저 고려할 것. 예외 처리 발생 Args: n (int) : 학생 수 lost (list) : 체육복을 잃어버린 학생 번호를 담은 리스트 reserve (list) : 체육복 여벌을 가져온 학생 번호를 담은 리스트 Returns: answer (int) : 체육 수업에..

🔸 만들 수 없는 금액 동전 n개가 주어졌을 때, 해당 동전들로 만들 수 없는 금액을 구하여라. 동전은 최대 1000개, 각 동전의 크기는 최대 1,000,000원이다. ex) 1,2,3, 7원 동전이 주어졌을 때, 1원 : 1 2원 : 1 3원 : 3 4원 : 1+3 5원 : 2+3 6원 : 1+2+3 7원 : 7 8원 : 1+7 9원 : 2+7 10원 : 3+7 11원 : 1+3+7 12원 : 2+3+7 13원 : 1+2+3+7 14원 : X 📌 초기 접근 방법 처음에 생각한 접근 방식은 어려웠다. 동전의 모든 조합을 구한다. 조합 별 최종 합을 구한다. 최종 합을 set에 담는다. 여기서 문제는 모든 조합을 구할 때 너무 많은 비용이 든다. Combination 연산 시에는 팩토리얼 단위로 연산하기..