컴퓨터 공부하는 블로그 컴퓨터 공부하는 블로그

해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임. 양의 정수 자리수 구하기 위와 같이 메서드에 매개변수로 특정 숫자를 입력하면 해당 숫자의 자리수를 반환하는 문제다. 최대값, 최소값, 중간값 구하기 - 자료구조와 함께 배우는 알고리즘 입문 해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임. 여러 변수의 값 중 최대값 구하기 예를 들어서 여러 개의 변수가 있을 때 그 중에서 가장 큰 값을 sgcomputer.tistory.com 이전 세 개의 정수 중 가운데 값 구하는 문제처럼 사람이 보면 알기 쉽다. 근데 컴퓨터한테 해당 작업을 시킬 때는 좀 더 번거롭게 처리해줘야 한다. 우선 나는 이 문제를 보고 사람은 왜 이걸 보고 ..

해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임. 정수의 합 구하기 - while을 이용 특정 숫자를 메서드 안에 넣으면 1부터 해당 숫자까지의 합을 구하는 식이다. public static int while_test(int a){ int i = 0; // 연산에 기준이 될 값 int sum = 0; // 반환할 값 while(i

해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임. 여러 변수의 값 중 최대값 구하기 예를 들어서 여러 개의 변수가 있을 때 그 중에서 가장 큰 값을 구하는 방법은 무엇일까? 아마 이건 따로 알고리즘을 접하지 않아도 어려운 문제는 아닐 것이다. 그냥 순차적으로 비교해나가면 된다. public static int max(int a, int b, int c, int d){ int max = a; // 변수 max를 생성해서 a의 값을 대입 if(b>max) max = b; // max와 b를 비교해서 b가 크다면 max에 b를 대입 if(c>max) max = c; // max와 c를 비교해서 c가 크다면 max에 c를 대입 if(d>max) max = d; // m..

해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임. 알고리즘이란? 문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이뤄진 집합. 알고리즘의 조건은 다음과 같다. - 입력이 가능: 어떤 조건의 수를 받아서 처리할 수 있어야 하기 때문이다. - 출력이 가능: 알고리즘은 문제 해결에 따른 결과물을 도출해야한다. - 명확성: 알고리즘은 각 단계가 명확하고 애매하지 않아야 한다. - 유한성: 알고리즘은 유한한 계산 단계를 거쳐야 한다. 간단히 말하면 명확한 계산 과정을 거친 일종의 문제 풀이를 위한 방법이라고 할 수 있을 것이다.

알고리즘은 효율적으로 짤수록 시간과 자원이 굉장히 줄어드는 효과를 볼 수 있다. 그리고 이러한 알고리즘이 수행하는데 걸리는 시간의 상한선 하한선을 시간복잡도로 표현할 수 있다. 시간복잡도가 낮을수록 해당 알고리즘이 더욱 효율적이라고 볼 수 있다. 시간복잡도에서 알고리즘의 실행시간 상한선은 Big-O 표기법을 사용해 나타낸다. O(1) 상수의 형태 O(log n) 로그 형태 이진 탐색 O(n) 선형 형태 선형 탐색 O(n long n) 선형로그 형태 퀵정렬, 병합정렬(합병), 힙정렬 O(n^c) 다차 형태 선택정렬, 버블정렬, 삽입정렬 해당 표에서는 O(1)가 가장 빠르고 O(n^c)가 가장 오래 걸린다. 이러한 시간 복잡도는 대략적인 큰 숫자를 비교하는 것을 기본으로 한다. 이유는 작은 수를 하나하나 헤..

합병 정렬(merge sort)란? 모여있는 데이터들을 요소가 단 1개가 될 때까지 계속 반으로 나누다가 1개로 나눠지면 그때부터 역으로 숫자를 1개씩 정렬하면서 올라가고 병합하는 방식 예를 들자면 다음과 같다. 7, 4, 5, 2, 6, 3, 8, 1 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과 4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과 1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과 1. 우선적으로 숫자들을 각 요소가 1개가 될 때까지 계속 쪼갠다. 2. 2개의 데이터를 묶어서 비교해서 큰 수는 오른쪽, 작..

선택정렬(selection sort)이란? 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수를 찾아) 첫 번째 위치 (혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬을 말한다. 선택은 교환 횟수를 최소화하지만, 반면에 각 자료를 비교하는 횟수는 증가한다. 간단히 말하면 1~10까지의 숫자가 뒤섞여 있으면, 가장 작은 숫자인 1을 찾아서 가장 왼쪽에 배열하고, 그 다음에는 1을 제외한 2~10이 뒤섞인 숫자에서 2를 찾아서 1 다음 배치하는 식으로 반복하여 정렬하는 방식을 말한다. list a = [3, 2, 5, 4, 1] 첫번째 리스트 a내의 n개의 숫자 중 가장 작은 숫자를 찾는다. 가장 작은 숫자 1을 가장 왼쪽에 놓는다. list a = [1, 3, 2, 5, 4] 이제 1을 제외한 n-..

정렬의 필요성 정렬의 필요성은 간단하다. 원하는 자료를 더욱 빨리 찾을 수 있게 도와주기 때문이다. 어떤 수를 찾을 때 정렬이 되있지 않다면 장기적으로 보면 시간과 자원의 낭비가 적체되는 현상을 겪는다. 정렬이 되지 않으면 탐색 또한 효율적으로 진행될 수 없다. 버블 정렬(bubble sort) 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법. 첫번째 데이터부터 마지막 데이터까지 훑으면서 작은 값은 작은 값대로 큰 값은 큰 값대로 단 두개의 요소를 1대1로 교체해가면서 정렬하는 방식을 말한다. 즉 리스트 안에 있는 두 개의 인접한 수를 비교해서 순서에 맞지 않는다면 교환해주고 이를 계속 반복하는 방식. 예를 든다면 다음과 같다. #define _CRT_SECURE_NO_WAR..