알고리즘
-
[Programmers] 순위(그래프, 플로이드와샬)알고리즘/알고리즘 풀이 2021. 4. 19. 17:06
프로그래머스 순위(그래프, 플로이드와샬) 풀이 리뷰 그래프 플로이드와샬 플로이드와샬을 통해 계속해서 순위를 업데이트해준다. a가 b를 이겼고,b가 c를 이겼으면,a가 c를 이겼다고 표시해주는 거다. 그리고 모든 행과 열을 비교하면서 승패가 확정났는지를 확인한다. 한 행을 돌 때마다 i, j 둘 중에 승패가 확실한 경우 count = n-1이 된다. 따라서 count == n-1이 되는 경우가 바로 순위가 확정난 경우이다. 문제 출처 programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr
-
[정렬] 계수 정렬알고리즘/알고리즘 개념 2021. 4. 14. 18:30
계수 정렬이란? 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 counting 값을 저장할 새로운 배열 공간이 필요함 비교정렬 X 안정정렬 시간 복잡도 모두 O(N+K) (데이터 개수 = N, 데이터 중 최댓값 = K) 언제 사용하면 좋을까? 때에 따라서 비효율적임 데이터가 0, 999999 와 같이 2개의 숫자가 있을 때, 정렬할 데이터는 적지만 1000000크기를 지닌 counting 배열을 생성해야 된다. 따라서, 동일한 값을 가지는 데이터가 여러 번 등장할 때 사용하면 좋음 구현 코드 int main () { int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, ..
-
[BOJ] 16926 배열 돌리기1알고리즘/알고리즘 풀이 2021. 4. 14. 01:23
백준 16926 배열 돌리기1 [문제 풀이] 구현 배열을 돌릴 테두리 갯수를 센다. -> (min(n,m)+1)/ 2 규칙에 따름 북->동->남->서 방향으로 하나씩 회전을 하는데, range체크를 한다. 범위 내면 한 칸씩 복사, 범위 밖이라면 dir++ 해서 방향 전환시킨다. [출처] www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net
-
[BOJ] 17144 미세먼지 안녕!알고리즘/알고리즘 풀이 2020. 4. 19. 17:23
문제 설명 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다...
-
[BOJ] 15686 치킨 배달알고리즘/알고리즘 풀이 2020. 4. 19. 16:45
문제 설명 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같..
-
[BOJ] 15685 드래곤 커브알고리즘/알고리즘 풀이 2020. 3. 24. 16:36
문제 설명 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다. 2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다) 3세대 드래곤 커브도 2세대 드래곤..