본문 바로가기
728x90

ALGORITHM142

[PG/Python] 숫자의 표현 📌 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📌 문제 접근 방법 n 이하의 자연수들 중에 연속으로 더해서 n이 되는 수를 찾는 문제 n 이하의 자연수 x부터 시작해서 k개의 수를 더해서 n이 된다고 가정하면 다음과 같은 식이 나온다. x + (x+1) + (x+2) + ... + (x+k-2) + (x+k-1) = n 이를 계산하면, k(2x+k-1)/2 = n 이를 x를 기준으로 치환하면 x = n/k - (k-1)/2 x는 자연.. 2022. 10. 3.
[Algorithm] Pregix Sum (누적합, 구간합) 누적합, 구간합 배열의 일부 구간에 대한 합을 빠르게 구할 수 있음 N개의 원소의 합을 구하는 경우 완전 탐색으로 구하면 O(N) 구간합으로 구하면 O(1) 1차원 배열 sum이라는 리스트를 만들어서 sum[i]에 arr[0] ~ arr[i-1] 의 합을 저장 0 부터 i 까지의 합을 구하고 싶은 경우 : sum[i+1] i 부터 j 까지의 합을 구하고 싶은 경우 : sum[j+1] - sum[i] 2차원 배열 sum이라는 리스트를 만들어서 sum[i][j]에 arr[0][0] ~ arr[i-1][j-1] 의 합을 저장 (0, 0) 부터 (i, j) 까지의 합을 구하고 싶은 경우 : sum[i+1][j+1] sum 리스트를 만드는 방법? # arr는 n*n 배열 # 1. 행단위로 더하고 열단위로 더하기 .. 2022. 9. 19.
[PG/Python] 메뉴 리뉴얼 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 📌 문제 접근 방법 orders를 문자열의 길이로 내림차순 정렬, course를 오름차순 정렬한다. (코스에 들어갈 메뉴의 개수보다 order의 길이가 작으면 필요없기 때문에 pop을 하기 위해 사전 처리) course를 순회하며 코스에 들어갈 메뉴 개수를 정하고 원하는 개수보다 적은 개수의 메뉴를 주문한 경우는 제외하기 위해 pop해준다. 각 주문에 대.. 2022. 6. 24.
[PG/Python] 광고 삽입 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/72414?language=python3 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 📌 문제 접근 방법 아이디어를 참고한 풀이 : https://dev-note-97.tistory.com/156 시간을 모두 초로 바꾸어서 Memoization을 사용한다. 로그의 시간을 all_time 리스트에 저장할 때, 반복문을 사용해서 start부.. 2022. 6. 24.
728x90

티스토리툴바