개발과 기획 다하기

정렬은 알고리즘 문제는 물론 실제 코드에서도 상당히 사용도가 높은 기능이다. 또한 구현할 수 있는 방법도 상당히 다양하며 그에 따라 수행시간 역시 상이해, 실력있는 개발자는 각 상황에 적합한 정렬 알고리즘을 사용할 수 있어야한다. 정렬 알고리즘들은 간단한 정렬 알고리즘인 선택정렬, 버블정렬, 삽입정렬과 고급 정렬 알고리즘인 병합 정렬, 퀵 정렬, 계수 정렬, 기수 정렬 등이 존재한다 오늘은 간단한 알고리즘에 속하는 선택정렬, 버블정렬, 삽입정렬을 정리해 보겠다. 1) 선택 정렬 원리: 1. 각 루프마다 최대(혹은 최소) 원소를 찾는다 2. 최대(혹은 최소) 원소와 마지막 원소를 교환한다 3. 탐색 범위를 1 줄인다 이를 범위가 1이 될 때까지 반복한다 코드(파이썬): def Selectionsort(a,..

1) 원격 저장소 앞서 만든 로컬 저장소는 나 혼자서 버전 관리를 할 때만 활용이 가능하다. 다른 이들과의 협업을 위해서는, 원격의 저장소가 필요한데 이를 레포지토리(Repository)라고 한다. Github에 접속하여 new repository를 통해 새로운 레포지토리를 만들 수 있다. 레포지토리의 이름과 설명도 정할 수 있다. 2) 레포지토리에 올리기 (push) 생성한 레포지토리에 들어가보면 레포지토리의 주소를 복사해 올 수 있다. 이제 로컬저장소와 원격저장소를 연결할 것이다. 로컬 저장소에서 git bash를 연 후에, git remote add origin (레포지토리 주소) 복사해온 주소를 이용해 적어준다. 이후 git push origin master 를 통해 원격저장소에 올릴 수 있다. ..

1. 버전 관리 프로그램을 개발, 특히 팀 단위로 개발하다 보면 버전 관리가 상당히 중요해진다. 따로 만든 코드를 합치거나, 서로의 코드를 수정하는 등 다양하고 복잡한 작업들을 하다 보면 코드들이 구분이 안되거나, 오류를 되돌릴 수 없어지기 때문이다. 대표적인 버전 관리 시스템이 Git이다. 그리고 Git을 호스팅해주는 사이트가 바로 Github이다. 추후의 협업 프로젝트들을 위해 Git에 대해 공부하고자 한다. 아래 내용을 위해선 Github.com의 가입과 git bash의 설치가 필요하다. 2. 로컬 저장소 일단 내 컴퓨터 내에서만 버전 관리를 한다고 생각하고 로컬저장소에서 버전 관리를 해보겠다. 먼저 git bash를 실행해 'git'이라는 명령어를 실행해 기본 명령어에 대한 안내가 나오는 지 확..

*참고 - 나동빈 유튜브 https://gae-gi-da.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra 알고리즘 - 다익스트라 알고리즘(Dijkstra) *참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이 gae-gi-da.tistory.com 다익스트라 알고리즘은 이전 포스트에서 말했듯이, 모든 간선의 가중치가 양수일 때만 적용이 가능하다. 현실의 상황에서는 간선의 가중치, 즉 거리가 음의 ..

* 참고 저서 나동빈저 https://gae-gi-da.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra 알고리즘 - 다익스트라 알고리즘(Dijkstra) *참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이 gae-gi-da.tistory.com 다익스트라 알고리즘이 하나의 시작 지점에 대해 각 노드까지의 최단 거리를 구하는 것이었다면, 플로이드 와샬 알고리즘은 모든 노드에 대해서 모든 노드까지의..

*참고 저서 나동빈 저 최단 경로 문제 유형에서 가장 많이 사용되는 알고리즘 중 하나로, 특정 노드에 대해 각 노드들까지의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 각 간선의 가중치들을 양수로 가정하고 있다. 따라 음의 가중치를 지닌 수가 있을 경우 다익스트라 알고리즘은 제대로 동작하지 않게 된다. 다익스트라 알고리즘의 과정은 다음과 같다. 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3과 4번을 반복한다. 최단 거리 테이블은 노드의 개수만큼의 크기를 지니며 출발노드에서의 최단 거리(가중치)를 ..

이번 알고리즘 스터디에서는 이분탐색과 동적계획법을 주제로 스터디를 진행하였다. 선정한 문제들이 나에게는 너무 어려워 자력으로 해결한 문제가 거의 없었다... 해결한 문제 역시 여러 풀이를 찾아보며 해결했는데, 이 과정에서 이분탐색/동적계획법 외의 많은 알고리즘 기법들 역시 배울 수 있었다. 동적 계획법의 인상적인 풀이방법도 배우게 되어 복습하고자 한다. 백준 12865 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ..

*참고저서 동적 계획법은 일반적으로 해결한 문제에 비해 수행시간을 비약적으로 줄일 수 있는 방법으로 알려져있다. 동적계획법의 핵심은 '중복된 연산을 줄이는 것' 이다. def fibo(x) ： if x == 1 or x == 2： return 1 return fibo(x - 1) + fibo(x - 2) 잘 알려진 수열인 피보나치 수열의 경우 재귀적으로 손쉽게 구현할 수 있지만 이는 상당히 비효율적인 방법이라, 실제로 데이터가 커지면 수행시간이 기하급수적으로 증가하게 된다. 그 이유는 낮은 숫자에 대한 fibo()값들이 수도 없이 다시 계산되기 때문이다. 실제로 이러한 풀이는 지수시간, 즉 O(2^n)의 수행시간을 가진다. 따라 이미 계산한 부분해(fibo(x)의 경우 x 이하 모든 수들에 대한 fibo..

*참고 저서 나동빈 저 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 데이터의 접근할 때 그 범위를 시작점과 끝점 2개를 사용하여 표현한다. 이를 문제의 특정 조건에 따라 시작점 혹은 끝점을 조작하며 탐색을 실시한다. 투 포인터를 활용해 해결할 수 있는 가장 대표적인 문제는 부분수열합에 대한 문제이다. 하나의 리스트에 대해 인접한 원소들의 합이 특정한 값인 경우의 수를 모두 구해내는 것이 문제이다. 1 2 3 2 .5 원하는 합의 값(목표값): 5 리스트가 위와 같을 시 (2+3),(3+2),(5)로 세 가지 경우를 찾을 수 있다. 이를 투 포인터 원리를 활용해 구현하는 방법은 다음과 같다. 1. 시작점, 끝점 모두 리스트의 첫 원..

*참고 저서 나동빈저 순차탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 O(n)의 시간 필요 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 O(logn)의 시간 필요 시작점(start),끝점(end),중간점(mid) 세 변수 사용하여 범위 좁힘 초기 리스트 [2,18,4,12,10,8] / 찾는 값 12 2 18 4 12 10 8 1) 리스트 정렬 [2,4,8,10,12,18] 2 4 8 10 12 18 2) 시작점, 끝점, 중간점 계산 각각 0,5,2 (인덱스) 2 4 8 10 12 18 3) 중간점의 값과 찾는 값 비교 리스트[2]의 값: 8 < 찾는 값:12 2)로 돌아가 시작점,끝점,중간점 갱신 찾는 값이 더..