백준 알고리즘 - 소트인사이드 (1427번) [Python]

문제 www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 상황 - 10억 이하의 수를 입력받아 그 자리수를 내림차순으로 정렬한 결과를 반환한다. 해결 전략 - 입력받은 숫자를 str로 만들고 그 리스트를 역순 정렬하여 합치고 반환한다. 코드 1 2 from sys import stdin print(''.join(sorted(list(stdin.readline().strip()),reverse=True))) cs 해설 - 자리수가 아니라 범위가 10억 이하이므로 길이가 10자리 이하를 정렬하는 문제이다. 만약 자리수가 10억자리 이하였으면 cou..
알고리즘 학습/백준 알고리즘 2021. 1. 12. 15:45
백준 알고리즘 - 체스판 다시 칠하기 (Brute Force) [Python]

문제 www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 상황 - 체스판 색깔이 백, 흑이 반복되어야 하는데 8이상, 50이하 길이의 판이 주어질 때 최소의 색칠로 8 by 8 체스판을 만들 경우의 최소 색칠 수를 반환한다. 해결 전략 - 우선 시작 행, 시작 열을 입력 했을 때 8 by 8 판에 해야 할 색칠의 수를 반환하는 함수를 만들고, 판의 가장 왼쪽 가장 위의 지점을 이동시키며 모든 경우를 탐색한다. 코드 1 2 3 4 5 6 7 8 9 1..
알고리즘 학습/백준 알고리즘 2021. 1. 11. 22:46
백준 알고리즘 - 리모컨 (1107) [Python]

문제 www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 상황 - 리모컨으로 목표 채널에 도달하기 위해서 필요한 최소 이동 횟수를 출력한다. 해결 전략 - 문제 상황 그대로를 시뮬레이션하여 최소 이동 횟수를 비교한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 from sys import stdin input..
알고리즘 학습/백준 알고리즘 2020. 10. 22. 10:41
백준 알고리즘 - 날짜 계산 (1476) [Python]

문제 www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타�� www.acmicpc.net 문제 상황 - 15, 28, 19를 기준으로 숫자가 순회할 때, 주어진 숫자는 몇번째인지 연산한다. 해결 전략 - 숫자가 크지 않기 때문에 1부터 순회하며 15, 28, 19로 각각 나눈 나머지가 주어진 E, S, M과 같은지 비교하고, 같다면 출력한다. 코드 1 2 3 4 5 6 7 8 9 10 from sys import stdin input = stdin.readline E, S, M = map(int..
알고리즘 학습/백준 알고리즘 2020. 10. 21. 10:16
백준 알고리즘 - 병든 나이트 (1783) [Python]

문제 www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 상황 - 나이트가 이동하며 최대한 많은 지점을 방문할 방법을 고려한다. dfs를 통해 개수를 카운트할 수 있지만 문제의 분류가 탐욕법이고 가로와 세로의 범위가 2,000,000,000 이하이므로 다른 방법을 생각해보아야한다. 해결 전략 - 문제의 상황을 일일이 가정하고 범위를 정의해 상황에 맞춰 시뮬레이션한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 from sys import stdin..
알고리즘 학습/백준 알고리즘 2020. 10. 20. 11:41
백준 알고리즘 - 암호코드 (2011) [Python]

문제 www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 상황 - 숫자가 주어지고 대응되는 암호코드를 만들 때, 가능한 암호 코드의 수를 출력한다. 숫자가 커질 경우를 대비해 1,000,000으로 나눈 수를 출력한다. 암호로 변경이 불가능한 경우 0을 출력한다. 해결 전략 - 우선 암호로 변경 불가능한 경우는 크게 두가지이다. 숫자가 아닌 값이 입력되거나, 0이 들어가는데 10, 20처럼 처리 가능한 숫자가 아닌 00, 40 처럼 알파벳에 대응될 수 없는 경우가 존재하는 상..
알고리즘 학습/백준 알고리즘 2020. 10. 19. 18:04
백준 알고리즘 - 쿼드트리 (1992) [Python]

문제 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 문제 상황 - 0과 1로 이루어진 2차원 배열을 압축하며 압축이 불가능할 경우 4분할하여 작업을 반복한다. 해결 전략 - 재귀를 이용하여 주어진 조건을 분할정복한다. 요소가 전부 한가지로 되어있으면 괄호가 없이 해당 숫자를 출력하고 0과 1이 모두 존재하면 다시 4분할하며 작업을 반복한다. 이 때, 괄호를 넣어주어야 한다. 1. 모든 요소를 검사하며 0행 0열의 값을 기준으로 다른 값이 하나라..
알고리즘 학습/백준 알고리즘 2020. 10. 19. 11:01
백준 알고리즘 - 종이의 개수 (1780) [Python]

문제 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 상황 - 종이를 확인하여 종이가 하나의 숫자로만 되어있으면 그 종이는 더이상 자르지 않고, 다르다면 9분할해서 카운팅을 반복한다. 해결 전략 - BOJ의 Z 문제와 유사한 풀이로, 함수를 설정해 재귀하도록 한다. 주어진 조건을 만족하면 글로벌을 통해 카운트를 증가시켜주고, 아니면 스플릿을 반복한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..
알고리즘 학습/백준 알고리즘 2020. 10. 16. 11:39
1 2 3 4 5 6 7 8