본문 바로가기
728x90

전체 글424

프로그래머스 - 과일 장수 문제 설명과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.한 상자에 사과를 m개씩 담아 포장합니다.상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻.. 2024. 5. 7.
Algorithm design - Matrix-chain Multiplication 연쇄 행렬곱셈i × j행렬과 j × k 행렬을 곱하기 위해서는 일반적으로 i × j × k 번 만큼의 기본적인 곱셈이 필요하다. 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다.예를들어 M1, M2, M3, M4이 각각 10x100, 100x5, 5x50, 50x20이라고 할때 아래와 같이 다양한 결과가 나올 수 있다. (1) M1x(M2x(M3xM4)) : 5x50x20+100x5x20+10x100x20 = 35,000(2) M1x((M2xM3)xM4) : 100x5x50+100x50x20+10x100x20 = 145,000(3) (M1xM2)x(M3xM4) : 10x100x5+5x50x20+10x5x20 = 11,000(4) ((M1x.. 2024. 5. 7.
프로그래머스 - 이웃한 칸 문제문제 설명  각 칸마다 색이 칠해진 2차원 격자 보드판이 있습니다. 그중 한 칸을 골랐을 때, 위, 아래, 왼쪽, 오른쪽 칸 중 같은 색깔로 칠해진 칸의 개수를 구하려고 합니다. 보드의 각 칸에 칠해진 색깔 이름이 담긴 이차원 문자열 리스트 board와 고른 칸의 위치를 나타내는 두 정수 h, w가 주어질 때 board[h][w]와 이웃한 칸들 중 같은 색으로 칠해져 있는 칸의 개수를 return 하도록 solution 함수를 완성해 주세요. 이웃한 칸들 중 몇 개의 칸이 같은 색으로 색칠되어 있는지 확인하는 과정은 다음과 같습니다. 제한사항  1 ≤ board의 길이 ≤ 7 board의 길이와 board[n]의 길이는 동일합니다.  0 ≤ h, w 1 ≤ board[h][w]의 길이 ≤ 10 boa.. 2024. 5. 5.
프로그래머스 - 추억 점수 문제사진들을 보며 추억에 젖어 있던 루는 사진별로 추억 점수를 매길려고 합니다. 사진 속에 나오는 인물의 그리움 점수를 모두 합산한 값이 해당 사진의 추억 점수가 됩니다. 예를 들어 사진 속 인물의 이름이 ["may", "kein", "kain"]이고 각 인물의 그리움 점수가 [5점, 10점, 1점]일 때 해당 사진의 추억 점수는 16(5 + 10 + 1)점이 됩니다. 다른 사진 속 인물의 이름이 ["kali", "mari", "don", "tony"]이고 ["kali", "mari", "don"]의 그리움 점수가 각각 [11점, 1점, 55점]]이고, "tony"는 그리움 점수가 없을 때, 이 사진의 추억 점수는 3명의 그리움 점수를 합한 67(11 + 1 + 55)점입니다. 그리워하는 사람의 이름을 .. 2024. 5. 4.
Regularization / Dimensional Reduction and Expansion Regularization위와 같은 경우에 weight W는 유일하게 결정될 수 없다.Hinge loss의 특징을 통해서 2W 또한 Loss를 0으로 만들 것이라고 예상할 수 있다.이 케이스에서 weight를 두배로 만들어도 아래와 같이 Loss는 계속 0임을 확인할 수 있다.Regularization의 기본 원리는 이왕이면 더 단순한 모델이 좋다는 것이다. 아래 케이스를 보면 f1이 f2보다 training set에 보다 적합하지만 너무 복잡한 것을 볼 수 있다. 이렇게 과적합이 되어있으면 다른 데이터가 들어왔을때 좋은 성능을 내기 어렵다.다른 데이터가 들어오자 더 단순한 f2가 더 잘 표현하고 있는 것을 볼 수 있다.많이 알려진 regularization 기법은 아래와 같다.L1 regularizat.. 2024. 5. 4.
Computational Graph / Backpropagation Gradient위와 같은 SVM Loss function에 대해서 어떤 식으로 gradient를 연산할지 생각해보자.당연히 직접 계산을 하나씩 해나갈 수 있다.그러나 당연하게도 직접 하나하나 계산하는 것은 어마어마한 양의 행렬 연산으로 인해 낭비가 많다. 또한 만약 Loss function을 바꾸고 싶어지면 연산을 처음부터 다시해야한다. 마지막으로 복잡한 모델에서는 더더욱 문제가 많을 것이다. 따라서 Computational graphs와 Backpropagation을 이용한다. 아래는 Computational graphs의 표현법이다.역전파의 간단한 예시를 살펴보자.우리가 알고있는 미분 값과 알고 싶은 미분 값은 아래와 같다.이를 chain rule을 이용하여 역으로 진행시켜 구할 수 있다.위 과정을 .. 2024. 5. 3.
프로그래머스 - 소수 만들기 문제문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 1. nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. 2. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 입출력 예       nums      result [1,2,3,4]       1 [1,2,7,6,4]     4  입출력 예 #1[1,2,4]를 이용해서 7을 만들 수 있습니다. 입출력 예 #2[1,2,4]를 이용해서 7을 만들 .. 2024. 5. 2.
Algorithm design - DP / Levenshtein Distance Dynamic ProgrammingDynamic Programming은 동적 계획법이라는 뜻이지만 실제로 그렇게 동적이지는 않다. 오히려 기록해둔 과거 기록을 저장해두고 꺼내서 이용한다는 점에서 Tabular Method라는 이름이 어울린다.Divide-And-Conquer는 top-down approach로 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. 반면Dynamic programming은 bottom-up approach로 큰 문제를 작은 문제로 나눈 다는 점은 Divide-And-Conquer와 동일하나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 것이 아니고 그 저장된 결과를 이용한다는 점이 다르다. 해답을 구축하.. 2024. 5. 2.
Digital Image Processing - Color Image Processing Backgrounds of Color색의 3속성은 흔히 색상(Hue), 명도(Brightness,value), 채도(Purity,saturation,chroma)로 불린다.Primary color(원색)은 서로 혼합되어 다른 컬러를 생성하는 기본 색상으로 일반적으로 R,G,B의 3색을 이용한다. 100% 모든 color를 생성하지는 못하지만 practically 충분하다.Color gamut은 Primary color의 조합으로 만들어낼 수 있는 모든 컬러를 말한다.CIE XYZ Color ModelCIE(CommissionInternationaledeI'Eclairage,International Commission on Illumination)에서 제정한 모델로 CIE primary color를 정했다.. 2024. 5. 1.
알고리즘 설계 실습 - Fibo_counter 문제피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 아래 소스 코드는 N번째 피보나치 수를 구하는 재귀함수이다.int fibonacci(int n) { if (n == 0) { print("0"); return 0; } else if (n == 1) { print("1"); return 1; } else return fibonacci(n‐1) + fibonacci(n‐2);}fibonacci(3)을 호출하면 다음과 같이 동작한다.- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출- 두 번째 호출한 fi.. 2024. 5. 1.
시험 대비 코드 정리(2) 보호되어 있는 글 입니다. 2024. 4. 22.
시험 대비 코드 정리(1) 보호되어 있는 글 입니다. 2024. 4. 19.
728x90

티스토리툴바