백준
-
[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] 백준 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에서 진행한 결과가 있는 경우 아기 상어 위치와 크..
-
[Python] 백준 15961, 2531 회전 초밥알고리즘/문제풀이 2021. 7. 17. 21:27
1. 문제 링크 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmi..
-
[Python] 백준 3151 합이 0알고리즘/문제풀이 2021. 7. 17. 21:04
1. 문제 링크 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 2. 문제 요약 세 팀원 코딩 실력이 0이 되는 경우의 수 구한다. 3. 아이디어 정리 3명인데 투포인터를 진행해야 한다. -> 한 명씩 기준으로 잡고 그 안에서 투 포인터를 진행한다. 1. 합이 0이 되는 경우, left값과 right 값이 같은 경우 해당 범위를 더한다. ⇒ 0이되는 right 학생수 얻어서 더하기 left값과 right 값이 다른 경우 right에 해당되는 점수를 ..
-
[Python] 백준 15565 귀여운 라이언알고리즘/문제풀이 2021. 7. 17. 20:57
1. 문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 2. 문제 요약 k개 이상 라이언이 포함된 가장 작은 연속된 인형들의 집합 크기 구하기 ⇒ 투 포인터 3. 아이디어 정리 투 포인터를 이용해서 이동 k개의 라이언이 존재하는 구간에서 결과 저장 left + 1 k개 이하의 라이언이 존재하는 경우, right + 1 4. 문제 풀이 4-1. 내 풀이 import sys n, k = map(int, sys.stdin.readlin..