본문 바로가기

코딩테스트7

[분할정복] 백준 2447 - 파이썬 의식의 흐름 알고리즘은 문제를 보고 내가 첨에 든 생각들을 끄적인거라 틀린 알고리즘임. 답만 알고 싶다면 최종 알고리즘이나 정답코드만 보면 된다.  백준 2447.https://www.acmicpc.net/problem/2447의식의 흐름 알고리즘쉬울거라 생각하고 도전했는데 이게 엔터가 들어가면서부터 뭔가 꼬인다. 진짜 재귀 문제 풀수록 자괴감 들어............................................머릿속에서 대충 돌아는 가는데 그걸 재귀로 구현하는게 정말 쉽지 않다.특히나 이번문제같은경우는 엔터값도 들어가고 하다보니 더 어려웠음..원래 생각한 방식은 1 ->3->9로 증가하면서 직전단계 패턴을 그대로 복사해서 중간만 비우고 다른칸에다 채우는건데 그렇게 하면 엔터가 자꾸 값으로.. 2024. 10. 26.
정렬 알고리즘 - 파이썬 (선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬, 계수정렬) 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.

티스토리툴바