C언어 예술가

버블정렬(bubble sort) - 정렬 알고리즘을 배울때 보통 먼저 배우는 정렬 알고리즘 입니다. 버블정렬은 간단하기 때문에, 직관적으로 쉽게 이해할 수 있습니다. 마치 거품이 수면으로 올라오는 것 같아서 버블정렬이라고 한다네요. 버블정렬을 설명하기에 앞서 주요 정렬 알고리즘에 관한 시각적 자료를 링크하겠습니다. 정렬들간에 비교와 정렬의 특성을 파악할 수 있습니다. 버블정렬은 사람의 입장에서는 그렇게 자연스럽지 않습니다. 위 영상처럼 두 개씩 대소관계를 비교하며 위치를 바꾸어 나가는 데 컴퓨터 가 살아있다면 컴퓨터 입장에서 이러한 단순함이 오히려 쉽다고 느껴질꺼라 생각합니다. 버블 소트의 문제해결 방법은 다음과 같습니다. 1. 배열의 첫번째 요소와 두번째 요소의 대소관계를 비교한다 2. 대소관계에 따른..

하노이 탑은 재귀호출의 대표적인 예다. 또 팩토리얼 연산은 재귀호출의 기본인데, 재귀호출이 무엇인지 알아보고, 점화식과의 관계를 도출하면서 C언어로 어떻게 코딩하는 가를 살펴보는 것이 이번 포스팅의 목표다. 거창한 듯 하지만 재귀호출을 이해만 하면 모든 것이 해결된다. 재귀호출은 간단히 말해서 함수가 자신을 호출하는 경우를 말한다. factorial의 경우를 살펴보자. factorial은 일련의 수의 곱을 말한다. a!은 1부터 a까지의 곱을 말하는데, for문을 이용해 증가되는 수를 계속 결과값에 곱해서 계산할 수 있다. 그럼 두가지 방법을 살펴보자. 재귀에 대한 생각(factorial) 결과는10! = 3628800으로 같다. 함수의 호출 형태는 같지만 내부적 구조는 다르다. 환경에 따른 성능의 차이..

유클리드의 호제법은 쉽게 말해서 최대공약수를 구하는 알고리즘이다. A와 B의 최대공약수를 구한다면, A=QB+R 위 식처럼 A와 B의 관계를 나타내도록한다.(A>B) 이상태에서 다시 제수(B)과 나머지(R)의 관계를 같은 형식으로 나타내보자. B=Q'R+R' 나머지로 제수를 계속해서 나눠간다. 이렇게 반복하다보면 언젠가 제수가 딱 떨어지는 순간이 생기게된다. 생각해 보면 모든 수에대하여 성립한다. 이 때 떨어지는 순간 제수가 최대 공약수가 된다는 것이 호제법이다. 연습삼아 유클리드 호제법으로 최대공약수를 구해보자. *제수:나누는 수 *피제수:나눔을 당하는수 *나머지:나머지 GCD(3,6) 2 = 6/3...0 나머지가 0일때 제수가 3이므로 GCD는 3 GCD(8,28) 3 = 28 / 8...4 2 =..

다익스트라의 핵심은 다음글을 보기 바랍니다. 2015/06/02 - [프로그래밍/알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)최단경로 알고리즘 아래 글은 제가 오래전 다익스트라를 처음 공부할 때 쓴 글이므로 이해가지 않는 부분도 있고 많이 부족합니다. 코드만 참고하시길 바랍니다. 다익스트라 알고리즘, 이름조차 어렵다. 이 알고리즘을 이해하기위해선 깊이 우선, 너비우선 탐색을 이해해야한다. 2013/06/05 - [프로그래밍/알고리즘] - 탐색-깊이우선탐색, 너비우선탐색 2013/06/07 - [프로그래밍/알고리즘] - 위상정렬(topological sort) 다익스트라 알고리즘은 시작점을 정하고 끝점을 정하면 그 두점사이 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘의 너비우..

깊이우선 탐색과 별반 다르지않다. 하지만 알고리즘의 1%만 수정되어도 제대로 이해를 하지못한다면 완전 다르게 보일수도있다. 컴퓨터의 알고리즘이란 1%로인해 전체적이 해법과 결과물이 달라지기때문이다. 익히 말한바와 같이 깊이 우선탐색은 재귀의 진행시 계속해서 시작정점을 반환하는 탐색방법이다. 내가 쓴방법은 한번 갔던 곳은 플래그로 표시를 해두었기때문에 판정을통해 다시는 안가도록 해놓았다. 이런경우는 노드와 노드사이의 간선이 하나만 존재할때 가능한일이다. 간선이 2개이상일땐 플래그를 해놓는 방법은 유용하지않다. 직접 행렬상의 간선의 개수를 지우는 방식으로 하겠다. 또한 한붓그리기의 취지에 맞게 모든 간선을 한번에 다 지나가야하므로 판정을 간선을 다 통과했는지 해야하고 이러한 모든 방법의 수를 구하기위해선, ..

발췌 : c언어로 배우는 알고리즘

위상정렬이란 방향 그래프에서 연결되어 있는 정점을 재귀가 회귀하는 역순서로 정렬하는 것을 말한다. (재귀의 진행의 반대는 재귀의 회귀라고 하자. 진행은 스택에 쌓는작업이고 회귀는 스택을 푸는 작업이라고하자.) 내가 이해하는 대로 쓴것이다. 우선 위상정렬은 탐색과 다르게 탐색할때의 정점을 재귀의 회기시에 반환해서 정렬하는 형태를 말한다. 탐색은 정점에서 다음 노드들 다시말에 정점과 연결된 곳을 재귀진행시에 반환 했었다.(다음노드는 다음탐색의 정점이 되어서 탐색을 진행해 나간다.) 이런위상정렬을 할시 폐쇄로가 있다면 위상정렬의 해는 없어지게된다. 위상정렬을 하기위해선 우선 폐쇄로에대한 판단을 먼저 해야한다. 폐쇄로란, 특정 정점에서 시작해서 회로를 도는중 그 정점으로 돌아오는 경우 폐쇄로로 판정된다. 폐쇄로..

아래 1부터 7 까지의 노드들이 있다. 이런 노드들을 연결해놓은 아래와 같은 그림을 그래프라고한다. 트리와 그래프의 차이는 트리는 한 노드에서 또다른 노드까지 가는 방법이 1가지인데 반해 그래프는 여러가지방법이 있을 수 있다. 이제 깊이 우선 탐색을 알아보겠는데 깊이란 시작점에서 부채모양으로 퍼진형태가아닌 선형태로 탐색을 하는 것을말한다. 그림에서 1-2-4-7 , 1-2-5-6 이런식으로 탐색해 나가는것이 깊이 우선 탐색이라고 한다. 너비우선탐색은 (1-2 ,1-3) (2-4,2-5) 이런식으로 시작점을 정하면 부채꼴모양으로 가능한 연결수를 다 찾아낸후 다음 탐색을 하는 형태이다. 깊이우선탐색은 시작정점의 변경이 한번의 이동에 한번씩 된다. 하지만 너비우선탐색은 시작정점이 있으면 연결된 노드를 다 탐색..

...#include #define BW 4 #define BH 4 struct { bool ready; bool pass; int num; int x,y; }Board[BW][BH]; int setnum[17]={1,}; int main() { int i, j,temp; for (i=0;i8?temp-8:temp); //숫자가 1~8이 두번반복 setnum[temp]=true; break; } if (temp==0) { temp=1; for (;temp8?temp-8:temp); setnum[temp]=true; break; } } } } for (i=0;i

슈팅게임을 만들때 적의 이동과 총알의 생성 알고리즘이 연속해서 만들어져야 효과적으로 표현할수 있다. 그렇지않으면 코딩이 더길어진다.for 루프안에서 시분할을 할 경우 이런 자잘은 팁들은 많은 경험을 통해 얻을수 있다. //적의 생성 for ---------//적의 이동// 총알의 생성------------