알고리즘
-
[Python] 에어컨알고리즘/프로그래머스 2023. 7. 28. 09:28
https://school.programmers.co.kr/learn/courses/30/lessons/214289 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 코드 import math def solution(temperature, t1, t2, a, b, onboard): # 0으로 정규화 diff = temperature - t2 if temperature > t2 else t1 - temperature # 시간0에 대해 초기 비용으로 초기화 result = [[ 1000000 for i in range(diff+1) ]+[0]] last_pa..
-
[Python] 상담원 인원알고리즘/프로그래머스 2023. 7. 23. 12:52
https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이 코드] from collections import Counter, defaultdict from itertools import combinations_with_replacement def solution(k, n, reqs): # 큰 수 answer = 999999999 # 중복조합 comb = combinations_with_replacement([i for i in range(k)],..
-
[2022 KAKAO BLIND RECRUITMENT] 주차 요금 계산알고리즘/프로그래머스 2022. 8. 24. 19:44
https://school.programmers.co.kr/learn/courses/30/lessons/92341?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 - 들어오고 나가는 차량에 대해서, 요금을 계산하려고 한다. 주어지는 데이터 - fees에는 기본시간(분), 기본요금, 단위시간(분), 단위요금 이 담겨있다. - records는 시간, 차량번호, 기록(IN, OUT) 이 담겨있다. 풀이 1. 각 차량의 번호를 key로 가지고, 입차했던 시간을 value로 가지는 딕셔너리를 만든다. 모든 입-출차 시간을 각..
-
[Backtracking] Subset Sum알고리즘/Algorithm Theory 2022. 6. 25. 19:41
Subset Sum(부분 합 문제) : 양의 정수들의 배열이 들어 올때, 배열의 부분합으로 일정 수를 만들 수 있으면 TRUE를, 만들 수 없으면 FALSE를 돌려준다. Ex) X = {8, 6, 7, 5, 3, 10, 9} T = 15이면, {8,7}, {5,10}, {6,9}, {7,5,3} > TRUE - Base Cases T = 0 이면, 선택하지않으면 항상 TRUE 이다. T < 0 이면, 항상 FALSE이다. - General Case(점화식) 총합이 T인 부분집합에 대해, 해당 부분집합은 X의 원소 x에 대해 x를 포함하거나, 포함하지않거나의 두가지로 나뉜다. 1. x를 포함할 경우, T-x 인 X-{x}의 부분집합이 존재한다. 2. x를 포함하지 않을 경우, T 인 X-{x}의 부분집합이..
-
[D&C] Binary Search알고리즘/Algorithm Theory 2022. 6. 25. 18:41
이진 탐색 정렬된 A[0...n-1]의 배열에 대해 k값을 찾을 때, a의 중간값(median)을 k 와 비교하여 같으면 종료. 이진탐색은 실은 분할정복기법이다. 중간값을 k와 비교한 뒤에 배열의 절반에 대해서만 탐색을 계속한다. 즉 문제의 크기가 n/2인 동일한 작은 문제를 해결하다보면, 문제를 해결 할 수 있다. 이진탐색 # A가 정렬된 배열일때 A[a...b]에서 k값을 탐색 int binary_search(A[a...b], k, a, b): if a>b: return -1 mid = (a+b)/2 if A[mid] > k: return binary_search(A, k, a, mid-1) elif A[mid] < k: return binary_search(A, k, mid+1, b) else re..
-
[2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기알고리즘/프로그래머스 2022. 6. 24. 06:48
https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 문제자체는 간단하다. 1. 진수변환 2. 조건에 맞는 소수 판별 # 어찌저찌 길이 줄여봄... import math def solution(n, k): num = '' while n > 0: n, mod = divmod(n, k) #몫과 나머지를 돌려줌 num += str(mod) numbers = [int(i..
-
[2022 KAKAO BLIND RECRUITMENT] 신고 결과 받기알고리즘/프로그래머스 2022. 6. 24. 01:30
https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 풀긴 풀었는데, 효율성이 좋을지는 모르겠다. 유저 : (신고한 유저목록) 과 같은 자료구조를 만들고 , 게시판 이용이 정지되는 유저목록을 구해서 교집합 연산 후에 개수를 세서 발송해야하는 메일 개수를 구하면된다. from collections import defaultdict def solution(id_list, report, k): result, ba..
-
[DP] 정수 삼각형알고리즘/프로그래머스 2022. 6. 23. 22:27
https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 예전에는 dp문제가 어려웠는데, 그렇게 어렵지도 않은 것 같다. 효율성 테스트도 한번에 통과했다. 위와 같이 삼각형의 일부분에 대해, 1을 지나가는 경우는, 3을 지나고 1을 지나는 경우와 8을 지나고 1을 지나는 경우 두가지밖에 없다. 즉 삼각형이 양 끝의 경우에 대해 if문으로 처리해주고, 그 가운데들에 대해서는 두 가지경우중 더 큰 경우를 선택하면서 삼각형테이블을 채우다보면, 맨 마지막 행중 최대값이 ..