블로그

[탐색 알고리즘] 순차 탐색 알고리즘 vs 이진 탐색 알고리즘 알고리즘 비교알고리즘의 시간 복잡도만 비교하게 되면, 순차 탐색 알고리즘은 $O(n)$이고 이진 탐색 알고리즘은 $O(logn)$이므로 이진 탐색 알고리즘이 훨씬 좋아 보인다. 하지만 이진 탐색 알고리즘은 데이터가 정렬되어 있어야 한다는 전제 조건이 있다. 보통 정렬 알고리즘의 경우 $O(nlogn)$의 시간 복잡도를 가진다. 어떤 알고리즘이 좋다고 분명하게 말할 수는 없다. 상황에 맞춰서 적합한 알고리즘을 선택해야 한다.아래 코드는 배열의 길이가 500, 5000, 50000일 때, 각 알고리즘의 최대 연산횟수를 나타낸 것이다.(Worst Case)$O(n)$과 $O(logn)$의 차이가 어느정도인지 알 수 있을 것이다. Code123456..

[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search) 이진 탐색 알고리즘 이진 탐색 알고리즘을 위해서는 데이터가 정렬되어 있어야 한다. 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 배열 { 1, 2, 3, 7, 9, 12, 21, 23, 27 }에서 3을 찾는 경우 알고리즘 진행 방식은 아래와 같다. 첫번째 시도배열 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 그 인덱스에 해당하는 값이 3인지 확인한다. 두번째 시도arr[4]의 값 9와 찾는 값 3의 대소를 비교한다.3이 9보다 작으므로 인덱스 4~8은 탐색의 범위에서 제외한다.(정렬된 데이터여서 가능)0과 3을 더하고 2로 나눈다.(나머지는 버린다.)결과가 1이므로 arr[1]의 값 2와 찾는 값 3이 일치하는..

[탐색 알고리즘] 순차 탐색 알고리즘(Linear Search) 순차 탐색 알고리즘 맨앞에서 부터 맨끝까지 순서대로 탐색을 진행하는 알고리즘. 시간 복잡도 O(n)을 가진다.(Worst Case) 종료 조건배열의 길이 내에서 숫자 발견시 종료. 탐색 실패시 배열의 길이만큼 탐색 후 종료된다. Code1234567891011121314151617181920212223242526272829303132#include // 순차 탐색 알고리즘 함수// 찾는 숫자가 있으면 찾는 숫자의 인덱스 리턴// 없으면 -1 리턴int LSearch(int ar[], int len, int target){ int i = 0; for (; i

[컴퓨터 알고리즘 성능분석] 시간 복잡도 vs 공간 복잡도 시간 복잡도와 공간 복잡도 알고리즘 트레이닝 사이트에서 문제를 풀다보면 아래 그림과 같이 시간 복잡도와 공간 복잡도가 조건으로 주어진다.알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데 수행시간에 해당하는 것이 시간 복잡도, 메모리 사용량에 해당하는 것이 공간 복잡도이다.정의는 아래와 같다.- 시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석결과- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석결과 간단하게 말하면 알고리즘 성능평가는 시간 복잡도와 공간 복잡도를 계산하고 점근적 표기법으로 나타내면 된다.(점근적 표기법 포스팅 : http://ledgku.tistor..

치킨에 위로 받았던 수 많은 날들치킨은 살포시 다가와 나의 피와 살이 되었네. 혼자 먹기에 두마리 치킨은 너무 많아남기고야 말았네... 사전 작업치킨이 남았을 때 다음 날 촉촉하게 먹기 위해서는 보관이 가장 중요합니다.포장용기에 그대로 보관하게 되면 치킨도 마르고 종이 냄새도 배고 위생상으로도 좋지 않아요.조금 귀찮더라도 남은 치킨은 위생 봉투에 밀봉 후 냉장고에 보관하는 습관을 들여요. 준비물남은 치킨, 뚜껑있는 후라이팬, 식용유 2큰술 Chicken Recovery냉장고에서 남은 치킨을 꺼내고 후라이팬을 꺼내서 중불에 달궈줍니다. 식용유, 까놀라유, 포도씨유등...(올리브유 X)을 두 수푼 정도 팬에 부어줍니다.기름에 열이 오르면 스냅을 이용해 팬에 기름이 골고루 묻도록 컨트롤 해 줍니다.그 다음 남..

[컴퓨터 알고리즘 성능분석] 점근적 표기법 (Asymptotic Notation) 점근적 분석주어진 문제를 푸는 알고리즘은 딱 하나만 있는 것이 아니라 여러 개가 존재한다.하드웨어, 운영체제, 프로그래밍 언어 등 특징에 따라서 최적화된 여러가지 알고리즘이 존재한다.어떤 문제를 해결하는 데에는 항상 다수 개의 알고리즘이 존재할 수 있으므로 알고리즘의 성능을 비교할 필요가 있다. 점근적 분석의 필요성어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다. 이를 효과적으로 해결하는 방법이 점근적 분석법이다. 점근적 분석법은 각 알고리즘이 ..

[컴퓨터 알고리즘의 정의] 컴퓨터 알고리즘의 정의와 표현 컴퓨터 알고리즘이란? 컴퓨터를 이용하여 문제를 풀기위한 방법을 과정이나 절차를 이용해 만들어 놓은 것. 컴퓨터가 이해할 수 있는 언어(C, Java...)를 이용해 실행할 내용을 컴퓨터가 할 수 있는 가장 작은 기본 작업의 형태로 만들고 순차적으로 나열한다. 컴퓨터는 지시 사항을 차례대로 하나씩 수행하면서 최종 결과를 얻게 되고 그 결과는 해결하고자 했던 문제의 해답이 된다. 컴퓨터 알고리즘의 정의와 표현컴퓨터 알고리즘을 정의하고 표현하기 위해서는 크게 4가지 단계를 거친다. - 문제 정의 (Problem Definition) : 해결하고자 하는 문제. 입력과 출력의 형태로 정의될 수 있어야 하고 컴퓨터가 수행할 수 있는 형태로 전환이 가능해야한다..

불금엔 고기 하지만 포스팅하는 지금은 새터데이 만원만 있으면 두 명은 충분 필요충분 LA 갈비 스테이크 만드는 법- 정육점이 간다. 아저씨에게 말을 건다. LA 갈비 만원어치 주시는데 2cm로 두껍께 썰어주세요.- 고기 절단 과정을 꼼꼼하게 검사한다. 주머니에서 자를 꺼내 고기 두께를 재고 오차범위가 $\pm$0.3cm 내외인지 확인 후 결제한다.- 집에 와서 쟁반에 고기를 편다.- 올리브 유를 고기에 흥건하진 않지만 촉촉할 정도로 뿌려준다. 대파와 마늘을 슬라이스해서 위에 뿌려주고 10~20분간 마리네이드 한다.- 마리네이드 하는 동안 수학 문제집을 꺼내 한권을 다 푼다.- 팬을 심할 정도로 달군다. 하지만 너무 심하면 안된다. 연기가 날랑말랑할때 바로 그 때 마리네이드한 고기를 팬에 올린다. 고기만 ..

[자료구조 정의] 자료구조와 알고리즘의 정의 그리고 연결고리 자료구조와 알고리즘의 정의와 상관관계 자료구조 : 데이터를 표현하고 저장하는 방법 알고리즘 : 문제 해결 방법어떤 자료구조를 쓰느냐에 따라 문제를 해결하는 방법이 달라지고 성능도 달라지게 된다.모든 상황에 좋은 자료구조는 존재하지 않는다. 상황에 따라 효율적인 자료구조를 선택하고 알고리즘을 구현해야한다. 자료구조란?우리가 평소에 많이 사용했던 정수형 변수 int, 구조체, 배열 등 데이터를 저장하기 위해 사용했던 것들 모두 크게 보면 자료구조에 속한다. 자료형이나 배열등은 너무 간단한 자료구조이기에 자료구조론에서는 주로 선형, 비선형 자료구조를 다룬다. 선형 자료구조(Linear Data Structure)- 데이터를 선의 형태로 나란히 혹은 ..

[HTML 수학 수식 표현] MathJax.js로 Web에서 수학 수식 표현하기 MathJax.js 소개 MathJax.js는 HTML 문서에서 수학 수식을 표현할 수 있게 해주는 오픈소스 스크립트입니다. (홈페이지 : https://www.mathjax.org/)간단한 스크립트 추가만으로 편리하게 수식을 입력할 수 있습니다. MathJax.js 설정- HTML 파일을 열고 사이에 아래 스크립트를 추가 123456 MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} });cs MathJax.js 문법- 수식 입력은 LaTeX나 MathML로 할 수 있다. ( LaTex 입력 방법 참조 : https://en.wikibooks.or..