보리남편 김 주부

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

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해 주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers return [6, 10,..

최대공약수(Greatest Common Divisor) : 주어지는 두 정수의 약수 중에서 가장 큰 공통약수 ex) 280 과 30 의 GCD는 10이다. . 280의 약수 : 1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280 . 30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30 - 소인수분해를 통해 GCD를 구할 수 있다. 2 | 280 30 5 | 140 15 --------------- 28 3 최대공약수 = 2 * 5 = 10 GCD 관련 법칙 - GCD(u,v) = GCD(u-v, v) if u > v - GCD(u,v) = GCD(v, u) - GCD(u,0) = u 위 법칙으로 아래와 같은 알고리즘을 구성할 수 있다.(유클리드 알고..

알고리즘이란 무엇인가? 알고리즘(Algorithm)의 정의 - 주어진 문제를 해결하기 위해 잘 정의된 동작들의 유한 집합 자료구조 - 알고리즘의 객체 - 구조화되고 조직화된 자료의 저장/추출/관리 방법 - 추상데이터타입 (Abstracted Data Type) - 배열, 스택, 큐, 트리.... 알고리즘 선택 시 주의사항 - 하나의 문제에 대해 여러 알고리즘이 존재 - 절대적인 최상의 알고리즘은 없다. - 주어진 문제와 환경을 먼저 숙지하라. - 속도와 자원(resource)의 상관관계 - 단순한 알고리즘이 좋다. . 지나친 속도결벽증은 금물 . 알고리즘의 사용빈도에 따른 선택 경험적 분석과 수학적 분석 - 분석은 알고리즘을 정확히 선택하기 위한 방법 - 시간 소요량 vs 공간 소요량 1) 경험적 분석(..

https://programmers.co.kr/learn/courses/30/lessons/12942 코딩테스트 연습 - 최적의 행렬 곱셈 크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = programmers.co.kr 난이도 : Level 4 잡동사니 : 최적의 행렬 곱셈 관련 많은 풀이들이 있는데 굳이 이 글을 작성하게 된 이유는 설명이 잘되어 있음에도 난 도대체 이해가 안돼서 멘붕이 왔다. 약간 오기도 생겨서 풀릴 때까지 풀어보잔 식으로 들이 파기 시작했다. 연쇄 행렬 최소곱셈 알고리즘에 대한 설명이 잘되어 ..

어떤 목적을 달성하기 위한 과정들에 다양한 알고리즘이 존재하고 우리는 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. 시간복잡도 - 알고리즘의 성능을 설명(연산을 수치화) 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존하며 각 알고리즘의 속도의 평가는 중요하지 않은 상수와 계수들을 제거하여 실행시간에서 중요한 성장률(입력값의 크기에 따른 함수의 증가량) - 점금적 표기법(Asymptotic notation) - 을 측정하여 판단할 수 있다. 이때 최상, 평균으로 측정 시 평가하기가 까다롭기에 최악일 경우를 판단하여 평균과 가까운 성능으로 예측할 수 있다.[빅오 표기법 (Big-O Notation)] 예) N개의 수열을 정렬하는 어떤 프로그램, 즉 이 숫자들을 오름차순으로 배치하는..

일전에 고향으로 내려가 대학교 때 수업 들었던 자료구조 책을 발견하였다. 요즘처럼 자료구조와 PS(problem solving)가 개발자 간에 화제가 된 건, 업체들이 입사 시 코딩 능력을 확인하기 위해 알고리즘 테스트를 채택하기 시작하면서부터 이다. 이직 시 필수 능력은 아니지만 이력서 작성 능력들이 나날이 증가하다 보니 작성된 경력기술서 및 프로젝트 경험이 참여는 했으나 기여도가 어느 정도인지 알 수가 없기에 구분까지는 아니더라도 최소한의 허들이 되고 있다. 나 같은 경우 (늙은 개발자를 뽑아주는 곳도 없겠지만) 이직을 하려는 것이 아니라 아래 2021년 회고를 하면서 개발자로서 기술적 성장을 하지 못했다는 생각에 https://jabdon4ny.tistory.com/10 2021년 회고 2021년 ..