분류 전체보기
-
[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] Programmers 다단계 칫솔 판매카테고리 없음 2021. 7. 31. 18:32
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 2. 문제 요약 부모 노드에게 10% 수익을 배분하여 판매원들의 이익금을 구하는 문제 3. 아이디어 정리 판매자 별 부모에게 칫솔 수익을 나눠준다. 부모가 있는 경우 부모에게 수익 배분 & 자신의 수익에서 배분한 금액만큼 빼기 내 부모가 부모의 부모에게 수익 배분하기 위해 재귀 호출 부모가 없는 경우고 센터한테만 수익 배분하고 끝 4. 문제..
-
[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에서 진행한 결과가 있는 경우 아기 상어 위치와 크..