본문 바로가기
반응형

파이썬 알고리즘14

[Python] 백준 11659번 - 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 혼자 힘으로 풀었는가? : X 알고리즘 유형 - 누적 합 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. .. 2022. 11. 13.
[Python] 백준 2231번 - 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 코드 n = input() min_m = int(n)-len(n)*9 check = 0 if.. 2022. 9. 20.
[Python][이코테] 삽입 정렬 삽입 정렬 삽입 정렬은 말 그대로 '삽입' 하여 정렬하는 것이다. 예를 들어 0~9까지 숫자를 오름차순 하고 싶은데 앞의 '선택 정렬'은 가장 작은 숫자를 '찾아서' 순서대로 맞춘다. 하지만 삽입 정렬은 일부러 찾는 것이 아닌 앞 인덱스와 비교하여 현재 인덱스 값 보다 앞 인덱스 값이 크면 '선택'하여 앞으로 보내는 것이다. 삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(.. 2022. 8. 31.
[Python][이코테] 선택 정렬 선택정렬은 말 그대로 '선택해서 정렬한다' 라고 할 수 있다. 예를들어 7 5 9 0 3 1 6 2 4 8 이라는 숫자의 모음이 있다. 이를 오름차순으로 정렬하고 싶을때 파이썬에서는 단순히 sort()를 사용하면 해결된다. 하지만 그래도 우리는 알고리즘을 공부하는 사람으로서 메서드에 의존할 것이 아닌 직접 코드로 구현할 줄 알아야한다. 선택 정렬의 알고리즘은 단순하다. 오름차순의 경우 '가장 작은 숫자를 찾아서 맨 앞에 두고, 그 다음 숫자를 찾아서 그 다음에 두고...' 를 반복한다. 7 5 9 0 3 1 6 2 4 8 에서 0 5 9 7 3 1 6 2 4 8 0을 찾아 7과 바꾸고 0 1 9 7 3 5 6 2 4 8 그 다음 1을 찾아 2번째 자리인 5와 바꾸는 식으로 가장 작은 숫자를 하나씩 찾아서.. 2022. 8. 17.
반응형

티스토리툴바