알고리즘
-
[Python] 백준 17182 우주 탐사선알고리즘/문제풀이 2021. 8. 7. 18:44
1. 문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 2. 문제 요약 모든 행성을 탐사하기 위한 최소 시간을 출력한다. 3. 아이디어 정리 플로이드 와샬. 모든 정점 최단 거리 구하기 행성을 백트래킹으로 탐색하여 모든 행성 방문하여 최소 시간 구하기 참고 - 플로이드와샬 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 플로이드 워셜 점화식 각 단계마다 특정한 노드 k를 거쳐 ..
-
[Python] 백준 14719 빗물알고리즘/문제풀이 2021. 8. 7. 18:41
1. 문제 링크 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 2. 문제 요약 아래 그림과 같이 빗물의 총량을 구하기 3. 아이디어 정리 투 포인터를 이용하여 빗물 총량을 구한다. ⇒ 오른쪽 포인터 최댓값, 왼쪽 포인터 최댓값을 이용해서 빼준다 오른쪽 포인터 최대값이 큰 경우, 왼쪽 빗물 구하기 & 왼쪽 이동 왼쪽 포인터 최대값이 큰 경우, 오른쪽 빗물 구하기 & 오른쪽 이동 예시를 통한 로직 순서 4. 문제 풀이 4-1. ..
-
[Python] 백준 16234 인구 이동알고리즘/문제풀이 2021. 8. 7. 18:38
1. 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 문제 요약 인접한 나라에 인구 차이가 L 이상, R이하면 국경선을 연다. 연합을 이룬 나라 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 3. 아이디어 정리 인구 이동이 없을 때까지 반복 모든 곳을 bfs로 방문하여 연합 진행 인접 국가를 탐색하면서 인구 차이 l명 이상, r명 이하인 경우 연합 진행 연합 국가 간 인구수는 (연합의 인..
-
[Python] 백준 18513 샘터알고리즘/문제풀이 2021. 7. 31. 18:35
1. 문제 링크 https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 2. 문제 요약 모든 집에 대한 불행도의 합의 최솟값 구하기 3. 아이디어 정리 샘터를 기준으로 불행도를 늘려주면서 bfs를 진행한다. 샘터를 기준으로 시작하기 위해 큐에 넣어준다. -1, + 1 위치 방향으로 bfs 진행 해당 집 위치를 큐에 넣기 - (집 위치, 현재 불행도 + 1) 4. 문제 풀이 4-1. 내 풀이 import sys from c..
-
[Python] 백준 10159 저울알고리즘/문제풀이 2021. 7. 31. 18:31
1. 문제 링크 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 문제 요약 비교 결과를 알 수 없는 물건의 개수 구하기 3. 아이디어 정리 플로이드와샬을 이용해 모든 노드에서 다른 노드 경로 구하기 a > b 가는 경로가 없는 경우(비교 결과를 알 수 없는 경우), count + 1 해주기 플로이드와샬 개념 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 2차원..
-
[Python] 백준 14466 소가 길을 건너간 이유 6알고리즘/문제풀이 2021. 7. 24. 19:32
1. 문제 링크 14466번: 소가 길을 건너간 이유 6 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 2. 문제 요약 길을 이용해야 하는 소들 쌍을 구하는 문제 예제 문제를 그려보면 아래와 같다. 소의 위치와 길의 위치가 주어지고, 두 소가 쌍을 지어 서로 길 없이 만날 수 있는지 확인을 해야 한다. 3. 아이디어 정리 소를 한 마리씩 돌려주면서(소 1) 정해진 길 없이 길을 건널 때 방문 여부를 모두 체크 ⇒ bfs 1에서 구한 소 1의 방문 여부 결과에서 소 2..
-
[Python] Programmers 행렬 테두리 회전하기알고리즘/문제풀이 2021. 7. 24. 19:24
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 2. 문제 요약 해당 위치를 시계 방향 회전한다. 회전에 의해 바뀐 숫자 중 가장 작은 숫자를 배열에 담아 리턴한다. 3. 아이디어 정리 시계 방향으로 회전하기 아래 그림과 같은 로직으로 진행된다. 왼쪽 > 오른쪽, 위 > 아래, 오른쪽 > 왼쪽, 아래 > 위 순서로 swap 하면서 진행한다. 회전한 숫자 중 최소값 찾기 4. ..
-
[Python] 백준 16236 아기 상어알고리즘/문제풀이 2021. 7. 24. 19:20
1. 문제 링크 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 문제 요약 아기 상어가 물고기를 먹으러 가는데 걸리는 최단 거리 구하기 3. 아이디어 정리 bfs로 현재 상어 위치에서 갈 수 있는 최단 거리를 찾는다. ⇒ bfs 예외처리 필요: 큰 상어는 못 지나간다. 1 결과를 이용하여 가장 가까운 물고기 위치를 얻는다. 예외 처리: 아기 상어보다 작은 물고기만 먹을 수 있다. 2에서 진행한 결과가 있는 경우 아기 상어 위치와 크..