알고리즘

[백준][Python] 10989번: 수 정렬하기 3

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. >> 수 정렬하기 1, 2에서 사용한 다른 값들과 비교하는 비교정렬과는 다르게 메모리 제한이 8MB으로 배열을 사용하는 계수정렬(counting)을 사용해야한다. 계수정렬: 비교가 한번도 이루어지지 않고 정렬하는 알고리즘, 주어진 입력값들의 크기를 기준으로 수를 배열에 저장하여 정렬, 여기서 리스트의 인덱스를 이용 O(N) or O(N+k) 의 시간복잡도, 가장 큰 수의..

[알고리즘] 재귀함수

재귀적으로 푼다는 것은 같은 형태의 더 작은 문제(부분문제)를 풀어서 나온 답을 이용해서 기존문제를 푸는 것 5! = 1*2*3*4*5 = 120 >> 4! 는 5!의 부분문제 0!은 1이다. 재귀적으로 해결할 필요 X n=0 >> n! = 1 n>0 일때 >> n! = (n-1)! * n 재귀함수는 콜스택은 한계있음 파이썬은 1000까지허용 반복문하고 재귀함수 중 더 깔끔한 쪽이 효율 재귀함수 콜스택이 쌓이는거 문제될 경우 반복문사용

[알고리즘] 정렬

리스트의 원소들을 특정 순서로 정리하는 것 list = [3, 2, 4, 5, 1, 6] 선택 정렬 각 위치에 어떤 값이 들어갈지 찾음 가장 작은 값을 찾아서 0, 그 다음 작은 값 1,,,, 이런 순으로 작은 값 먼저 인덱스 지정 list에서 가장 작은 값을 찾는다. list에서는 5번 인덱스가 가장 작다. 첫번째 인덱스 0과 자리를 바꾸고 후 다음 비교에선 0번 인덱스는 제외해줌.. 가장 작은 값을 찾고 비교한 인덱스 중 첫 인덱스랑 값 바꿈 그러면 첫번째인덱스에 가장 작은 값이 들어가있음 가장 작은 값이 첫번째 인덱스에 있기 때문에 다음 비교에선 필요없으니 제외하고 다시 비교... 반복 삽입 정렬 각 값이 어떤 위치에 들어갈지 찾음 새로운 값이 들어왔을때 기존에 정렬된 값중 어느 위치에 넣을지 정하..

[알고리즘] 탐색

원하는 값 얻기위해 탐색한다. [1,2,3,4,5,6,7,8,9,10] 선형 탐색 알고리즘 하나하나 보는 것을 선형탐색이라고함. 이진 탐색 알고리즘 중간값을 찾아서 찾으려는 값이 왼쪽인지 오른쪽인지 확인 후 찾으려는 값이 오른쪽에 있다면 왼쪽에 있는 값 제외, 오른쪽의 값만 본다. 다시 오른쪽의 값을 가지고 위와 같이 중간값을 찾은 후 찾으려는 값이 왼쪽, 오른쪽인지 확인을 반복하면 원하는 값을 찾을 수 있다. 반씩 제외하면서 찾는 방식이다. def binary_search(element, some_list): start_index = 0 end_index = len(some_list) - 1 while start_index element: end_index = midpoint - 1 else: star..

[Level1] 이상한 문자 만들기

programmers.co.kr/learn/courses/30/lessons/12930 코딩테스트 연습 - 이상한 문자 만들기 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 programmers.co.kr 내 풀이 def solution(s): a = '' cnt = 0 for i in range(len(s)): if s[i] == ' ': cnt = 0 a += s[i] elif cnt % 2 == 0: cnt += 1 a += s[i].upper() else: cnt += 1 a += s[i].lower() return a 처음엔 %2 == 0일때 대문자로 바꾸..

[Level1] 제일 작은 수 제거하기

programmers.co.kr/learn/courses/30/lessons/12935 코딩테스트 연습 - 제일 작은 수 제거하기 정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1 programmers.co.kr 내 풀이 def solution(arr): if len(arr) < 2: return [-1] arr.remove(min(arr)) return arr remove를 return 줄에 해버리면 none으로 뜸.