본문 바로가기

IT이야기/CODE PRACTICE12

정렬 알고리즘 - 파이썬 (선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬, 계수정렬) 1. 선택정렬제일 앞에서부터 작은 것 부터 채워서 정렬for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i]print(array)   2. 버블정렬인접한 두개끼리 비교하며 작은것을 앞으로 보내어 제일 뒤가 가장 큰 값으로 남게.그러고 다시 남은 배열끼리 비교 반복for i in range(len(array) - 1, 0, -1): # 정렬 범위 줄여 나가기 for j in range(i): if arr.. 2024. 10. 16.
[파이썬] 코딩테스트에서 사용되는 함수 기본기 - 탐색, 소수찾기, 소인수분해, k진수 등 DPDP(Dynamic Programming)botton-up : 보통 for문으로 풀며 밑에서부터 위로 문제해결 타고 올라감top-down : 보통 재귀함수로 풀며 위에서부터 아래로 부분문제로 쪼개지며 해결함 많은 경우의 수, 큰 숫자의 경우는 높은 확률로 DP를 사용해서 푸는 문제혹은 첫 경우의 수의 최댓값을 구한 후 한줄한줄 차근차근 누적 + 그 다음단계 경우의 수를 더해나가는 문제 ->어떤 규칙으로 최적화 값을 구할 수 있을지 점화식을 세울 수 있어야 함   정렬문제푸는방식 정렬문제는 딕셔너리, 리스트를, 내장함수(sort, sorted 등)를 잘 이용해서 풀어야함. 또한 시간제한과 메모리제한을 잘 확인해서 풀어야 함  정렬시간복잡도+계수정렬 O(N + 데이터 최대값)#INPUT1052314235.. 2024. 10. 15.
백준 3190 - 파이썬 힌트 및 풀이과정 백준 3190. https://www.acmicpc.net/problem/3190 이 문제를 처음 접했을 때 든 생각은 일단 보드판을 배열로 놓고, 사과의 위치도 1로 설정을 한다. 그리고 뱀 머리랑 꼬리랑 저장한 값을 가지고서..? FIFO인 deque로 풀어야할 것 같다. 였다. 문제1. 이제 머리와 꼬리를 tuple형태로 세트로 저장하는 하는 방식으로 생각을 해봤는데 너무 복잡해졌다. 문제2. 그리고 방향 전환 시 x,y좌표를 어떻게 변동시킬 지 잘 감이 안온다. 3190 문제풀이 힌트 문제1 힌트. 머리 꼬리를 tuple로 하는 것이 아니라 뱀의 머리-꼬리 위치를 보드판 위에 2나 -1과 같은 다른 형태의 숫자로 올린다. 문제2 힌트. 통상적인 좌우로 이동하는 문제를 풀 때 사용하는 [0, 1, .. 2024. 1. 17.
백준 17298 - 파이썬 힌트 및 풀이과정 백준 문제 중 자료구조 알고리즘의 골드단계 문제 위주로 뽑아서 풀어보고자 한다. 정답률은 45% 이하인 친구들로 랜덤 선택. 코테 푸는 수준은 여전히 허접이다. 백준 17298. https://www.acmicpc.net/problem/17298 문제 자체는 간단해보이는데 간단한 만큼 그 생각 그대로 풀어쓴다면 (이중포문) 이중 포문으로 돌아야 하다보니 최악의 경우의 수가 1,000,000 * 1,000,000 정도이다. 당연히 틀릴 걸 알았지만 일단 떠오른 대로 써보기라도 하자 해서 써본 코드다. 시간초과 틀린답 O(N^2) def num17298(): N = int(input()) arr = list(map(int, input().split())) arr.insert(0,0) res = [] for .. 2024. 1. 17.

티스토리툴바