Java
-
[프로그래머스]길 찾기 게임 - JAVA문제풀이/프로그래머스 2021. 3. 14. 13:50
[프로그래머스]길 찾기 게임 programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 입력받은 데이터를 가지고 트리를 만들고, 전위순회/후위순회한 결과를 반환하면 된다. 트리에 대해 잘 알고 있었다면 크게 어려움 없이 풀 수 있는 문제였고 트리에 대해 잘 모르더라도 이 문제를 통해 트리를 이해하는데 도움이 될만한 좋은 문제라고 생각한다. 이 문제에서 요구되는 트리를 x값을 기준으로 생각한다면 이진검색트리라고 볼 수도 있을 것 같..
-
[백준]16432: 떡장수와 호랑이 - JAVA문제풀이/백준 2021. 3. 13. 15:11
[백준]16432: 떡장수와 호랑이 www.acmicpc.net/problem/16432 16432번: 떡장수와 호랑이 동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 www.acmicpc.net 풀이 전형적인 DFS 탐색 문제로 문제의 조건에 따라 이전에 뽑은 숫자와 다른 숫자를 N만큼 뽑을 수 있다면 뽑은 수를 출력하고, 뽑을 수 없다면 -1을 출력하면 된다. 간단하게 DFS를 사용하여 구현하였다. 그리고 N개를 뽑을 수 있는 방법이 여러개라면 한 개만 출력하면 되므로 N개를 뽑고 출력한 다음 프로그램을 종료시켰다. 만약 DFS를 돌면서 N개를 뽑지..
-
[백준]1405: 미친 로봇 - JAVA문제풀이/백준 2021. 3. 12. 14:27
[백준]1405: 미친 로봇 www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 DFS + 백트래킹을 사용하여 풀었다. 결국엔 문제에서 구하는 값은 같은 곳을 방문하지 않고 N번동안 이동할 때의 확률을 구하는 것이다. 즉 DFS를 사용하여 N번만큼 이동하되 visited 함수를 사용하여 같은 공간은 방문하지 않도록 처리하면 된다. 이때 이동할 확률을 구하는 방법은 같은 공간을 방문하지 않고 이동하며, 이동할 때매다 이동할 방향의 확률을 곱해서 그 값을 ..
-
[프로그래머스]가장 긴 팰린드롬 - JAVA문제풀이/프로그래머스 2021. 3. 12. 13:57
[프로그래머스]가장 긴 팰린드롬 programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 풀이 중첩 반복문을 사용하여 가장 긴 팰린드롬을 찾아내도록 하였다. 가장 긴 팰린드롬을 발견하면 그대로 그 값을 반환하였다. 우선 팰린드롬의 길이를 문자열 s의 길이로 지정한 후 팰린드롬이 아니라면 길이를 1씩 줄여나가면서 찾았다. 그 다음 시작점 부터 팰린드롬의 길이 만큼 s의 문자들을 비..
-
[백준]2458:키 순서 - JAVA문제풀이/백준 2021. 3. 10. 18:34
[백준]2458: 키 순서[백준]2458: 키 순서 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 키를 비교한 결과의 일부를 입력받고, 이를 통해서 유추할 수 있는 비교 순서를 모두 유추한 다음 확실하게 자신의 키가 몇 번째 인지 알 수 있는 학생의 수를 출력하는 문제이다. 모든 학생들의 비교 순서를 비교하면서 유추할 수 있는 비교 순서가 발견되면 값을 변경해 주기 위해 플로이드-와샬 알고리즘을 사용하였다. 풀이 순서는 다음과 같당. MAX값으로 초기화..
-
[백준]1038: 감소하는 수 - JAVA문제풀이/백준 2021. 3. 9. 21:00
문제 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 처음에는 정직한 완전탐색 방법으로, 이전에 뽑은 수에 1씩 더해가며 감소하는 수 인지 판별하며 수를 찾았다. 이렇게 풀면 시간초과가 발생한다. 제일 첫 번째 뽑는 수를 기준으로 감소하는 수를 만들어서 list에 저장하고, list를 정렬하여 n번째 수를 반환하도록 하였다. 예를들어서 아래와 같당. 처음에 뽑는 수 다음에 올 수 있는 수 만들어 지는 수 1 0 10 2 1, 0 21, 2..
-
[백준]2023: 신기한 소수 - JAVA문제풀이/백준 2021. 3. 8. 18:51
[백준]2023: 신기한 소수 www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 수중에 소수를 모두 출력하는 DFS문제이다. 숫자를 자리수 별로 하나씩 뽑으면서 뽑았을 때 소수가 되는 경우만 수를 이어서 뽑는다. 뽑다가 N자리가 되는 순간 출력을 하도록 하였다. 소수를 판별하는 방법은 에라토스테네스의 접근 방식을 사용했다. 소수 판별식 코드는 아래와 같다. public static boolean isPrime(int num) { if(n..
-
[백준]9019: DSLR - JAVA문제풀이/백준 2021. 3. 7. 19:53
문제 www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 A를 B로 표현할 수 있는 최소한의 방법을 출력하는 것이므로 BFS를 사용하였다. 모든 경우에서 4가지 명령어를 실행하고 각각의 실행한 경우에서 또 명령어를 실행하도록 반복해 주었다. 이러다가 B가 되었을때 그때까지의 명령어를 반환하도록 하였다. 현재까지 사용된 명령어를 저장하기 위해서 Node 클래스를 사용해 주었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..