문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 이 문제는 '서로소 집합'과 '크루스칼 알고리즘'을 알고 있으면 손쉽게 풀 수 있다. https://born2bedeveloper.tistory.com/29 [JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find) 서로소(Disjoint) 서로소(disjoint)는 공통으로 포함하는 원소가 없는 두 집합의 관계다. 서로소 집합(Disjoint Sets)과 연산(Union & Find) 서로소 집합은 위 그림처럼 서로소 집합..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 이 문제를 보고 처음 생각한 로직은 이랬다. 1. people 무게 오름차순으로 정렬 2. 가벼운 사람부터 구명보트에 limit넘기지 않도록 최대한 때려 넣기(?) 그런데 자꾸 테스트케이스가 오류가 나서 살펴보니... 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 이 문제를 보고 처음에 필자는 이렇게 생각했었다. '조합을 이용해서 숫자를 다 뽑은 다음에, 가장 큰 수를 뽑으면 되지 않을까?' 결과는? 무수한 런타임 에러의 환영을 받았다 ㅎㅎ.. number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. 해당 제한사항 때문에 문자에서 int로 변환하는 과정에서 메모리 초과 이슈로 펑펑 터질 수밖에 없는 것이다^^.. 완전탐색으로 불가능하다면 그리디(greedy)하고 탐욕스럽게 문제를 풀어야한다고 깨닫고 로직 노선을 다시 변경했다. number = "4177252841", k = ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 먼저 조이스틱의 상, 하 조작을 살펴보자. 1. 조이스틱의 상,하 조작으로 원하는 알파벳 조작하기 조이스틱을 위로 조작해 알파벳을 찾는 경우는 '알파벳2' - '알파벳1' 처음 'A'에서 아래로 조작해 찾는 경우는 26(총 알파벳 수) - ('알파벳2' - '알파벳1') ex) 'A' 'C' 의 경우 'C' - 'A' = 2로, 위..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다. 해당 주의사항을 생각하고 로직을 짜면 간단하다. 필자의 로직은 이러하다. 1. 전체학생 n만큼의 배열 int student[n] = 1 로, answer = n으로 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr yellow와 brown의 타일 개수가 주어진 후, 가로 세로를 구하는 문제이다. 갈색 타일은 항상 테두리 1줄만 노란색 타일을 감싸고 있다. 중앙의 노란색 타일은 항상 사각형이다. 늘 가로가 세로보다 길거나 같다. 해당 조건을 생각해 보았을 때, 필자는 하나의 공식을 세울 수 있었다. (타일의 가로 * 세로) - (yellow 가로 * 세로) =..