모카의 촉촉한 개발 로그

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되어있지 않은 리스트에서 데이터를 찾아야 할때 사용 시간복잡도는 O(N)이다. 이진 탐색 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 시작점,끝점,중간점으로 범위를 나누어 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는다 STEP 1 시작점과 끝점을 확인한 다음 둘 사이 중간점을 시작점과 끝점을 더한 값을 2로 나눈 값으로 한다. 다음으로 중간점[4]의 데이터와 8과 찾으려는 데이터 4를 비교한다. 중간점의 데이터 8이 더 크므로 중간저 이후의 값은 확인 할 필요가 없다. 그래서 끝점을 [4]의 이전인 [3]으로 변경 STEP 2 1과 ..

N개의 원소를 가진 서로다른 배열 A,B가 있을 때 K번 교환하여 A의 원소의 총합을 최대로 하라. 입력 예시) 5 3 1 2 5 4 3 5 5 6 6 5 출력 예시) 26 나의코드 n,k=map(int,input().split()) arrA=list(map(int,input().split())) arrB=list(map(int,input().split())) arrA.sort() arrB.sort(reverse=True) for i in range(k): arrA[i],arrB[i]=arrB[i],arrA[i] print(sum(arrA)) 각각의 배열을 입력 받은뒤 A배열은 오른차순으로 B배열은 내림차순으로 정렬한다. 그 후 k번 만큼 0번 인덱스 부터 스와프 해준다. 정답 코드 n, k = map(..

N명의 학생정보가 이름과 성적으로 입력이 될때 성적이 낮은 순서대로 학생의 이름을 출력하라. 입력예시) 2 홍길동 95 이순신 77 출력 예시) 이순신 홍길동 나의 코드 N=int(input()) arr=[] for i in range(N): arr.append(list(map(str,input().split()))) arr[i][1]=int(arr[i][1]) arr.sort(key=lambda x:x[1]) for i in range(N): print(arr[i][0], end=' ') 빈 배열에 str타입의 리스트로 입력을 받은 값들을 추가 하며 1번 인덱스인 성적을 다시 정수화 한다. 그 후 sort 함수의 key에 람다함수를 적용해 1번 인덱스를 기준으로 정렬한다. 정답코드 # N 입력 받기 n..

수열을 내림차순으로 정렬하는 프로그램을 만드시오. 입력 예시) 3 15 27 12 출력예시 ) 27 15 12 나의 코드 n=int(input()) arr=[] for _ in range(n): arr.append(int(input())) arr.sort(reverse=True) print(arr) 처음 수열의 크기를 입력 받은 뒤 그 크기 만큼 반복문을 돌며 리스트에 추가한다. 그후 한번에 sort함수로 reverse옵션으로 정렬을 한다. 정답 코드 # N 입력 받기 n = int(input()) # N개의 정수를 입력 받아 리스트에 저장 array = [] for i in range(n): array.append(int(input())) # 파이썬 정렬 라이브러리를 이용하여 내림차순 정렬 수행 arr..

계수정렬 - 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다 - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다 - 모든 데이터가 양의 정수인 상황을 가정했을때, 데이터의 개수가 N개고 데이터 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다 - 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능하다 - 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문에, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬을 사용할 수 없다 - 앞서 다룬 알고리즘과 달리 직접 데이터의 값을 비교한 뒤 위치를 변경하며 정렬하는 비교 기반의 정렬 알고리즘이 아니다 - 계..

퀵정렬 - 병합 알고리즘과 더불어 대부분의 라이브러리의 근간이 되는 가장 많이 사용되는 알고리즘이다. - 기준(피벗(Pivot))을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다 - 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식(리스트의 첫 데이터를 피벗으로 설정)을 기준으로 퀵 정렬을 이해해 보자. 피벗을 설정한 후 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환한다 ==> 위 과정을 반복하면 피벗에 대하여 정렬이 수행 이해의 편의를 위해 크게 3개의 파트로 나..

삽입정렬 - 처리되지 않은 특정한 데이터를 하나씩 골라 적절한 위치에 삽입 - 선택 정렬보다 실행 시간이 조금 더 효율적이다 - 특히, 데이터가 정렬 되어 있을 때 더욱 효과적이다. (선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교한다) - 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞의 데이터들은 이미 정렬되어 있다고 가정한다 - 정렬되어 있는 앞쪽의 데이터 리스트에서 적절한 위치를 찾은 후, 그 위치에 삽입 첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에 두번째 데이터부터 시작 STEP 0) 5가 들어갈 수 있는 위치는 앞 쪽의 데이터인 7의 왼쪽이나 오른쪽, 총 2가지 경우만 존재한다. 우리는 카드를 오름차순으로 정렬할 것이기 때문에 7의 왼쪽에 삽입한다 ST..

연속된데이터를기준에따라서정렬하기위한알고리즘 정렬 이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는것이다. 정렬을 통해 이진탐색이 가능해진다. 수많은 정렬 알고리즘이 있지만 선택정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 정도만 학습하자. 면접에도 자주 나오는 알고리즘이니 빠삭하게 알아 두고 가자 ! 선택정렬 - 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞의 뎅터와 바꾸는 것을 반복 - '가장 작은것을 선택' 한다는 점에서 선택 정렬이라고 불린다. STEP 0) 초기단계에서는모든데이터가정렬되어있지않으므로, 전체중에서가장작은데이터를선택한다. 따라서 0 을선택해 맨 앞에 있는 데이터7과 바꾼다. STEP 1) 이제 정렬된 첫번쨰 데이터는 제외하고 그 뒤의 데이터 중에서 가장 작은 데이터인 1..

미로탈출 N x M 공간에 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 이 때 동빈은 (1,1) 즉, 왼쪽 상단에 있을 때 (N,M)즉, 오른쪽 최하단에 있는 미로로 최단 경로로 갈 때 시작 칸과 마지막 칸을 포함하여 총 몇칸을 지나는지 출력 하시오. 입력 예시) 5 6 101010 111111 000001 111111 111111 출력예시) 10 나의 코드 from collections import deque def BFS(x,y,arr): print(n,m) dq=deque() dq.append([0,0]) dx=[-1,0,1,0] dy=[0,1,0,-1] L=0 while True: D=len(dq) for _ in range(D): x,y=dq.popleft() if x==n..

N x M 크기의 얼음 틀이 있다. 0은 구멍이 뚫려있는 부분, 1은 칸막이가 존재하는 부분이다. 구멍이 뚫려 있는 부분끼리 상하좌우로 붙어 있는경우 서로 연결된 것으로 간주한다. 이때 연결된 한 덩어리를 아이스크림 1개라고 할때 몇개의 아이스크림이 생성 되는가? 입력 예시) 4 5 00110 00011 11111 00000 출력 예시) 3 나의 코드 def DFS(x,y,arr): arr[x][y]=1 dx=[-1,0,1,0] dy=[0,1,0,-1] for k in range(4): nx=x+dx[k] ny=y+dy[k] if 0