조용하지않는개발Blog

삽입정렬 알고리즘 - 알고리즘 설명 삽입정렬이란? 삽입을 이용한 정렬 알고리즘 무엇을 삽입할 것인가? key값과 정렬된 리스트가 주어졌을때, key값을 정렬된 리스트의 알맞은 위치에 삽입 어떻게 삽입정렬이 돌아갈까? 삽입 정렬은 key값을 하나씩 추가하면서 정렬한다. 예를 들어.. A[1..n]이 주어진 배열이라고 하면 첫번째 A[2]을 정렬된 배열 A[1]에 집어넣는다. 두번째 A[3]을 정렬된 배열 A[1..2]에 집어넣는다. ... n-1번째 A[n]을 정렬된 배열 A[1...n-1]에 집어넣는다. 위와 같이 배열 A에 원소를 하나씩 추가하면서 정렬하게 된다. 삽입 정렬 수행 시간 최선의 경우 : an+b 최악의 경우 : an^2+bn+c 평균적으로 n^2의 시간이 걸린다고 한다. O(n^2) 삽입..

컴퓨터 알고리즘 기초 3강 정렬문제를 보고 간단하게 정리하고 추가적으로 파이썬 코드등을 추가하였습니다. 정렬문제란? n개의 숫자를 입력 받아 입력 받은 숫자들을 점점 커지는 순서나 점점 작아지는 순서로 다시 배열하여 출력하는 문제 선택 정렬 알고리즘 선택 정렬은 무엇인가? 선택하여 정렬하는 알고리즘. 최소값을 선택 정렬 - 가장 작은 값을 선택(오름차순) 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택한다. 선택한 숫자를 정렬되지 않는 숫자들 중 첫 번째 숫자와 자리를 바꾸면 선택된 숫자는 정렬된 것이다. 모든 숫자를 옮길 때까지 1-2번 과정을 반복한다. 최대값을 선택 정렬 - 가장 큰 값을 선택(내림차순) 정렬되지 않은 숫자 중에 가장 큰 숫자를 선택한다. 선택한 숫자를 정렬되지 않는 숫자들 중 첫 ..

아예 처음 하는 코딩을 처음하는 사람: www.acmicpc.net/search#q=Python%20배우기&c=Workbooks 검색 www.acmicpc.net 컴퓨터 알고리즘 기초 https://www.youtube.com/watch?v=vQv7PTKM2LI&list=PL9mhQYIlKEhdvKFh-wVpDuihNQv6C1gSy&index=2 컴퓨터 알고리즘 중급 https://www.youtube.com/watch?v=Cc-YlbLOaqY&list=PL9mhQYIlKEhcqOXxPOhs6pNpq681RDK4J&ab_channel=SKplanetTacademy 이것이 코딩 테스트다 - 나동빈님 https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEm..

SELCET 조회 SELECT * FROM ANIMAL_INS 위는 모든 모든 열을 가져옴 SELECT NAME,DATETIME FROM ANIMAL_INS 위는 NAME,DATETIME에 대한 열을 가져옴 FROM 테이블 선택 WHERE 테이블에 조건걸기 SELECT * FROM ANIMAL_INS WHERE CONDITION = 'Sick' # 부정 SELECT * FROM ANIMAL_INS WHERE NOT CONDITION = 'Sick' or CONDITION = '' # and, or SELECT * FROM ANIMAL_INS WHERE INTAKE_CONDITION = 'Sick' or INTAKE_CONDITION = 'Normal' # in SELECT NAME, ANIMAL_ID F..

다익스트라 알고리즘은 모든 정점까지의 최단 경로를 구할때 사용하는 알고리즘이다. 다익스트라 알고리즘은 그 방식이 효육적이라 그래프가 큰 경우에도 사용 가능한 장점이 있다. 그림을 그리기에는 시간이 많이 걸리니 나무위키의 그림을 가져와서 이야기 하겠습니다. A에서 시작한다는 가정하에 최단 거리를 찾아봅시다. 먼저 다익스트라 알고리즘은 아직 확인 되지 않은 거리는 전부 무한으로 해놓습니다. 첫 루프를 돌리면 위와 같이 a->b가는 거리는 10, a->c가는 거리는 30 a->d로 가는 거리는 15가 되는 것을 알수있다. 이때 리스트에는 b,c,d가 쌓이게 된다. a의 모든 루프는 끝이 났다. 다음으로는 b,c,d 중 하나를 이동하면 되는데 이때 거리가 최소인것을 먼저 진행한다. 거리가 10인 B를 먼저 시작..

백준 문제를 풀다보니 골드 문제에서 보이기 시작한 이진 탐색 문제를 좀더 잘 알고있어야 할듯 싶어 알고리즘을 작성하였다. 이진탐색 (바이너리 서치) Big O 는 O(log n) 정렬된 자료를 반으로 나누어 탐색하는 방법 주의점: 자료는 오름차순으로 정렬되어있어야함. 이진트리, 바이너리서치는 코딩 인터뷰 단골 문제라고 한다. 구현을 위한 준비 target : 찾고자 하는 값 data : 오름차순으로 정렬된 list start : data의 첫 인덱스 end : data의 마지막 인덱스 mid : start,end의 중간 인덱스 구현 개요 자료의 중간 값이 mid를 찾고자 하는 값인기 검사 아니라면 대소관계를 비교하여 start,end 값을 이동함. 동인 연산을 반복함. def binary_search(t..

분할 정복 이란? 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식. 라고 하는데 말로 설명하면 어렵다. 그래도 최대한 이해하기 쉽게 설명을 진행하겠다. 먼저 3을 10번 곱한다면 식으로 $$ 3*3*3*3*3*3*3*3*3*3 = 3^{10} $$이런식으로 계산을 하게 된다. 이때 분할 정복을 사용하면 $$ 3^{2}*3^{2}*3^{2}*3^{2}*3^{2} $$ 으로 나누어지고 계산된 값인 9를 $$ 9^{2}*9^{2}*9 $$ 이어서 또 다시 81을 $$ 81^{2}*9 $$ 만 계산하면 끝이난다 총 10번 반복할것은 3번으로 줄인것이다. 이처럼 분할 정복을 이용하면 시간을 단축시킬 수 있다. def Recursiv..