algorithm
-
[프로그래머스] 자물쇠와 열쇠 (07.26)algorithm/프로그래머스 2020. 7. 26. 16:31
문제 https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 접근법 저번에 풀었던 적이 있는데도 다시 풀기가 어려웠다. 저번에는 dfs를 통해서 배열을 90도로 돌렸는데 이번엔 순수 포문만을 사용했다. 열쇠의 모든 부분이 자물쇠와 겹쳐야 하는 것이 아니고 상하좌우로 움직여서 열쇠의 일부분만을 결합시킬 수도 있다. 따라서 열쇠와 자물쇠가 모두 들어갈 수 있는 큰 배열을 만들고 열쇠를 삽입하며 가능성을 확인한다. solution 메소드에선 배열을 90도로 돌리고, 배열..
-
[프로그래머스] 2xN 타일링 (07.25)algorithm/프로그래머스 2020. 7. 26. 00:00
문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 �� programmers.co.kr 접근법 dp문제의 가장 기본이 되는 문제이다. 점화식은 dp[n] = dp[n-1] + dp[n-2]로 도출할 수 있었다. n-1이 되는 경우는 1x2 타일이 하나 들어갈 경우, n-2가 되는 경우는 2x1 타일이 위아래로 두개 들어간 경우가 해당된다. n-2일때 1x2타일이 좌우로 두개 들어가는 가능성을 생각할 수도 있는데 이 가능성은 ..
-
[프로그래머스] N으로 표현 (07.24)algorithm/프로그래머스 2020. 7. 24. 19:05
문제 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 접근법 문제 분류는 DP로 되어있지만 DFS로 해결하였다. 그냥 사칙연산만 있었다면 간단했을텐데 55, 555처럼 숫자를 이어 붙이는 것까지 가능해서 좀 복잡했다. tmp라는 변수를 두고 그 변수에 55, 555같이 이어붙여지는 숫자를 넣어주었다. 8개 이상의 숫자는 사용할 수 없으므로 반복문은 8까지만 돌렸다. 코드 class Solution { private int min = Integer.MAX_VALUE; private int N = 0; private int number = 0; public int solution(int N,..
-
[프로그래머스] 종이 접기 (07.23)algorithm/프로그래머스 2020. 7. 23. 14:53
문제 https://programmers.co.kr/learn/courses/30/lessons/62049 코딩테스트 연습 - 종이접기 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽�� programmers.co.kr 접근법 규칙을 찾아서 dp를 적용시켰다 dp[n] = dp[n-1] + "0" + reverse(dp[n-1]) 라는 점화식을 도출해내고 reverse라는 메소드를 따로 만들어서 빼주었다. 전에는 재귀로 풀었는데 이번에는 dp로 풀었당!! 코드 class Solution { public int[] solution(int n) { String[]..
-
[프로그래머스] 숫자 야구 (07.20)algorithm/프로그래머스 2020. 7. 20. 23:29
문제 https://programmers.co.kr/learn/courses/30/lessons/42841 코딩테스트 연습 - 숫자 야구 [[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]] 2 programmers.co.kr 접근법 완전 탐색이라는 분류에 맞게 가능한 모든 경우의 수를 체크했다. 범위가 세 자리 수로 많지 않으므로 123부터 897까지 직접 확인했다. 문제에서 서로 다른 세개의 수라고 했으므로 세 숫자는 모두 달라야 하고 1~9까지의 범위라고 했으므로 0이 들어가면 안되는 조건을 고려하여 진행하였다. 코드 import java.util.*; class Solution { public int solution(int[][] baseball) { Se..
-
[프로그래머스] 라면공장 (07.16)algorithm/프로그래머스 2020. 7. 16. 18:19
문제 https://programmers.co.kr/learn/courses/30/lessons/42629 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 접근법 우선순위 큐라는 것을 사용하였다. Comparator 메소드를 파라미터로 지정해주면 메소드의 성질에 따라 정렬이 된 상태로 큐에 삽입이 가능하다. for문을 k(마지막날)까지 돌리면서 stock을 하나씩 빼주었다. 그 과정에서 밀가루가 공급되는 날마다 우선순위 큐에 넣어주고 stock이 0이 될때마다 밀가루 공급량이 내림차순으로 저장된 큐에서 하나..
-
[프로그래머스] 여행경로 (07.15)algorithm/프로그래머스 2020. 7. 15. 18:43
문제 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 접근법 백트래킹으로 해결했다. 도착지와 출발지를 비교해가면서 DFS로 배열을 순회한다. 순회를 하면서 모든 경로를 str이라는 배열에 이어붙여주고 모든 티켓을 사용하게 되면 str에 저장된 경로를 리스트에 저장해준다. 제한 사항에서 경로가 2개 이상이라면 알파벳 순으로 하라고 했기 때문에 Collections.sort를 통해서 배열을 알파벳 순으로 정렬해주고 경로를 배열로 바꿔 ..
-
[프로그래머스] 단어 변환 (07.13)algorithm/프로그래머스 2020. 7. 13. 16:01
문제 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 접근법 먼저 당연히 DFS 일거라고 생각하고 풀었다. 백트래킹을 통해서 모든 배열을 확인하고, target에 도달할 때마다의 cnt 값들 중 최소값을 최종 결과로 리턴하였다. 다 풀고 다른 사람들의 풀이를 보는데 대부분의 사람들이 BFS로 풀었다. 그래서 나도 BFS로도 다시 풀어보았다. 방법은 비슷하였다. 코드 ..