Codility - NumberOfDiscIntersections (Sorting) [Python]

문제 app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/ NumberOfDiscIntersections coding task - Learn to Code - Codility Compute the number of intersections in a sequence of discs. app.codility.com 문제 상황 - 주어진 배열의 인덱스는 각 원의 중심점을 의미한다. 즉, 인덱스 J 번째 원은 (J,0)을 중심으로 하는 원이다. 이 때 다른 원과 교차하는 원들의 쌍의 개수를 구한다. 문제의 조건에 안써있지만, 순서의 개념이 없어 1번 원, 3번 원의 쌍과 3번 원, 1번 원의 쌍은 같은 것으로 취급한다. 해결 전..
알고리즘 학습/Codility 2020. 11. 4. 16:04
백준 알고리즘 - 리모컨 (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
백준 알고리즘 - 배열 합치기 (11728) [Python]

문제 www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거�� www.acmicpc.net 문제 상황 - 정렬된 두 배열을 하나로 합쳐 정렬된 결과물을 출력한다. 해결 전략 1. 인덱스를 하나씩 탐색하며 더 작은 쪽을 결과물에 담으면 된다.(Merge)의 개념 2. Python의 내장 sort(O(NlogN))을 이용한다. 코드 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 ..
알고리즘 학습/백준 알고리즘 2020. 10. 16. 10:50
1 ··· 6 7 8 9 10 11 12 ··· 22