알고리즘
-
프로그래머스 Lv.4) 3xn 타일링알고리즘/프로그래머스 2020. 5. 14. 23:45
3xn 타일링 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 타일링 시리즈 문제로 DP 문제이다. 하지만, 점화식 세우는데 애를 먹었다. 우선, 홀수의 경우 타일을 채울 수 없다는 것과 dp[n] = dp[n-2]*3 부분까지는 쉽게 세울 수 있었다. n이 2씩 증가할 때마다 새롭게 생기는 3x2의 직사각형 부분을 채우는 경우의 수가 3가지기 때문에 이 전보다 3배의 경우의 수가 더 생긴다. 이해하기 힘들었던 부분은 n이 4마다 새롭게 생기는 2가지 경우의 수였다. n이 4 증가할 때마다 생기는 이 부분 때문에 많은 고민을 하게했고, 다른 분들이 포..
-
프로그래머스 Lv.3) 2xn 타일링알고리즘/프로그래머스 2020. 5. 14. 23:28
2 x n 타일링 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 1 이 문제도 풀었었는데..?? 하는 생각이 들었다. 나중에 알고보니 백준에 타일링 시리즈가 많다는 것을 들었다. dfs의 로직을 dp로 옮기는 문제 중 가장 기본인 문제라고 생각한다. 이 문제는 피보나치 수열을 이용하는 문제로 무리없이 풀 수 있었다. 2020.06.03) 코드 2 얼마 전, 멀리뛰기 문제를 풀면서, 피보나치를 배열이 아닌 세 변수를 이용해 푼 기억이 났다. 그래서 이 문제에서도 배열이 아닌, 변수 세 개를 이용해 풀면서 완벽히 숙지했나 확인하려고 다시 풀었다. ..
-
프로그래머스 Lv.4) 지형 이동알고리즘/프로그래머스 2020. 5. 14. 23:23
지형이동 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 언젠가 풀었던 문제인 것 같기도 하고.. 아닌 것 같기도 하다. 아무튼 처음에 생각한 것은 for문을 돌면서 dp로 최소 값을 누적해가는? 로직으로 풀었는데 많이 틀린 것을 보고 이 로직은 풀 수 없다고 판단했다. MST에 약하다고 생각해서 최대한 기피하려고 했지만, 검색이나 다시 생각해봐도 MST를 통해 풀어야겠다는 생각이 들었다. 1. 사다리 없이 이동할 수 있는 섹터를 Grouping 해준다. 2. 각 구역에서 다른 구역으로 이동하는 경우에 두 그룹의 넘버와 사다리의 비용을 우선순위 큐에 ..
-
프로그래머스 Lv.3) 종이접기알고리즘/프로그래머스 2020. 5. 14. 00:35
종이접기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 (코드 1, 코드 2) 문제를 보자마자 점화식이 필요한 문제라고 생각했다. 그래서 처음 생각한 점화식은 n => n-1까지의 결과를 두 번 반복하고 끝에 1이 들어간다고 생각했다. 주어진 테스트 케이스만 봤을 때는 답이 나오기는 했다. 하지만 제출 결과는 0점이었다. 점화식이 틀렸다는 것을 알아차리고 새로운 점화식을 세우려했다. 하지만 어제 과음.. 다른 분의 점화식을 참고하니까 2^(n-1)을 기준으로 대칭되는 인덱스는 서로 다른 값을 가지고 있다는 식을 보았다. 물론 기준점(2^(n-1)) ..
-
-
알고리즘) 카카오 블라인드 채용 2020, 외벽 점검알고리즘/프로그래머스 카카오 2020. 5. 8. 20:38
Kakao Blind Recruitment 2020 외벽 점검 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한사항 n은 1 이상 200 이하인 자연수입니다. weak의 길이는 1 이상 15 이하입니다. 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다. 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다. weak의 원소는 0 이상 n - 1 이하인 정수입니다. dist의 길이는 1 이상 8 이하입니다. dist의 원소는 1 이상 100 이하인 자연수입니다. 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 retur..
-
프로그래머스 Lv.2) 폰켓몬(포켓몬, Pokemon)알고리즘/프로그래머스 2020. 5. 7. 17:25
폰켓몬 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제 역시 스킬 체크를 풀다가 나왔다. 보자마자 최근 많이 풀고있던 이분탐색(이진탐색, Binary Search)라는 것을 눈치챘고, 포켓몬 타입의 수가 리턴값이기 때문에 left, right, mid도 쉽게 정할 수 있었다. 그나마 생각할 시간이 조금 필요했던 부분은 이 기준을 어떻게 이용해서 값을 얻을 것이냐였다. 내가 찾은 답은 타입의 종류를 담은 배열을 만들어 중복 체크를 하는 것이었다. 1~200,000까지 분류 번호가 된다는 조건이 있어서 배열을 200,001만큼 초기화 시켜줬다. ..
-
프로그래머스 Lv.2) 최솟값 만들기알고리즘/프로그래머스 2020. 5. 7. 17:14
최솟값 만들기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 스킬 체크를 풀다 나온 문제이다. 문제와 예시를 보자마자 최소값이랑 최대값이랑 곱해서 더하면 평균으로 맞춰지니까 최소가 아닌가? 하는 생각이 들었고 그 생각이 맞았다. 1. 두 배열을 정렬해준다. 2. A는 첫번째 값부터 B는 마지막 값부터 곱해서 더해준다. 코드 import java.util.Arrays; public class MakeMinNum_12941 { private static int solution(int []A, int []B) { int answer = 0; Arrays...