문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 첫 5단계 문제풀이.. 특별한 알고리즘을 요하지 않지만, 방이 만들어지는 조건과 필요한 변수의 타입을 확실하게 지정해주지 않으면 시간초과나 메모리 초과 이슈가 생긴다. 문제 풀이 먼저, 화살표가 움직인 범위를 사각형(행렬) 기준으로 구해보자. arrows 배열을 쭉 돌며 움직인 방향을 변수에 담는다. 오른쪽 방향이 들어간 화살표(오른쪽 위, 오른쪽, 오른쪽 아래)는 width+1 왼쪽 방향이 들어간 화살표(왼쪽 위, 왼쪽, 왼..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 풀이 과정 필자는 이 문제를 보고 순서대로 로직을 정리해봤다. 1. 선수별 경기 결과를 인접행렬에 저장한다. 선수 1이 선수 2를 이긴 경우, graph[1][2] = 1, 선수 2가 선수 1에게 졌으니 graph[2][1] = 0이 들어간다. 2. 주어진 경기 결과로 구현한 인접행렬을 바탕으로 확정된 순위를 구한다. 선수가 N명일 때, 선수a가 지고, 이긴 경우를 합쳐 N-1인 경우 해당 선수의 순위를 확정지을 수 있다. ex) 선수 2의 경우, 이긴 경기..

플로이드-워셜 알고리즘 그래프에서, 한 정점에서 다른 정점으로 가는 최단거리가 있다. 플로이드-워셜 알고리즘을 사용한다면 각각의 모든 정점에서 모든 정점으로 가는 최단거리를 전부 구할 수 있다. 즉, 1 ~ 2, 1 ~ 3, 1 ~ N 2 ~ N 3 ~ N 4 ~ N 5 ~ N 모든 경로에서 전부 최단 거리를 구할 수 있다. 2 -> 1로 가는 최단 경로를 볼 때, 2 -> 1은 9 2 -> 3 -> 1은 7로 노드 3을 거쳐가는 것이 더 빠름 이렇게 노드를 거쳐서 가는게 더 빠른 경로까지도 플루이드-워셜 알고리즘을 통해 구할 수 있다는 것이다. 플로이드-워셜 알고리즘은 DP(Dynamic Programming) 기법을 사용한 알고리즘이다. 즉, 노드 0개를 거쳐가는 최단거리를 구하고, 노드 1개, 노드..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 과정 문제에 주어진 그림을 보자 마자 바로 그래프 자료구조로 접근했다. https://born2bedeveloper.tistory.com/42 [JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트) 그래프(Graph)란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex : 정점 edge : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이 문제 역시 제한사항을 보면 1,000,000,000 이하 라는 어마어마한 범위를 가지고 있다. 즉, 완전탐색으로는 백퍼센트 타임오버라는 것이다. 따라서 효율적으로 값을 찾을 수 있는 이분 탐색을 사용할것이다. 이분 탐색 https://born2bedeveloper.tistory.com/40 [프로그래머스] 입국심사-JAVA 문제 링크 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제의 제한사항을 보면 1,000,000,000이라는 택도없이 큰 숫자가 등장한다. 보통 제한사항의 숫자가 큰 경우에는 완전탐색등의 방법을 쓰면 경우의 수가 어마무시하게 커지게 될 것이다. 이런 경우에는 효율적인 알고리즘을 채택해야 하는데, 필자는 이 문제에서 '이분 탐색'을 선택했다. 이분 탐색 이분 탐색은 일련의 데이터들 중에서 하나의 값을 찾을 때..