분류 전체보기
-
[백준]6593: 상범 빌딩 - JAVA문제풀이/백준 2021. 3. 21. 15:03
[백준]6593: 상범 빌딩 www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 최단거리를 찾는 문제이므로 bfs를 사용하여 탐색하였다. 시작 위치, 도착 위치를 입력 받기 위해 Node 클래스를 정의해 주었다. 이 문제는 좌표를 이용한 bfs문제이면서 일반적인 문제와 달리 3차원 공간에서의 bfs최단거리를 찾는 문제이다. 기존의 x, y방향으로만 이동하여 문제를 풀었던 방식을 살짝 변형하여 문제를 풀어 주었다. 이동 방향이 오른, 왼, 위, 아래 4방향에 위층..
-
[백준]2668: 숫자고르기 - JAVA문제풀이/백준 2021. 3. 14. 15:32
문제 www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 뽑힌 정수의 집합과 뽑힌 정수 바로 아래 정수들이 이루는 집합이 일치하는 숫자들을 뽑는 문제였다. 예제의 숫자들 중에서 뽑힌 숫자들을 보면 싸이클을 이루는 숫자들이라는 것을 알 수 있다. 즉, 싸이클을 이루는 숫자들을 뽑는 문제인 것이다. 예를들어 위의 예제에서 발생한 싸이클은 아래와 같당. 1 -> 3 -> 1 (싸이클) 3 -> 1 -> 3 (싸이클) 5 -> 5 (싸이클) 이때 싸이..
-
[프로그래머스]길 찾기 게임 - 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의 문자들을 비..
-
Network - Dynamic Routing ProtocolCS/Network 2021. 3. 11. 20:34
Dynamic Routing Protocol Dynamic Route란? 최적의 경로를 결정하며 라우팅 테이블을 지속적으로 관리한다. 라우팅 프로토콜에 의해 이웃 라우터 끼리 정보를 교환하여 최적의 경로를 확인한다. Dynamic Routing Protocol EGP: 다른 그룹간 라우팅 경로를 설정한다. EX) SK - LG 통신 IGP: 같은 그룹 간 라우팅 경로를 설정한다. EX) SK - SK 통신 1. RIPv2 Metric(목적지 까지 걸리는 시간을 계산하는 방법): hop count를 사용한다. 라우터를 지날 때마다 hop count + 1을 해준다. Distance Vector 자신의 최적 경로만 이웃 라우터에 전달하며 전체 토폴로지를 기억하지 않는다. 라우팅 테이블을 주기적으로 업데이트하..
-
[백준]2458:키 순서 - JAVA문제풀이/백준 2021. 3. 10. 18:34
[백준]2458: 키 순서[백준]2458: 키 순서 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 키를 비교한 결과의 일부를 입력받고, 이를 통해서 유추할 수 있는 비교 순서를 모두 유추한 다음 확실하게 자신의 키가 몇 번째 인지 알 수 있는 학생의 수를 출력하는 문제이다. 모든 학생들의 비교 순서를 비교하면서 유추할 수 있는 비교 순서가 발견되면 값을 변경해 주기 위해 플로이드-와샬 알고리즘을 사용하였다. 풀이 순서는 다음과 같당. MAX값으로 초기화..