본문 바로가기

전체 글

 (44)
Algorithm(알고리즘) - selection sort(선택 정렬)이란 무엇인가::FBTT 지난 글에 이어서 정렬 알고리즘에 대해서 이야기해 보도록 하겠습니다. 이번에 이야기할 선택 정렬도 성능이 좋다고 할 수 없는 시간 복잡도가 O(n ^ 2)인 알고리즘입니다. 이번 정렬도 배열에서의 오름차순 정렬을 기준으로 설명하겠습니다. 선택 정렬의 개념 선택 정렬은 배열에서 가장 작은 원소를 찾아 '선택'하여 배열의 첫 번째 원소와 교환을 통해 정렬을 진행합니다. 그러고 나서 배열의 첫 번째 원소를 제외하고 다시 가장 작은 원소를 찾은 후 배열의 두 번째 원소와 교환합니다. 두 번째 진행을 통해 찾은 작은 원소는 두 번째로 작은 원소이기 때문입니다. 이렇게 (배열의 길이) - 1번 반복해주면 정렬된 배열을 얻을 수 있습니다. 예를 들어 아래의 배열을 선택 정렬을 통해 정렬한다 해봅시다. 5 1 2 3 ..
Algorithm(알고리즘) - Bubble Sort(버블 정렬, 거품 정렬)이란 무엇인가::FBTT 지난 글에서는 시간 복잡도가 O(n ^ 2)인 정렬 알고리즘들 중 하나인 삽입 정렬에 대해서 알아보았습니다. 이번에도 마찬가지로 시간 복잡도가 O(n ^ 2)인 정렬 알고리즘 중 대표적인 버블 정렬에 대해 알아보겠습니다. 이번에도 배열에서의 오름차순 정렬을 기준으로 설명하겠습니다. 버블 정렬의 개념 버블 정렬의 기본은 인접한 두 자료의 비교를 통해 원하는 순서로 바꾸어주는 것입니다. 앞에서부터 비교할 수도 있고, 뒤에서부터 비교할 수도 있습니다만 저는 뒤에서부터 비교하는 알고리즘을 구현하겠습니다. 여기저기 나와있는 알고리즘을 보니까 앞에서부터 비교하는 알고리즘들이 대부분이더군요. 앞에서부터 비교하는 알고리즘은 다른 글들을 찾아보면 금방 찾을 수 있을겁니다. 뒤에서부터 비교한다고 했으니 예를 들어 보는 것..
Algorithm(알고리즘) - insertion sort(삽입 정렬)이란 무엇인가::FBTT 오늘은 정렬 알고리즘들 중 하나인 삽입 정렬에 대해서 알아보겠습니다. 배열에서의 정렬을 가정하고 설명하도록 하겠습니다. 정렬은 오름차순을 기준으로 하겠습니다. 삽입 정렬의 개념 이름에서 알 수 있다시피 삽입, 즉 추가 연산을 통해 정렬을 하는 알고리즘입니다. 추가할 때 크기 순으로 삽입을 진행한다면 추가 연산을 모두 끝냈을 때 데이터들은 정렬된 상태일 테니까요 그러면 '정렬되지 않은 데이터가 있을 때 삽입 정렬을 실행시키면 어디에 추가 연산을 진행하냐'라는 의문이 생깁니다. '새로운 배열에 다시 하나하나 추가를 통해 정렬을 하는 것인가?' 그건 아니고 배열 속에 정렬되어 있는 부분 배열에 추가를 해줍니다. 부분 배열에 적당한 위치에 삽입해줌으로써 부분 배열의 정렬을 유지하면서 추가해줍니다. '그러면 배열..
백준 5585 거스름돈 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 이번 문제는 이전에 풀었던 문제와 매우 비슷합니다. 바로 설탕 배달 문제입니다. https://readytoearndon.tistory...
data structure(자료 구조) - Linked list(연결 리스트) 기반의 Stack(스택) 구현::FBTT 지난 번에는 배열을 기반으로 스택을 구현했었습니다. 그러면서 그 글 마지막에 되도록이면 빨리 연결 리스트 기반의 스택도 구현할 거라고 했었는데 그게 바로 오늘입니다. 참고용으로 배열 기반의 스택은 아래 글에 구현해놨습니다. https://readytoearndon.tistory.com/37 data structure(자료 구조) - Array(배열) 기반의 Stack(스택) 구현::FBTT 지난 글에서는 스택의 개념과 정의 그리고 그 쓰임새에 대해서 알아보았습니다. https://readytoearndon.tistory.com/36 data structure(자료 구조) - stack(스택)의 개념과 사용 이번에 알아볼 자료구조는 stack(.. readytoearndon.tistory.com '연결 리..
data structure(자료 구조) - 변형된 Queue(큐)::FBTT 큐의 단점을 보완하기 위해 여러가지로 변형된 큐들이 존재합니다. 오늘은 특수한 큐들 중 3가지를 알아볼 것입니다. circular queue(원형 큐) deque(덱) priority queue(우선순위 큐) Circular queue(원형 큐) 첫 번째로 알아볼 것은 원형 큐입니다. 지난 글에서는 일반적인 큐를 구현해봤습니다. 그 때는 말하지 않았지만 구현했던 큐에는 단점이 하나 있습니다. https://readytoearndon.tistory.com/39 data structure(자료 구조) - Array(배열) 기반의 Queue(큐)의 구현::FBTT 지난 글에서는 큐가 무엇인지와 그의 연산들을 간단히 보았었습니다. https://readytoearndon.tistory.com/38 data st..
data structure(자료 구조) - Array(배열) 기반의 Queue(큐)의 구현::FBTT 지난 글에서는 큐가 무엇인지와 그의 연산들을 간단히 보았었습니다.https://readytoearndon.tistory.com/38data structure(자료 구조) - Queue(큐)의 개념::FBTT이번에는 큐에 대해서 설명해보고자 합니다. 지난번 설명했던 스택과 비교해서 설명해보려 합니다. 혹시 스택에 대해서 모르시는 분은 아래 글을 먼저 보고오시길 추천드립니다. 그래도 스택을 몰라도 되게끔 설명..readytoearndon.tistory.com이번에는 큐의 구현을 해보려고 합니다. 저는 코드를 올릴 때 조각조각 올려서 마지막에 합치는 방식으로 올리지 않고 처음에 올렸던 코드 뒤에 이어 붙여서 마지막에는 완성된 코드가 되게끔 합니다. 이 점을 유의하시고 코드를 읽어주셨으면 합니다. 저번 글에서 ..
data structure(자료 구조) - Queue(큐)의 개념::FBTT 이번에는 큐에 대해서 설명해보고자 합니다. 지난번 설명했던 스택과 비교해서 설명해보려 합니다. 혹시 스택에 대해서 모르시는 분은 아래 글을 먼저 보고오시길 추천드립니다. 그래도 스택을 몰라도 되게끔 설명해볼 겁니다. https://readytoearndon.tistory.com/36 data structure(자료 구조) - stack(스택)의 개념과 사용 이번에 알아볼 자료구조는 stack(스택)입니다. stack 뜻을 알아보겠습니다. 영어 사전을 보면 여러 뜻 중 쌓다라는 뜻이 있는 것을 볼 수 있습니다. 스택은 뜻에 따라 자료를 쌓아 보관한다고 생각하면 됩니다. 실.. readytoearndon.tistory.com queue(큐)는 흔히 줄, 대기열에 빗대어 많이 설명합니다. 예를 들어 맛집에서 ..

티스토리툴바