[파이썬] 백준 24051 알고리즘 수업 삽입 정렬 1
백준 24051 알고리즘 수업 - 삽입정렬 1☞ 백준 사이트 : https://www.acmicpc.net/problem/24051삽입정렬 이란주어진 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,자신의 위치를 찾아 삽입하는 정렬이다.선택정렬이나 버블정렬과 같은 알고리즘에 비해 빠르며, 안정적인 정렬 알고리즘이다.삽입정렬 풀이 순서[4, 5, 1, 3, 2]을 오름차순 정렬로 변경하는 경우[4, 5, 1, 3, 2]2번 index 1을 0번 index부터 비교.4 보다 작아 0번 index에 insert나머지 shift[1, 4, 5, 3, 2] 3번 index 3과 4 비교 insert나머지 shift[1, 3, 4, 5, 2] 4번 index 2와 3 비교 insert나머지..
2024. 7. 12.
[파이썬] 백준 23969 알고리즘 수업 버블 정렬 2
백준 23969 알고리즘 수업 - 버블 정렬 2☞ 백준 사이트: https://www.acmicpc.net/problem/23969버블정렬 로직배열의 두 수(a, b)를 비교하면서 정렬시킴. 이를 반복▷ [7, 2, 0, 1, 5, 6, 4] 정렬 예시[7, 2, 0, 1, 5, 6, 4] 0번 index 7,2 비교 swap[2, 7, 0, 1, 5, 6, 4] 1번 index 7,0 비교 swap[2, 0, 7, 1, 5, 6, 4] 2번 index 7,1 비교 swap[2, 0, 1, 7, 5, 6, 4] 3번 index 7,5 비교 swap[2, 0, 1, 5, 7, 6, 4] 4번 index 7,6 비교 swap[2, 0, 1, 5, 6, 7, 4] 5번 index 7,4 비교 swap[2, 0..
2024. 7. 3.
[파이썬] 백준 23968 알고리즘 수업 버블 정렬 1
백준 23968 알고리즘 수업 - 버블 정렬 1 문제 풀이☞ 백준 사이트 : https://www.acmicpc.net/problem/23968 버블정렬이란배열의 두 수(a, b)를 선택한 뒤, 두 수를 비교하여 정렬이 필요하면 swap, 아니면 pass 한다.위 작업을 계속 반복하는 것이 버블정렬이다.시간복잡도 O(n2)로 상당히 느린 반면, 코드가 단순하기 때문에 자주 사용된다.▶ 오름차순 정렬이면 a ▶ 내림차순 정렬이면 a > b 판단하여 정렬 [ 4, 6, 5, 1, 3, 2] 정렬 대상 리스트인 경우 정렬 순서,[ 4, 6, 5, 1, 3, 2] 4,6 은 정렬, 6,5는 미정렬 → 1번 index 6, 5 swap[ 4, 5, 6, 1, 3, 2] 2번 index 6, 1 swap[ 4, 5..
2024. 7. 1.
[파이썬] 백준 23899 알고리즘 수업 선택 정렬 5
백준 23899 알고리즘 수업 - 선택 정렬 5 문제 풀이☞ 백준 사이트 : https://www.acmicpc.net/problem/23899 선택정렬 로직주어진 리스트 값 중에 최대값을 찾는다.그 값을 맨 뒤에 위치한 값과 swap 한다.위 작업을 반복한다.[3, 1, 2, 5, 4][3, 1, 2, 5, 4] 최대값 5, 4번 index와 swap[3, 1, 2, 4, 5] 최대값 4, 3번 index에 있으므로 pass[3, 1, 2, 4, 5] 최대값 3, 2번 index와 swap[2, 1, 3, 4, 5] 최대값 2, 1번 index와 swap[1, 2, 3, 4, 5] 정렬 완성▶ 선택정렬의 정의는 이전 글 참고 [파이썬] 백준 23881 알고리즘 수업 선택 정렬1백준 23881 알고리즘 ..
2024. 6. 28.
[파이썬] 백준 23881 알고리즘 수업 선택 정렬1
백준 23881 알고리즘 수업 - 선택 정렬 1 문제풀이선택 정렬이란주어진 리스트 값 중에 최소값을 찾는다.그 값을 맨 앞에 위치한 값과 swap 한다.위 작업을 반복한다.[3, 1, 2, 5, 4] 선택 정렬 순서[3, 1, 2, 5, 4] → 최소값 1, 0번 index와 swap[1, 3, 2, 5, 4] → 최소값 2, 1번 index와 swap[1, 2, 3, 5, 4] → 최소값 3, 2번 index에 있으므로 pass[1, 2, 3, 5, 4] → 최소값 4, 3번 index와 swap[1, 2, 3, 4, 5] → 정렬 완성백준 23881 문제에 있는 선택정렬 의사코드는 최대값에서 거꾸로 찾아가는 코드라서 아래와 같다.주어진 리스트 값 중에 최대값을 찾는다.그 값을 맨 뒤에 위치한 값과 s..
2024. 6. 26.
[파이썬] 백준 2309 일곱 난쟁이 (조합 combination)
백준 2309 일곱 난쟁이 문제 풀이https://www.acmicpc.net/problem/2309조합이란서로 다른 n개의 원소에서 (단, 0혹은 그 결과를 조합(combination)이라고 한다. ▶ 예시A, B, C 가 있을 때 2명으로 선택되는 가짓수는 얼마나 될까?(A, B), (A, C), (B, C) 로 총 3가지이고 이를 조합(combination)이라 한다. 여기서 중복을 허용하는 것은 순열(permutations)이다. 순열인 경우 총 6가지 가짓수가 나온다.('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B') ☞ 출처 조합combination / 組 合 서로 다른 개의 원소에서 (단, )개를 중복없이, 순서를 고..
2024. 6. 21.
[파이썬] 백준 1929 소수 구하기, 소수 판별법
백준 1929 문제풀이https://www.acmicpc.net/problem/1929풀이소수란1과 자기 자신으로밖에 나누어 떨어지지 않고, 자기 자신의 곱셈의 역수가 없는 수소수 예시101, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 2,3,5,7알고리즘어떤 수 N 이하의 수로 N을 나눠서 한 번이라도 나누어 떨어지면 합성수, 아니면 소수여기서 N 이하는 N의 양의 제곱근 이하의 수로 판별할 수 있는 것이 key point→ math 모듈의 sqrt() 함수 활용아래와 같이 주어진 입력값 기반의 반복문으로 풀면 시간초과 발생import sysvar = sys.stdin.readline().rstrip().split(" ")rtn = ""for i in range(int(var[0]), int(..
2024. 6. 17.
[파이썬] 백준 2609 최대공약수, 최소공배수
백준 2609 문제 풀이https://www.acmicpc.net/problem/2609풀이최대공약수와 최소공배수는 파이썬의 math 모듈의 gcd(), lcm() 함수로 구할 수 있다. 최대공약수란0이 아닌 두 정수 n과 m이 서로 공통으로 가지고 있는 약수 중 가장 큰 수를 말한다.약수란어떤 수를 나누어 떨어지게 하는 수6 은 1,2,3,6 이 약수두 수를 곱해서 어떤 수를 나오면 그 두 수가 약수최대 공약수 예시 : 12와 20인 경우12 : 1, 12, 2, 6, 3, 4 정렬하면 1, 2, 3, 4, 6, 1220 : 1, 20, 2, 10, 4, 5 정렬하면 1, 2, 4, 5, 10, 20같은 약수중에 제일 큰 것은 4. 최대공약수는 4☞ 참고 사이트 최대공약수 - 위키백과, 우리 모두의 백..
2024. 6. 16.