SilentWalk

문제 풀이과정 문제를 풀기에 앞서, 문제에 주어진 조건을 먼저 살펴보면 단체사진을 찍을 프렌즈는 8명으로 고정되어있음을 알 수 있다. 즉, 만일 무조건 만족할 수 있는 조건만 주어졌다면 최대 8! = 40320 개의 경우의 수가 존재함을 알 수 있다. 조건의 최대 갯수는 100개로 주어졌다. 따라서 모든 가능한 경우의 수를 먼저 계산한 후, 각각의 경우의 수가 조건을 만족하는지를 확인하게 된다면 최대 약 400만 번의 조건 확인 작업을 거치게 될 것임을 알 수 있다. 위의 두 가지 점으로부터 미루어 보아 조건을 생각하지 않고 모든 가능한 경우의 수를 먼저 구한 후, 각각의 경우의 수가 주어진 조건을 모두 만족하는지 검사하여도 크게 시간적으로 무리가 가지 않을것이라 예상하였다. 풀이과정은 아래와 같은 과정..

문제 풀이과정 주어진 사람들의 무게를 정렬한다. 현재 남아있는 사람들 중 가장 무거운 사람(주어진 배열의 가장 뒤쪽 index부터 센다)과 가장 가벼운 사람의 무게(주어진 배열의 가장 앞 index부터 센다)의 합이 무게 제한을 초과하면 가장 무거운 사람이 혼자서 보트를 타야 한다. 배열 뒤에서부터 세는 index 값 1 감소 2번의 계산에서 무게 제한을 초과하지 않을 경우 가장 무거운 사람과 가장 가벼운 사람이 함께 구명 보트에 탑승한다. 배열 뒤에서부터 세는 index 값 1 감소 배열 앞에서부터 세는 index 값 1 증가 무거운 사람의 순서를 나타내는 index 값이 가벼운 사람을 나타내는 index 값보다 큰 동안 2~3번 과정을 반복한다. 반복이 종료되었을 때 두 index가 같다면 마지막 한..

로또의 최고 순위와 최저 순위 문제 : 로또의 최고 순위와 최저 순위 풀이과정 로또의 최고 순위는 알아볼 수 있는 번호가 맞은 갯수 + 알아볼 수 없는 번호도 모두 맞을 경우 를 통해 알 수 있다. 로또의 최저 순위는 알아볼 수 없는 번호가 모두 틀렸을 때, 알아볼 수 있는 번호 중 맞은 갯수 를 통해 알 수 있다. 이를 찾기 위해 아래의 과정을 수행한다. 알아볼 수 없는 번호를 모두 제거하고, 알아볼 수 있는 번호만 남긴다. 이 과정에서 알아볼 수 없는 수의 갯수를 알 수 있다. 알아볼 수 있는 번호 중 정답 번호와 일치하는 것들의 갯수를 센다. 위 1과 2에서 얻은 결과를 바탕으로 등수를 계산한다. 이 때, 맞은 갯수가 0개 또는 1개일 경우 모두 6등이므로 이 경우에 대한 고려가 필요하다. 여기서는..

문제 : 소수찾기 - Programmers 풀이과정 Permutation을 이용하여 주어진 숫자 카드들로 만들 수 있는 모든 경우의 수를 구한다. 참고 모든 경우의 수를 계산할 때, 카드를 1장만 사용해서 만드는 경우의 수 부터(맨 앞에서 1자리만) 카드를 n장 사용해서 만드는 경우의 수(맨 앞에서부터 n장)까지 모든 수를 Set에 저장한다. (1 ≤ n ≤ 전체 카드의 수) 2의 결과로부터 Set에는 주어진 카드들로 만들 수 있는 모든 정수가 적혀 있다. 여기서 가장 큰 값을 계산한다. → Collections.max() 3의 결과로 얻은 수에 대해서 에라토스테네스의 체 알고리즘을 사용하여 1부터 해당 수 까지의 소수 테이블을 구한다. 4의 결과로 얻은 테이블을 사용하여 Set에 들어있는 모든 숫자들이..

문제 : 카펫 - 프로그래머스 풀이 간단한 중학교 수학 문제를 코드로 옮겨 풀이하는 문제이다. 주어진 조건 테두리 1줄은 모두 갈색이다. 테두리 1줄을 제외한 중앙부분은 모두 노란색이다. 카펫의 가로 길이는 세로 길이와 같거나 세로 길이보다 길다. 갈색으로 칠해진 격자의 수는 8 이상 5,000 이하인 자연수이다. 노란색으로 칠해진 격자의 수는 1 이상 2,000,000 이하인 자연수이다. 식 세우기 주어진 카펫의 가로길이가 width, 세로길이가 height 라고 했을 때, 갈색으로 칠해진 격자의 수와 노란색으로 칠해진 격자의 수는 각각 다음과 같은 식으로 나타낼 수 있다. brownCount 갈색으로 칠해진 격자의 수 = (width * 2) + (height - 2) * 2 yellowCount 노..

문제 : https://programmers.co.kr/learn/courses/30/lessons/17676

문제 : https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 풀이과정 먼저, 두 정수의 최소공배수를 계산하는 수식을 살펴보면 다음과 같다. 이 식을 통해 두 정수의 GCD를 알면 LCM을 계산할 수 있음을 확인 할 수 있다. 이 때, GCD를 계산하는 방법으로 유클리드 호제법(https://en.wikipedia.org/wiki/Euclidean_algorithm)을 활..

StringBuffer 저장하고 있는 문자열을 변경할 수 있는 클래스이다. 내부적으로 문자열 편집을 위한 버퍼를 가지고 있으며, 인스턴스를 생성할 때 그 크기를 직접 지정해 줄 수도 있다. default size는 16으로 설정되어 있다. 편집 중인 문자열의 길이가 버퍼의 길이를 초과하면 버퍼의 길이를 늘려주는 작업이 추가로 수행되어야 한다 → 효율성 하락 인스턴스 생성시에 버퍼로 사용하기 위한 char형 array가 생성되는 것으로 알고 있었는데, 실제 코드를 열어 보면 byte array 타입으로 멤버변수가 선언되어 있다. 내부 코드를 조금 살펴보면 문자열이 UTF-16과 LATIN1 방식 두 가지 인코딩 방식으로 존재할 수 있기 때문에 이를 모두 지원하기 위한 방법인 것으로 생각된다. 그래서 인스턴..