프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다. 다음은 6 x 6 크기 ..

플로이드 워셜 알고리즘이란? 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 이전에 배웠던 다익스트라 알고리즘은 한 노드에서 가능한 모든 노드 쌍에 대해 최단 거리를 구했기 때문에 이 점이 2가지의 알고리즘에 차이라고 할 수 있다. 플로이드 워셜 알고리즘의 시간 복잡도는 O(N³)으로 3중 for문으로 보통 모든 경우의 수를 비교한다. 플로이드 워셜 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 그래서 k를 두어서 모든 노드에 대해서 최단 거리를 구할 수 있도록 하였다. fun floydWarshall() { val d = Array(4) { IntArray(4) } for (i in 0 until 4) { for (j in 0 ..

다익스트라 알고리즘이란? 다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는알고리즘이다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 처음 고안되었을때의 다익스트라 알고리즘은 O(N²)의 시간복잡도를 가진다. 이후에 PriorityQueue 를 이용해서 O(NlogN) 까지 시간복잡도를 줄이는 방식이 고안되었다. 다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 ..

PriorityQueue 우리는 이전에 Queue의 구조에 대하여 학습한적이 있다. Queue는 First In First Out 구조로 먼저 집어넣은 데이터가 먼저 나오는 구조를 가지고 있다. 하지만 PriorityQueue는 이름에서 알 수 있듯이 Queue의 구조에서 데이터의 우선순위에 따라서 우선순위가 높은 데이터가 먼저 나오는 구조를 가지고 있다. 위의 구조는 PriorityQueue의 구조이다. 데이터를 무작위로 Enqueue 했을때 그 순서와 상관없이 우선순위가 높은 데이터가 가장 왼쪽에 위치하는 것을 알 수 있다. 구현 PriorityQueue의 구현은 Array, LinkedList, Heap으로 가능하다. 다만 Array와 LinkedList는 매번 가장 높은 우선순위의 데이터를 가장 ..

이번에는 ArrayList와 LinkedList에 대해서 알아보도록 하겠다. 이름만 봐도 알 수 있듯 2개의 자료구조는 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체이다. 하지만 동작하는 기능은 서로 다르기 때문에 하나하나 알아보고자 한다. ArrayList ArrayList는 중복을 허용하고 순서를 가지며 인덱스로 원소들을 관리한다. 이 말을 들으면 우리는 바로 ArrayList는 Array와 매우 유사한 기능을 가지고 있다고 생각할 수 있다. ArrayLIst란 이름에서도 알 수 있듯이 Array의 이런 점, List의 데이터가 저장될 때 필요에 의해 자동으로 늘어나며 순서를 가지는 점을 가지고 있다. Array와 가장 큰 차이점은 Array는 처음에 크기를 지정하면 그..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다. 예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을..

11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제 뿌요뿌요의 룰은 다음과 같다. 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다. 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다. 아래로 떨어지고 나서 다시..

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구..