본문 바로가기
728x90

분류 전체보기429

프로그래머스 - 가장 많이 받은 선물 문제문제 설명선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.예를 들어 A가 B에게 선물을 5번 줬고, B가 A에게 선물을 3번 줬다면 다음 달엔 A가 B에게 선물을 하나 받습니다.두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다... 2024. 5. 13.
프로그래머스 - 붕대감기 문제어떤 게임에는 붕대 감기라는 기술이 있습니다.붕대 감기는 t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복합니다. t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다. 게임 캐릭터에는 최대 체력이 존재해 현재 체력이 최대 체력보다 커지는 것은 불가능합니다.기술을 쓰는 도중 몬스터에게 공격을 당하면 기술이 취소되고, 공격을 당하는 순간에는 체력을 회복할 수 없습니다. 몬스터에게 공격당해 기술이 취소당하거나 기술이 끝나면 그 즉시 붕대 감기를 다시 사용하며, 연속 성공 시간이 0으로 초기화됩니다.몬스터의 공격을 받으면 정해진 피해량만큼 현재 체력이 줄어듭니다. 이때, 현재 체력이 0 이하가 되면 캐릭터가 죽으며 더 이상 체력을 회복할 수 없습니다.당신은 붕대감기 기술의 정보.. 2024. 5. 11.
프로그래머스 - 최고의 집합 문제자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.각 원소의 합이 S가 되는 수의 집합위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요. 제한사항최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return.. 2024. 5. 9.
Digital Image Processing - Clustering / Segmentation ClusteringClustering은 대표적인 unsupervised learning의 예시중 하나이다. Clustering은 비슷한 특성을 가진 데이터를 군집화 하는 것을 말한다. 각 군집 내의 데이터는 최대한 유사하고 다른 군집 간의 데이터는 최대한 차별화되도록 하는 것이 clustering의 목적이다. 아래와 같이 다양한 clustering기법이 존재하고 각각 데이터 구조에 따른 분류 성능이 다르다. Clustering 과정을 아주 간단히 말하면 군집내의 분산을 최소화하는 과정이다. 이는 아래와 같이 식으로도 표현할 수 있다.각 군집의 데이터와 군집의 중심간의 거리의 합의 평균이 최소가 되도록 하는 것을 볼 수 있다.K-Means ClusteringK-Means Clustering은 군집의 수 K.. 2024. 5. 8.
알고리즘 설계 실습 - 삼각분할 문제정N각형 P는 P의 두 꼭지점 쌍들을 연결하는 선분 (모든 선분은 교차하지 않아야 함)으로 N-2개 의 삼각형으로 분할될 수 있습니다. 예를 들어, 정사각형은 두 개의 삼각형으로, 정오각형은 세 개의 삼각형으로, 정육각형은 네 개의 삼각형으로 분할될 수 있습니다. 이러한 삼각형들의 집합 T 를 P의 삼각 분할이라고 합니다.P의 삼각 분할의 집합 T 내의 두 삼각형 a와 b 사이의 거리는 a에서 b로 이동할 때 인접한 두 삼각형의 경계를 넘는 횟수로 정의됩니다. 이동하는 동안 언제든지 정N각형 P 내부에 머물러야 하며, P의 경계를 넘어서는 이동은 허용되지 않습니다. 우리는 정N각형의 삼각 분할 집합 T 내 모든 삼각형 쌍 사이의 거리의 최댓값 중에서 최소인 값을 찾는 프로그램을 작성해야 합니다.예를 .. 2024. 5. 8.
프로그래머스 - 과일 장수 문제 설명과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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.
728x90

티스토리툴바