본문 바로가기
반응형

전체 글330

[파이썬] 정렬 알고리즘 - 선택 정렬 선택 정렬(Selection Sort) 정렬과정 리스트 내의 최소값을 찾음 그 값을 리스트의 맨 앞에 위치한 값과 교환 맨 처음 위치를 제외한 나머지 값들을 대상으로 위 과정 반복 (시간 복잡도 O(n^2) Step 최솟값 7을 찾아 맨앞 35와 교환하고 다시 최소값을 찾음 다시 정렬 안된 리스트와 교환하고 위의 과정을 반복함 정렬되지 않은 마지막 원소가 가장 큰 값을 가지므로 정렬 완료 코드 구현 def selectionsort(arr) : n = len(arr) for i in range(n-1) : min_arr = i for j in range(i+1, n) : if arr[min_arr] > arr[j]: min_arr = j arr[i], arr[min_arr] = arr[min_arr], a.. 2023. 2. 12.
[파이썬] 자료찾기 알고리즘 - 검색 방법(순차 검색, 이진 검색) 검색 방법(Search) 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 순차 검색 (sequential search) 이진 검색 (binary search) 정렬되어 있지 않은 경우의 검색 과정 첫 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾음 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환 자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패 ex) [4, 9, 2, 7, 21] 에서 7을 검색하는경우 앞에서부터 체크 4≠7 → 9≠7 → 2≠7 ≠ 7 = 7 def search(a, key): x = 0 n = len(a) while x < n and a[x] != key : x += 1 if x 2023. 2. 12.
[파이썬] 부분집합을 구하는 방법 부분집합 구하는 방법 부분집합의 수 각 원소가 n개 일 때, 공집합을 포함한 부분집합의 수는 2^n개 ex) [1,2,3,4,5] —> 2^5 = 32개 각 원소가 부분 집합에 포함되었는지 확인하는 방법 arr = [1,2,3,4,5] for i in range(2) : arr[0] = i for j in range(2) : arr[1] = j for k in range(2) : arr[2] = k for l in range(2) : arr[3] = l for n in range(2) : arr[4] = n print(arr) 부분집합을 for문을 이용하는 방법(비트 연산자 활용) 비트연산자 & : 비트 단위로 and 연산 | : 비트 단위로 or 연산 >피트연산자의 비트 열을 오른쪽으로 이동 arr =.. 2023. 2. 12.
[백준 1874] 스택 수열 (python) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택 수열 문제 while을 잘 활용하면 쉽게 해결 할 수 있는 문제 100% 내 생각으로 풀었는가? → △ while문의 특징에 대해 캐치하는데 너무 오래걸려서 힌트 참고 내가 푼 코드 (정답) import sys N = int(sys.stdin.readline()) stack = [] start = 1 opera.. 2023. 2. 12.
[SWEA 9386] 연속한 1의 개수(python) https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXALDUIq97oDFASI SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 연속한 1의 갯수 문제 각 케이스에 대해 연속된 1의 갯수가 가장 많은걸 찾으면 되는 간단한 문제 100% 내 생각으로 풀었는가? → O 비교적 간단하게 해결한 문제이다. 내가 푼 정답 코드 T= int(input()) def max_case(n) : cnt = n[0] for i in range(len(n)) : if cnt < n[i] : cnt = n[i] return cnt f.. 2023. 2. 12.
[파이썬] 정렬 알고리즘 - 버블 정렬 & 카운팅 정렬 버블 정렬 특징 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지로 이동하는 정렬 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됨 (시간 복잡도 O(n^2)) 실제로 알고리즘 풀이에는 잘 쓸일 없음(시간 복잡도 때문) 정렬 과정 7, 6, 4 를 정렬한다고 해보자. Step 맨 앞의 7과 6의 자리를 서로 바꿔준다. 다시 반복해서 7과 4의 자리를 바꿔준다. (숫자가 더 많을 경우) 계속해서 반복해서 바꿔준다. 1번의 싸이클이 돌고 난 후 다시 처음부터 같은 작업을 반복한다 버블 정렬 코드 def Bubblesort(List): #정렬할 list, 원소 수 N for i in range(len(List)-1, 0.. 2023. 2. 12.
반응형

티스토리툴바