문제 링크 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 : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 ..

그래프(Graph)란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex : 정점 edge : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 행렬, 인접 리스트 방식으로 표현할 수 있다. 그래프 구현 - 인접 행렬 먼저, 행렬로 구현하는 방식을 살펴보자 정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다. 만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다. 기본적으로 무방향 그래프의 경우는 (a,b) (b,a)에 모두 간선 값을 넣지만, 방향 그래프같은 경우는 위의 표와 같이 방향에 맞는 간선만 표기한다. ex) 정점 1과 3을 잇는 간선이 존재할 때 : graph[1][3] = 1, gr..

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