백준 알고리즘 - 순열 사이클 (10451) [Python]

문제 www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제 상황 - 주어진 순열이 몇개의 사이클을 이루고 있는지 개수를 구하는 문제이다. 해결 전략 - dfs를 통해 visited를 갱신하며 새로운 visited를 찾을 때 cnt를 갱신해준다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 from sys import stdin, setrecursion..
알고리즘 학습/백준 알고리즘 2020. 10. 6. 21:25
Codility - Distinct [Python]

문제 app.codility.com/demo/results/trainingKZ7PTU-ND7/ Test results - Codility Write a function def solution(A) that, given an array A consisting of N integers, returns the number of distinct values in array A. For example, given array A consisting of six elements such that: A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1 the f app.codility.com 문제 상황 - 서로 다른 숫자의 종류 찾기 해결 전략 - set을 사용하면 쉽게 해결..
알고리즘 학습/Codility 2020. 9. 27. 15:06
Codility - PassingCars [Python]

문제 app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/ PassingCars coding task - Learn to Code - Codility Count the number of passing cars on the road. app.codility.com 문제 상황 - 배열 A는 i번째에서 출발하는 차들의 이동 방향을 알려주는 배열이다. 즉, A[2] = 0 이면 2에서 출발하여 동쪽으로 이동하는 차라는 의미가 된다. 문제의 조건에 없지만 출발 시간은 동시라고 설정하고, 추월은 없다고 가정해야 문제가 성립한다. 해결 전략 1 - 결과적으로 1의 개수를 구하는 문제인데 구분점은 0이 된다. 즉, 어떤 서쪽으로 가는 차가 나왔을 때, 이 ..
알고리즘 학습/Codility 2020. 9. 27. 14:39
Codility - MinAvgTwoSlice [Python]

문제 app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/ MinAvgTwoSlice coding task - Learn to Code - Codility Find the minimal average of any slice containing at least two elements. app.codility.com 문제 상황 - 주어진 리스트를 순회하며 부분 집합의 평균 중 최소가 되는 경우의 시작 인덱스를 출력한다. 해결 전략 - 수학적 지식이 필요한 문제이다. 어떤 두 수의 평균은 항상 작은 수보다 크고 큰 수보다 작다. 즉, 서로 다른 두 수 a, b(a
알고리즘 학습/Codility 2020. 9. 27. 13:52
백준 알고리즘 - 제곱수의 합 (1699) [Python]

문제 www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 상황 - 입력받은 정수 N을 자연수의 제곱수의 합으로 표현할 때 최소 항의 개수를 출력한다. 해결 전략 - 처음엔 brute force식으로 생각했지만 이렇게는 해결 불가능하다. N보다 작은 최대의 제곱수를 제거하며 계산하려고 햇지만 반례가 생길 수 있다. N을 만드는 방법은 결국 부분적으로 쪼갤 수 있는데 이 쪼개는 기준이 중요하다. 코드 1 2 3 4 5 6..
알고리즘 학습/백준 알고리즘 2020. 9. 21. 17:32
백준 알고리즘 - 연속합 (1912) [Python]

문제 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 상황 - 주어진 수열에서 합이 가장 큰 연속 부분 수열의 합을 구하는 문제이다. 해결 전략 1 - 범위가 100,000이므로 O(N^2)는 100억으로 속도 이슈가 발생하여 O(N) 혹은 O(NlogN)의 범위 안에서 작동하여야 한다. - cache를 어떻게 정의하느냐가 문제의 포인트이다. - 0부터 i 사이의 구간에서 i로 끝나는 연속 부분합 중 최대의 값을 저장한다. 코드 1 2 3 4 5 6 7 8 9 1..
알고리즘 학습/백준 알고리즘 2020. 9. 21. 16:22
백준 알고리즘 - 가장 긴 바이토닉 부분 수열 (11054) [Python]

문제 www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 상황 - 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. - 주어진 수열에서 길이가 최대가 되는 바이토닉 부분 수열을 찾는다. 해결 전략 - LIS가 양쪽으로 있는 문제이다. - 처음에는 기분 인덱스 i를 옮겨가며 양쪽에서 LIS를 계산해 답을 도출하려고 하였다. 하지만 이렇게 되면 i를 움직이는 ..
알고리즘 학습/백준 알고리즘 2020. 9. 21. 14:56
백준 알고리즘 - 포도주 시식 (2156) [Python]

문제 www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 상황 - 포도주를 최대로 마실 수 있는 상황을 정해 그 최대값을 출력한다. 해결 전략 - i번째 와인을 마시는 경우는 2가지가 있다. i-1번째 와인도 마시되 i-2번째는 안마신 상태일 경우, 혹은 i-2번째까지의 최대값을 구하고 i번째 와인까지 마시는 경우이다. 코드 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 ..
알고리즘 학습/백준 알고리즘 2020. 9. 20. 23:10
1 ··· 8 9 10 11 12 13 14 ··· 22