문제풀이
-
[프로그래머스]하노이의 탑 - JAVA문제풀이/프로그래머스 2021. 2. 18. 14:06
[프로그래머스]하노이의 탑 programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 풀이 DP의 전형적인 문제인 하노이의 탑 문제이다. 하노이의 탑은 문제 설명에도 나와있듯이 N개의 원판을 1번 기둥에서 3번 기둥으로 2번 기둥을 사용하여 조건에 맞게 이동시키는 문제이다. 이 문제를 이해하기 위해 N이 작은 때를 생각해 보았다. N이 2라면 2개의 원판을 1 -> 2 -> 3으로 옮기는 경우의 수가 될 것이고..
-
[백준]2341: DDR - JAVA문제풀이/백준 2021. 2. 18. 13:34
[백준]2341: DDR www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 DP문제로 왼쪽, 오른쪽 발의 위치를 바꾸어 가면서 최소값을 찾아내야 한다. 이때 항상 이전의 왼쪽 발의 위치와 오른쪽 발의 위치를 기억하고 있어야 해서 DP를 3차원 배열로 선언해 주었다. DP[][][]에서 각 자리의 의미는 DP[현재 밟아야 할 위치][이전의 왼쪽발 위치][이전의 오른쪽발 위치]이다. 이러한 상황에서 두 가지 경우가 존재한다...
-
[백준]1238: 파티 - JAVA문제풀이/백준 2021. 2. 17. 17:44
[백준]1238: 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 처음에는 다익스트라 알고리즘을 사용하여 풀려고 하였다. X에서 모든 마을 까지의 거리를 구하는 방법은 어렵지 않았으나 모든 마을에서 X까지 거리를 구하는 방법이 어려웠다. 결국 각각의 마을에서 X까지 가는 모든 최단거리를 구하고 그 중에 X로 가는 거리만 뽑아내려고 하였다. 그런데 생각해보니 이건 모든 노드에서 모든 노드까지의 최단거리를 구하는 것과 다..
-
[백준]11404: 플로이드 - JAVA문제풀이/백준 2021. 2. 17. 15:11
[백준]11404: 플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 최단거리 알고리즘 공부한 기념으로 관련 문제들을 풀어보았다. 이 문제는 플로이드-워샬 알고리즘을 쓰면 바로 답이 나온다! 모든 정점에서 모든 정점까지의 최단거리를 구하는 문제이다. 문제를 꼭 제대로 읽자! 출력 설명에 i에서 j로 가는 길이 없으면 0을 출력한다고 되어있다. 이를 체크 안해주면 98프로에서 틀린다. 꼭꼭 문제를 제대로 읽자. 코드 1 2 3 4 5 6 7 8 9..
-
[프로그래머스]합승 택시 요금 - JAVA문제풀이/프로그래머스 2021. 2. 17. 13:59
[프로그래머스]합승 택시 요금 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 방향성이 없는 연결 그래프에서 최단 경로를 구해야 하는 문제였..
-
[백준]2887: 행성 터널 - JAVA문제풀이/백준 2021. 2. 16. 18:57
[백준]2887: 행성 터널 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 MST유형의 문제로, 모든 간선의 정보를 만들어서 그 중에 작은 간선을 선택하면서 최소 간선을 찾을 수 있게 kruskal 알고리즘을 사용하여 구현하였다. 행성의 정보를 입력받을때 이차원배열을 사용하여 2중 반복문으로 모든 노드의 거리의 최솟값을 구해 q에 넣어주었더니 메모리 초과가 났다. 행성의 정보를 저장하는 class를 따로 구현해주었고 x..
-
[백준]1922: 네트워크 연결문제풀이/백준 2021. 2. 16. 16:52
[백준]1922: 네트워크 연결 www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 어제 MST를 공부한 기념으로 MST문제를 풀어보았다! MST는 prim알고리즘과 kruskal알고리즘으로 풀 수 있다. 두 알고리즘을 모두 사용하여 문제를 풀어보았다. 이번 문제는 변형 1도 없이 MST알고리즘만 쓰면 답이 나온다! 코드 prim algorithmn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..
-
[프로그래머스]불량 사용자 - JAVA문제풀이/프로그래머스 2021. 2. 16. 14:25
[프로그래머스]불량 사용자 programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 풀이 백트랙킹을 사용하여 뽑을 수 있는 모든 경우의 수를 뽑은 뒤 HashSet에 저장해 중복된 값이 이미 있었으면 저장이 되지 않도록 하였다. 그리고 마지막으로 set의 size를 return하였다. 문자열을 비교할 때는 정규식을 사용하기 위해 banned_id의 "*"을 모두 "."으로 바꾸어 주었다. 그리고 mathes()함수를 사용해 정규식과 u..