백준
-
[Python] 백준 1038 감소하는 수알고리즘/문제풀이 2021. 9. 4. 15:29
1. 문제 링크 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 2. 문제 요약 n번째 감소하는 수를 찾는 문제이다. 9876543210 이후로 감소하는 수는 없기 때문에 그 이후 수는 -1을 출력한다. 3. 아이디어 정리 0~9로 1개~10개까지 모든 조합을 구한다. 오름차순을 하여 정렬을 진행한다. 해당 수를 출력하거나 인덱스 에러가 나면 해당 순서 감소하는 수가 없는 것이라 -1 출력한다. 4. 문제 풀이 4-1. 내 풀이 ..
-
[Python] 백준 11659 구간 합 구하기 4알고리즘/문제풀이 2021. 9. 4. 15:26
1. 문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 2. 문제 요약 i번째 수부터 j번째 수까지 합을 구한다. = 구간합 3. 아이디어 정리 현재 수 + 앞에 존재하는 수들의 합을 구한다. 1에서 구한 값 j에서 i - 1을 빼면 구간에 대한 합을 구할 수 있다. 4. 문제 풀이 4-1. 내 풀이 import sys # 수의 개수, 합을 구해야하는 횟수 n, m = map(int, sys.stdin.readl..
-
[Python] 백준 16235 나무 재테크알고리즘/문제풀이 2021. 8. 20. 22:33
1. 문제 링크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 2. 문제 요약 4계절에 맞게 구현을 하여 k 년이 지난 후 살아있는 나무 개수를 출력한다. 3. 아이디어 정리 나무 나이를 저장할 그래프를 새로 생성한다. - 3차원으로 저장 k 년 동안 4계절을 반복 진행한다. 봄: 자신의 나이만큼 양분 먹고 나이 + 1 한 칸에 여러 개 나무가 있다면 어린나무부터 여름: 죽은 나무 = (나이 // 2)로 현재 양분에 넣어준다...
-
[Python] 백준 21278 호석이 두 마리 치킨알고리즘/문제풀이 2021. 8. 20. 22:29
1. 문제 링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 2. 문제 요약 모든 건물에서 가장 가까운 치킨집 2개를 고른다. 3. 아이디어 정리 모든 정점에서 모든 정점으로 가는 최소 거리 구하기 ⇒ 플로이드 와샬 2개의 건물을 선택하여(예상 치킨집) 모든 집을 방문해서 걸리는 거리를 측정 현재까지 최소 거리이면 결과에 저장 4. 문제 풀이 4-1. 내 풀이 import sys n, m = map(int, s..
-
[Python] 백준 1956 운동알고리즘/문제풀이 2021. 8. 14. 20:17
1. 문제 링크 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 2. 문제 요약 최소 사이클의 도로 길이의 합을 출력한다. 3. 아이디어 정리 모든 정점에서 모든 정점으로 가는 최소 거리 구하기 ⇒ 플로이드 와샬 자기 자신 -> 자기 자신 마을로 돌아오는 거리 중 최솟값 구하기 참고 - 플로이드와샬 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜 점화식 각 단계마다 특정한 노드 k..
-
[Python] 백준 17609 회문알고리즘/문제풀이 2021. 8. 14. 17:45
1. 문제 링크 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 2. 문제 요약 회문: 0 (앞뒤 동일) 유사회문: 1 (한 문자 삭제 시 앞뒤 동일) 둘 다 해당 안됨: 2 3. 아이디어 정리 투 포인터를 이용해서 회문을 검사한다. left right 문자가 동일한 경우: left + 1, right + 1 left right 다른 경우: 한 문자열 제거 후 회문 확인 오른쪽 문자열 제거한 경우 제거 후 회문이 되는지 확인 왼쪽 문자열 제거한 경우 제거 후 회문이되는지 확..
-
[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. ..