꿈꾸는 개발자의 devLog

[부품 찾기] - N개의 부품이 있음 - 손님은 M개 종류의 부품을 대량 구매하겠다고 함 - 이때, 고객이 요청한 부품이 모두 있는지 확인하는 프로그램 작성 예시) - 가게의 부품이 총 5개 일 때 부품 번호가 다음과 같음 N = 5 [8, 3, 7, 9, 2] - 손님은 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같음 M = 3 [5,7,9] 총 입력 예시 5 8 3 7 9 2 3 5 7 9 - 각 부품이 존재하면 yes, 없으면 no 출 [코드] ## 앞의 코드에서 조금만 수정하면 됨 ## 재귀 함수로 작성하는 이진탐색 import sys def binary_search(ary, target, start, end): if start > end: return None ## 중간점 지정 m..

[순차 탐색] - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 (보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용) [이진 탐색] - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 - 데이터가 무작위일 때 사용 불가능 - 탐색 범위를 절반씩 좁혀가며 데이터 탐색 - 시작점, 끝점, 중간점 필요 - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교 1. 중간점이 실수 일때는 소수점 이하를 버림 - 예시에서 시작점 0, 끝점 9, 중간점이 원래 4.5이지만 소수점 이하 버려서 4 - 중간점에 위치한 값과 타겟값 비교후, 중간점이 더 크다면 중간점 이후의 값은 확인할 필요 없음 2. 시작점, 중간점, 끝점 변경 - 끝점을..

[계수 정렬 Count sorting] - 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 (사실 이 정렬 방법은 처음 본다....) - 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능 (예 : 0 이상 100 이하인 성적 데이터를 정렬할 때 효과적) - ** 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 함 만약, 가장 큰/작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화 --> 1을 더해주는 이유는 0 부터 1,000,000까지 해서 이기 때문 [예시] 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 - 현재 예..

[퀵 정렬] - 가장 많이 사용 되는 알고리즘 - 기준 설정 후, 큰 수와 작은 수 교환 --> 리스트를 반으로 나눔 - 여기서 말하는 기준: pivot * 호어 분할 방식 : 리스트에서 첫 번째 데이터를 피봇으로 선정 - 왼쪽에서부터 피봇보다 큰 데이터 찾고, 오른쪽에서부터 피봇보다 작은 데이터 찾음 - 큰 데이터와 작은 데이터의 위치 교환 - 위와 같이 찾는 값의 위치가 서로 엇갈린 경우, 작은 데이터와 피봇의 위치를 서로 변경- 위 그림과 같이 피봇의 위치를 변경하면 피봇을 기준으로 왼쪽에는 피봇보다 작은 데이터가, 오른쪽에는 피봇보다 큰 데이터만 위치하게 됨 - 각각의 리스트에서 같은 방식으로 개별적으로 정렬 진행 - 똑같이, 제일 왼쪽에 있는 값을 피봇으로 선정하여 위치 변경 시행 그렇다면 퀵 ..

정렬로 이진 탐색 가능 주로 나오는 정렬 : 선택, 삽입, 퀵, 계수 정렬 [선택 정렬] - 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 - 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복 - 처음 인덱스를 기준으로 그 뒤에 있는 데이터들이랑 비교 ary = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(ary)): min_idx = i ## 가장 작은 원소의 인덱스 for j in range(i+1, len(ary)): # 기준이 되는 인덱스 이후의 데이터들 if ary[j] < ary[min_idx]: min_idx = j ## 이렇게 해야 다음 행에서 정렬 할 수 있음 (자리 위치..

[미로 탈출] - NxM크기의 미로 - 시작 위치는 (1,1), 미로의 출구는 (N,M) - 괴물이 있는 부분은 0, 괴물이 없는 부분은 1 - 탈출하기 위해 움직여야하는 최소 칸의 개수 출력 (칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산) 위와 같은 예시 인 경우, 총 움직여야 하는 칸의 개수는 다섯칸 [해석] - 무조건 기억 ! DFS : 스택, 재귀 / BFS : deque (이게 헷갈려서 스택으로 풀 뻔 했다..) - 최소 머시기를 구하라는 문제는 BFS로 탐색하면 될듯 하다 - 이 문제를 처음 봤을 때, 4방향을 살피고 괴물 유무를 파악한 후에 좌표 이동하는 것 까지 생각이 났지만 좌표 리스트를 어떻게 deque에 넣지? 라는 생각을 했따 (하지만 너무 간단한 방법..set() 방법..

[음료수 얼려먹기] NxM 크기의 얼음 틀이 있음 구멍이 뚫린 부분 : 0, 칸막이가 존재하는 부분 : 1 구멍이 뚫려있는 부분 끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주 얼음틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성 해당 얼음틀에서 만들 수 있는 아이스크림은 총 3개 [해설코드 - 거의 코드 참고하였음] - 먼저, 입력받는 리스트를 그래프로 지정 - 끝까지 탐색해야 되는 문제는 DFS 사용 (재귀로 사용하면 탐색이 효과적인듯) - 먼저, (0,0)부터 대체로 시작인데 해당 위치가 얼음틀인지 아닌지 확인 - 얼음 틀이라면, 해당 부분을 1로 바꿔주고 상하좌우 위치를 바꿔서 dfs함수 실행 - 사실 이 부분이 재귀의 사용 부분인데, 나는 여기서..

BFS(BBreadth First Search - 너비 우선 탐색) 가까운 노드부터 탐색하는 알고리즘 큐 자료 구조 사용 위의 예시로 사용 될 경우, 결과 예시는 1,2,3,8,7,4,5,6이 됨 [코드 예시] from collections import deque def bfs(graph, v, visited): q = deque([v]) visited[v] = True # 현재 노드 방문 처리 while q: ## queue가 빌 떄 까지 반복 p = q.popleft() ## 하나 먼저 뽑고 for i in graph[p]: if not visited[i]: ## 방문하지 않았다면 q.append(i) # 큐에 삽입하고 visited[i] = True # 방문 처리 graph = [ [], [2,3,..