기록하고 싶은 것들

최단 경로 문제최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘 다양한 문제 상황한 지점에서 다른 한 지점 까지의 최단 경로한 지점에서 다른 모든 지점 까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로각 지점은 그래프에서 노드로 표현지점 간 연결 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하기다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 알고리즘 동작과정출발 노드 설정최단 거리 테이블을 초기화방문하지 않은 노드 ..

다이나믹 프로그래밍메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 방법이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함다이나믹 프로그램잉의 구현은 탑다운 & 보텀업으로 구성다이나믹 프로그래밍은 동적계획법이라고도 부름 다이나믹 프로그래밍의 조건최적 부분 구조(Optimal Substructure)큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 더 큰 문제 해결 가능 중복되는 부분 문제(Overlapping Subproblem)동일한 작은 문제를 반복적으로 해결 가능 피보나치 수열피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능1,1,2,3,5,8,13,21,34,55,89, …점화식: 인접한 항들 사이의 관계식배열이나 리스트를 이용해 수열 표현 ..

이진 탐색 알고리즘순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 이진 탐색의 시간 복잡도단계마다 탐색 범위를 2로 나누는 것과 동일 , 연산횟수는 log2N에 비례즉, 이진 탐색은 탐색 범위를 절반씩 줄이고 시간 복잡도는 O(log2N) # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target:..

정렬 알고리즘정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 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) 시간 복잡도는 O(N**2) 삽입 정렬처리되지 않은 데이터를 하나씩 ..

그래프 탐색 알고리즘대표적인 그래프 탐색 알고리즘이 DFS/BFS는 코딩테스트에서 매우 자주 등장하는 유형 스택 자료구조선입후출의 자료구조 입구와 출구가 동일한 형태(ex : 박스 쌓기) 스택 구현 예제stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 큐 자료구조선입 선출의 자료구조입구와 출구가 모두 뚫린 터..

그리디 알고리즘그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법정당성 분석이 중요일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많지만,코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황임 ex) 거스름 돈: 문제아이디어: 가장 큰 화폐 단위부터 돈을 거슬러줌큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장최소한의 아이디어를 떠올리고 정당한지 검토 n = 1260 count = 0 array = [500,100,50,10] for coin in array: count += n // coin #해당 화페로 거슬러 줄..

실수 값을 제대로 비교하지 못하는 상황 발생시ex) 0.6+.0.3을 0.899999 로 나타냄이럴 때는 round()함수를 이용하여 문제해결 수자료형의 연산파이썬에서는 나누기 연산자(/)는 나눠진 결과를 실수형 반환몫을 구할때는 a//b 리스트 자료형데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형배열 또는 테이블이라고 부름 리스트 인덱싱과 슬라이싱리스트 뒤에서 부터 원소를 접근할 때 음수 사용리스트에서 연속적인 위치를 가지는 원소를 가져올 때는 슬라이싱 사용(끝 인덱스는 실제 인덱스보다 1을 더 크게 설정) 리스트 컴프리헨션 a = [i for i in range(50)]array = [i for i in range(20) if i % 2 == 1]2차원 리스트를 초기화할 때 효과적으로 사용 가..

인공지능 회의록 MiniMinute 👩‍👩‍👧‍👦 팀 구성 총 4명이 함께 진행 (AI+Backend1, Backend 1, Frontend 2) 🕐 프로젝트 기간 *2022.03 ~ 2022.06 (*Frontend 개발) 🔗 Link https://github.com/yunhwan98/MiniMinute ✍️ 요약 Miniminute은? 참가자들의 회의 내용을 대화 형식으로 저장하고 텍스트와 음성을 기반을 한 감성 인식을 통해 참가자에게 피드백을 제시하는 감정인식 AI회의록 ✏ 논리 구성도 🏛 아키텍쳐 🛠️ 사용 기술 및 라이브러리 Fontend: React Backend: Django DB: MariaDB AI: AWS Transcribe, Pytorch, Tensorflow 💻 담당 역할 및 기능..