Algorithm
-
프로그래머스 Lv.2) 튜플알고리즘/프로그래머스 카카오 2020. 5. 19. 22:21
튜플 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 풀이 답의 규칙을 찾은 결과 가장 작은 크기의 부분 수열이 가진 원소의 순서대로 답의 순서가 정해진다는 것이었다. "{{1,2,3},{2,1},{1,2,4,3},{2}}" 위의 예제로 설명하면, 가장 작은 크기의 부분수열 {2}로부터 2가 정답의 맨 첫번째임을 알 수 있고, 그다음 {2,1}을 통해 2->1, {1,2,3}을 통해 2->1->3, {1,2,4,3}을 통해 2->1->3->4가 되는 것이다...
-
프로그래머스 Lv.2) 124 나라의 숫자알고리즘/프로그래머스 2020. 5. 16. 17:30
124 나라의 숫자 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 풀이 이 문제도 고민의 시간이 길었다. 문제 자체는 이해하기 쉬웠다. 모든 10진법 숫자는 1,2,4 세 개를 통해 표현해야하는 문제이고 3진법과 비슷한 느낌이라고 생각했다. 다만 다른 점?은 세가지 숫자만 이용하는데 1,2,3이 아닌 1,2,4라는 것이다.. ㅎㅎ 조금 특이하게 이 문제는 로직 자체는 쉽게 떠올랐으나, 구현이 오래걸렸다. (멀쩡한 사각형과 이 문제는 어제 푼 문젠데, 어제 컨디션이 별로였..
-
프로그래머스 Lv.2) 스킬트리알고리즘/프로그래머스 2020. 5. 16. 16:42
스킬트리 코딩테스트 연습 - 스킬트리 programmers.co.kr 풀이 (2020.05.16) 스킬을 찍어야하는 순서를 ArrayList에 char로 담아주었다. 또한, char를 담으면서 해당 스킬이 ArrayList에 부여된 인덱스 넘버를 HashMap을 통해 저장해주었다. 이후, 스킬 트리 배열을 돌면서 String값을 검증했다. 우선 모든 스킬이 가능하다는 가정을 두고 스킬트리 배열의 길이 만큼 return할 결과에 담아주었다. String을 돌 때마다 해당 SkillTree를 위한 ArrayList에 스킬을 저장하면서 확인했다. String의 index마다 그 스킬이 찍어야하는 스킬 ArrayList에 담겨있는지 먼저 확인하고, 배워야하는 스킬이면 이 스킬 이전에 배워야하는 스킬을 배웠는지 ..
-
프로그래머스 Lv.2) 카카오프렌즈 컬러링북알고리즘/프로그래머스 카카오 2020. 5. 16. 16:34
카카오프렌즈 컬러링북 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 그림의 난이도를 영역의 수로 정의했다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다. picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다. 이 두 부분만 유의하면 어렵지 않게 풀 수 있었다. 영역의 갯수와 가장 넓은 공간을 가지고 있는 영역의 넓이를 리턴해야하기 때문에 1. 먼저 grouping을 해주고 2. 해당 그룹의 넓이를 HashMap에 저장해주었다. grouping을 할때는 out of index..
-
프로그래머스 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. 각 구역에서 다른 구역으로 이동하는 경우에 두 그룹의 넘버와 사다리의 비용을 우선순위 큐에 ..
-
알고리즘) 프로그래머스 Graph, 사이클 제거알고리즘/프로그래머스 고득점 Kit 2020. 5. 1. 15:37
프로그래머스 고득점Kit - Graph 사이클 제거 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 노드의 사이즈를 돌면서 하나씩 제거하고 사이클이 있는지 없는지 체크했다. 결과적으로 정확성 테스트는 다 맞지만, Cycle을 확인하는 메소드를 재귀로 호출하여 효율성은 다 틀린 것 같다. 이후 이 문제를 푼 분들의 로직을 보면서 가장 매력적인 로직을 찾아냈다. 전체 노드의 갯수 -1 개가 되면 사이클이 없다는 것이다. 다만, 컴포넌트의 갯수가 1개가 아닌 2개~n개일 때는 컴포넌트의 갯수도 같이 세줘야 한다는 것이다. 이 로직에 따라 코드를 짜봤지만, ..