경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!{{쉽게 알 수 있다 시리즈|이 문서는 정말 쉽습니다.|문서의 내용이 너무 쉬워서 오늘부터 프로그래밍 할 수 있을 것 같습니다.}} [[분류:컴퓨터_프로그래밍]] {{토막글}} == 들어가기 전 == {{--|일단 이게 입문인지부터 생각해보자}} 빨간 컵에 [[칠성사이다]]가 담겨져 있고 파란 컵에 [[스프라이트]]가 담겨져있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 안된다고는 안했다. 알고리즘은 문제를 해결하기 위한 것이지 [[수수께끼]]나 [[넌센스]] 문제가 아니다. 이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스 처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. <del>이제 제 3의 변수를 쓰지 않고 변수 2개의 값을 맞바꾸는 알고리즘을 생각해보자.</del> {| class="collapsible collapsed" |- ! 의사코드 펼치기 |- | 1 '''function''' 바꾸기(''첫번째컵'', ''두번째컵''): 2 ''잠시담아둘컵'' ← ''첫번째컵'' 3 ''첫번째컵'' ← ''두번째컵'' 4 ''두번째컵'' ← ''잠시담아둘컵'' 5 '''end function''' 6 7 '''function''' 지금상황(): 8 ''파란컵'' ← "칠성사이다" 9 ''빨간컵'' ← "스프라이트" 10 바꾸기(''파란컵'', ''빨간컵'') 11 '''print''' ''파란컵'' 12 '''print''' ''빨간컵'' 13 '''end function''' |- |} <source lang="csharp" class="mw-collapsible mw-collapsed"> using System; namespace 사이다컵바꾸기 { class Program { static void Main(string[] args) { // 빨간 컵과 파란 컵에 칠성사이다와 스프라이트가 담겨져 있다. string 빨간컵 = "칠성사이다"; string 파란컵 = "스프라이트"; Console.WriteLine("=====바꾸기 전====="); Console.WriteLine("빨간컵 : {0}", 빨간컵); Console.WriteLine("파란컵 : {0}", 파란컵); // 새롭게 준비한 노란 컵 string 노란컵; // 스프라이트를 빨간 컵에 붓기 위해 칠성사이다를 노란컵에 붓는다. // 그 다음 파란 컵의 스프라이트를 빨간 컵에 붓는다. // 그 다음 노란 컵에 임시로 담아둔 칠성 사이다를 파란 컵에 붓는다. 노란컵 = 빨간컵; 빨간컵 = 파란컵; 파란컵 = 노란컵; Console.WriteLine("=====바꾼 후====="); Console.WriteLine("빨간컵 : {0}", 빨간컵); Console.WriteLine("파란컵 : {0}", 파란컵); } } } </source> 여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값을 b에 저장한다. 그 다음 a에서 b를 뺀 값을 a에 저장하면 된다. <del>숫자가 아니고 객체면?</del> <del>[[우린 안될 거야 아마|포인터 주소값을 더하고 빼면... ...]]</del> 사실 덧셈보다 더 빠른 방법은 XOR 회로를 사용하는법이 있다. 값이 같지 않으면 a=a^b b=a^b a=a^b를 넣어두면 정수가 아니더라도, 산술적 연산이 아니라 비트 배열 자체가 바뀌기 때문에 값이 교환된다.<s>하지만 병렬 프로그래밍에서는 무리DA☆ZE★</s> == 알고리즘의 시간 복잡도 == 방을 정리한다고 해보자. 방에 널려있는 물건의 양에 따라 정리에 걸리는 시간이 달라질 것이다. 이렇게 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이걸 알고리즘의 시간 복잡도라 한다. 알고리즘의 시간 복잡도는 계산 횟수가 많아지면 높아진다. 그런데 이 계산 횟수의 정확한 측정이 어렵기 때문에, 보통 [[Big O 표기법]]이라는 걸 이용해서 표시한다. 예를 들어, 입력된 데이터의 갯수가 <math>n</math>개일 때 <math>2n+7</math>번 계산하는 알고리즘과 <math>2n</math>번 계산하는 알고리즘이 있다고 하자. <math>n</math>이 커지면 둘 사이의 차이는 사실상 없어진다. 즉 <math>O(2n+7)=O(2n)</math>이다. 좀 더 나아가면 계산 횟수가 <math>n</math>에 비례하므로, 그냥 <math>O(n)</math>라고 표현할 수 있다. 일반적으로, 이 중 가장 간단한 형태인 <math>O(n)</math>로 표기한다. 이와 비슷하게, <math>2n^3+n^2</math>번 계산하는 알고리즘의 시간 복잡도는 <math>O(n^3)</math>로 나타낼 수 있다. 자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다. 위에서 아래로 갈수록 시간 복잡도가 높아진다. {| class='wikitable' ! 시간 복잡도 !! 설명 |- | <math>O(1)</math> || 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다. |- | <math>O(\log n)</math> || [[로그]] 형태 |- | <math>O(n)</math> || 선형 |- | <math>O(n\log n)</math> || 선형로그 형태 |- | <math>O(n^2), O(n^3),\cdots</math> || 다차 형태 |- | <math>O(2^n)</math> || [[지수]] 형태 |- | <math>O(n!)</math> || [[팩토리얼]] 형태 |} 예를 들어 아래의 [[쉽게_배우는_프로그래밍_입문/알고리즘#자료구조#선형 랜덤 접근 불가능#데크#링크드 리스트|링크드 리스트]]에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 <math>O(n)</math>, [[쉽게_배우는_프로그래밍_입문/알고리즘#자료구조#선형 랜덤 접근 가능#해시|해시 테이블]]에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 <math>O(1)</math>이다. 이는 평균적으로 해시 테이블에서의 탐색이 링크드 리스트에서의 탐색보다 빠르다는 뜻이다. == 알고리즘의 정당성 증명 == 갑자기 왠 뜬금없이 증명이 튀어나왔는지 궁금할 것이다. 당연하지만, 우리는 천재가 아니라서 머릿속으로 생각한 알고리즘이 실제로 아주 잘 돌아간다고 보장할 수 없기 때문에 생각해낸 알고리즘이 문제를 풀 수 있다는 것을 보여야 한다. === 수학적 귀납법 === 다들 수학 공부하면서 한 번씩은 들어봤을 그것이다. 수학적 귀납법을 이용한 증명은 크게 ''단계 나누기''와 ''첫 단계 증명'', ''귀납 증명''으로 나눈다. 자세한 내용은 [[수학적 귀납법|해당 항목]] 참고. ==== 반복문 불변식 ==== 반복문의 내용이 매 번 실행될 때마다 중간 결과가 올바른 답을 도출하기 위한 결과로 잘 나오는지를 판별하는 조건이다. 반복문이 마지막에 올바른 답을 내놓으려면 항상 이 식이 변하지 않아야 한다(그러므로 ''불변식''이라고 한다). 불변식을 이용해 다음과 같이 반복문의 정당성을 증명할 수 있다. # 반복문 진입시에 불변식이 성립함을 보인다.(''초기 조건'') # 반복문 내용이 불변식에 영향을 주지 않음을 보인다.(''유지 조건'') # 반복문 종료후 불변식이 성립하면 항상 올바른 답이 나옴을 보인다. === 귀류법 === 수학에서도 많이 사용되는 만능의 증명법, 귀류법이다. 자세한 내용은 [[귀류법|해당 항목]] 참고. === 비둘기집의 원리 === 경우의 수에서 자주 언급되는 그 원리 맞다. [[수포자도 쉽게 알 수 있는 수학#경우의 수|해당 항목]] 참고. === 구성적 증명 === 위에 언급한 증명 방법들과는 달리, 구성적 증명은 답의 존재성을 보이는게 아닌, ''답을 구하는 방법 그 자체를 보이는 것''이다. 쉽게 말해, 그냥 '''답을 구하는 알고리즘의 실행 과정을 설명'''한다고 생각하면 된다. == 이 문서에서 알고리즘을 표현하기위해 사용한 언어 == 아래 나오는 모든 코드는 '''[[C(프로그래밍 언어)|C언어]]'''를 기본으로 하며, 다른 언어들은 알아서 [[추가바람|추가해주길 바란다]]. 실제 문제 풀이 예제를 제외한 알고리즘을 [[의사코드]]로 작성할 수 있다면 각 언어별 코드보다 위에 의사코드 버전을 추가해주길 바란다. == 플로우 차트 == === 기호 === == 자료구조 == === 선형 자료구조 === 한 종류의 데이터가 선처럼 길게 나열된 자료구조이다. ==== 랜덤 접근 가능 ==== 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다. ===== 배열 ===== 가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. [[C(프로그래밍 언어)|C언어]]에서는 대괄호를 사용한다. <source lang="C"> int array1[]; //int *array1과 비슷함. int array2[10]; //크기를 가지는 배열 int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열 </source> C에서 배열에 포인터를 사용하여 접근하는 것을 보면, 배열의 각 원소의 주소가 연속적으로 배치되어 있다는 것을 알 수 있다. ===== 해시 ===== 해시는 해시 함수로 구현한다. 해시 함수는 마치 배열처럼, 어떤 자료를 찾을 때 <math>O(1)</math>의 시간만을 소요한다. 해시함수에 키 값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다. 하지만, 언제나 <math>O(1)</math>이 보장되는 것은 아니다. 자세한 것은 [[해시 테이블]] 참고. ==== 랜덤 접근 불가능 ==== 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다. ===== 스택 ===== [[파일:Data stack.svg|섬네일|스택 자료구조]] 먼저 들어간 자료가 나중에 나오는 자료구조. 유식한 말로 후입선출(後入先出) 구조라고 한다. 자료를 넣는 push 함수와 자료를 빼는 pop 함수를 갖는 게 정석이다. empty, full 등 다른 함수들을 옵션으로 가질 수도 있다. 아래는 배열로 구현한 스택이다.<ref>C++ STL의 그것보다 빠를 것이다. 다만 확장이 어려울 뿐.</ref> <source lang="C"> //헤더 부분 void push(int); //push 함수 정의 int pop(); //소스 부분 int array[500]; //스택의 최대 크기는 500 int top = -1; //스택의 현재 크기는 0; void push(int n) { array[++top] = n; } int pop() { return array[top--]; } </source> 사용법은 스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다. <source lang="c"> push(1), push(2), push(3); printf("%d %d %d", pop(), pop(), pop()); </source> 출력 결과는 3 2 1과 같을 것이다. ===== 큐 ===== [[파일:Data Queue.svg|섬네일|큐 자료구조]] 먼저 들어간 자료가 먼저 나오는 자료구조. 선입선출(先入先出) 구조라고도 한다. 자료를 넣는 Enqueue 함수와 Dequeue 함수를 가진다. 밑의 큐는 [[연결 리스트]]로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다. <source lang="C"> void enqueue(int); int dequeue(); struct linkedList { int value; struct linkedList *next; }; struct linkedList *front; //큐의 맨 앞을 가리킨다. struct linkedList *back; //큐의 맨 뒤를 가리킨다. void enqueue(int n) //큐에 자료를 넣는 함수 { if(front == NULL) //큐가 비어있을 경우 { *front = {n, NULL}; //맨 앞에 자료를 넣고 back = front; //맨 뒤와 맨 앞을 같게 한다. } else { back -> *next = {n, NULL}; //맨 뒤 다음에 자료를 넣는다. back = back -> next; //넣은 자료를 맨 뒤로 한다. } } int dequeue() //큐에서 자료를 빼는 함수 { int res = front -> value; front = front -> next; return res; } </source> ===== 데크 ===== 간단하게 말하자면 스택과 큐의 [[융합]]형태. 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 보통 입력이나 출력 중 하나를 한 쪽 입구만 가능하게 제한하는 형태가 많이 쓰인다. ===== 링크드 리스트 ===== 연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다. 옵션으로 이전 노드를 가지게 할 수도 있으며, 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다. 가장 간단하게 구현한 것은 위의 [[큐]]. 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다. === 비선형 자료구조 === 선형 자료구조가 아닌 모든 자료구조이다. ==== 그래프 ==== [[파일:6n-graf.svg|섬네일|이런 거.]] 수학, 과학 시간에 많이 보던 그 그래프와는 [[사뭇]] 다르다. <del>고등학교 교육과정에서 이산수학이 빠지고 행렬도 빠짐에 따라 같이 빠지게 되는 비운의 단원</del>알고리즘을 배우다 보면 자주 나오는 구조. 점들, 그리고 점들을 연결하는 선들로 이루어진 [[지도]] 비스무리한 걸 연상하면 편하다. 이때의 점을 노드, 선을 엣지라고 부른다. 간단한 구조체를 만들어 보자. <source lang="C"> struct Edge //노드보다는 엣지로 나타내는 편이 대부분의 경우에 더 좋다. { int snode; //시작 노드 int enode; //종료 노드 //int cost; //가중치를 가지는 엣지에 사용된다. }; </source> 위의 struct Edge가 하나 이상 있는 것이 바로 그래프이다. ===== 순회 알고리즘 ===== 그래프를 순회하는 방법이다. 각 방법마다 장단점이 있으니 상황에 따라 적절한 알고리즘을 선택하는 것이 중요하다. ====== 깊이 우선 탐색 ====== Depth First Search, DFS ====== 너비 우선 탐색 ====== Breadth First Search, BFS ==== 트리 ==== ===== 구현과 순회 ===== ===== 이진 검색 트리 ===== === 문자열 === == 기초 정렬 알고리즘 == 정렬 알고리즘은 크기순, 사전순과 같이 정렬하는 알고리즘을 말한다. 효율적인 알고리즘들 중 대부분은 데이터가 사전에 정렬되어 있을 것을 요구하는 것이 많다. {{YouTube|kPRA0W1kECg}} {{ㅊ|뿅뿅뿅뿅뿅}} 일단 이걸 보고 뭘 배우면 좋을 지 생각해보자. 영상을 보다보면 마지막의 보고(Bogo) 정렬은 결과를 보여주지 않는걸 보고 의아해 할 수도 있는데, 보고 정렬은 모든 값을 랜덤하게 줄세우는걸 반복하다보면 '''언젠가는''' 정렬이 된다는 식으로 동작하는 알고리즘이라서 그렇다(...) 알고리즘의 구성도 랜덤배치->정렬여부 확인의 무한루프. 당연하지만 효율성은 바닥을 긴다. 잘하면 한방에 정렬되지만, 영원히 정렬되지 않을 수도 있다. [[기글 하드웨어]]의 한 유저가 10개의 값으로 테스트하니 결과를 보기까지 '''4천만번'''의 읽기작업이 수행되었다고 한다.<ref>http://gigglehd.com/zbxe/10760945</ref><s>설마 이런데도 배우고 싶다고는 안하겠지?</s> === 거품(Bubble) 정렬 === 세상에서 가장 만만한 정렬(...) 바로 뒤의 원소와 비교해 더 크다면 뒤로 간다. 구현이 쉬운 만큼 성능이 '''구리다'''. 알고리즘이 쉬워서 입문용으로 나오는거지 사실 정렬이 되어있든 아니든 대체적으로 느리고 캐시도 못 타고 여러모로 안 좋다. 공부할 목적으로만 쓰고 실제로 정렬을 돌려야한다면 쓰지 말자. <source lang="C"> int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; void sort() { int i, j; for(i = 0; i < 10; i++) for(j = i; j < 9; j++) if(arr[j] > arr[j + 1]) //j번째 원소가 다음 원소보다 크다면 바꾼다. { arr[j] = arr[j] ^ arr[j + 1]; arr[j + 1] = arr[j] ^ arr[j + 1]; arr[j] = arr[j] ^ arr[j + 1]; } } </source> ==== 선택(Selection) 정렬 ==== ==== 삽입(Insertion) 정렬 ==== == 다음 단계로 == 축하한다. 우리는 일단 밑바탕을 배운것이다. 이제 [[그럭저럭 배우는 프로그래밍/알고리즘|''다음 단계'']]로 넘어갈 차례이다. 이제부터 슬슬 긴장해야 한다. [[작성중]] {{각주}} {{쉽게 배우는 프로그래밍 입문}} 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:-- (원본 보기) (준보호됨)틀:YouTube (원본 보기) (준보호됨)틀:YouTube/styles.css (편집) 틀:Youtube (편집) 틀:ㅊ (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:고지 상자 (원본 보기) (보호됨)틀:쉽게 알 수 있다 시리즈 (편집) 틀:인용문2 (원본 보기) (준보호됨)틀:취소선 (원본 보기) (준보호됨)틀:탭 (원본 보기) (준보호됨)틀:탭/styles.css (편집) 이 문서는 다음의 숨은 분류 1개에 속해 있습니다: 분류:유튜브 영상이 포함된 문서