[softeer] 금고털이 (Python)

https://softeer.ai/practice/info.do?idx=1&eid=395 문제 루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가? 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다. 제약조건 1 ≤ N ≤ 106인 정수 1 ≤ W ≤ 104인 정수 1 ≤ Mi, Pi ≤ 104인 정수 입력형식 첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다...

• format_list_bulleted 코딩테스트 준비/Softeer
• · 2023. 6. 15.
• textsms

이진 탐색

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이진 탐색 알고리즘 ​ · 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 ​ · 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 · 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. ​ 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾아보자. ​ 먼저 시작점은 제일 왼쪽에 있는 0번째 인덱스, 끝점은 가장 오른쪽에 있는 9번째 인덱스 그리고 중간점은 가운데 4번째 인덱스로 설정한다. 만약 중간값이 2개가 있으면 소수점을 제거한 값이 ..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms

정렬 알고리즘 (2) [퀵 정렬, 계수 정렬]

https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 ​ 3. 퀵 정렬 · 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. · 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. · 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. · 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. ​ 맨 처음 피벗의 값은 '5'다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 그 뒤, 이 두 데..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms

정렬 알고리즘 (1) [선택 정렬, 삽입 정렬]

https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 정렬 알고리즘 · 정렬이란 데이터를 특정 기준에 따라 순서대로 나열하는 것 · 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. ​ ​ 1. 선택 정렬 알고리즘 · 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘 ​ 정렬 되지 않은 데이터 맨 처음 위와 같이 정렬 되어있지 않은 데이터가 존재한다고 가정해보자. ​ 처리 되지 않은 데이터 중 가장 작은 값인 '0'을 선택해 가장 앞에 있는 '7'과 교환한다. ​ 다시 처리되지 않은 데이터 중 가장 작은 값인 '..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms

다이나믹 프로그래밍

본 글은 나동빈 선생님의 이것이 코딩테스트다 with 파이썬을 기준으로 작성되었습니다. ​ 출처 : https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 ​ · 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. ​ · 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 탑-다운과 바텀-업으로 구성된다. ​ · 탑-다운 : 위에서 아래로 (하향식) 바텀-업 : 아래에서 위로 (상향식) ​ · 다이나믹 프로그래밍은 2가지 조건을 만족할 때 사용 가능하다. ​ ​ 1. 최적 ..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms