본문 바로가기

Programming/Algorithm

(6)
[C언어] assign 연산자의 return 값을 활용한 string copy 함수 만들기 assign 연산자는 variable 에 값을 assign 할 뿐만 아니라 값을 return 한다. assing 연산자가 return한느 값은 바로 assign 한 값이다. (Rvalue, Right-Hand Side Value) 따라서 문자열 복사 ( string copy ) 함수를 C언어에서 다음처럼 구현할 수 있음. #include void str_copy(char* s, char*d){ while((*d++=*s++)!=0); } void main(void) { char a[5]; char b[5] = "ABCD"; str_copy(a, b); printf("%s\n%s\n", a, b); } 1) str_copy 함수는 source 문자열과 destination 문자열의 시작 주소를 s랑 d라는..
[C언어/파이썬] Insertion Sort Algorithm C와 Python으로 구현해보기 - 배열 맨 처음 정렬된 부분에 정렬되지 않은 다음 항목들을 반복적으로 삽입하는 방식이다. - 즉 미리 정렬된 리스트에 새 항목을 추가할 때 좋은 정렬 알고리즘이다. - 데이터의 크기가 작고 리스트가 이미 정렬되어있으면 다른 merge sort 나 quick sort 같은 고급 알고리즘보다 성능이 좋음 - 최선의 경우 시간복잡도 O(n) - 평균과 최악의 경우 시간복잡도 O(n^2) 1. insertion sort ( 삽입 정렬 ) 알고리즘 process index 0 1 2 3 4 5 11 3 28 43 9 4 를 정렬한다고 가정 outer loop i : 0 ~ 5 0 번부터 5번 인덱스 i 가 차례로 리스트에 추가된다고 가정한다. 인덱스 i 가 추가될 때에는 0~ i-1 까지는 정렬되어 있다고 가정..
[문제해결 알고리즘] BFS :: 연습문제 :: 미로탈출 로봇 대회(정올) :: C언어 0. 문제 설명 정올에서 미로탈출 로봇 대회를 개최하였다. 대회에 사용되는 미로는 가로(X), 세로(Y) 100이하의 크기이며, 미로를 한 칸 이동하는 데는 1초가 걸린다. 대회에 참가중인 민성이는 자신의 로봇이 가장 빨리 미로를 탈출하기 위해 미로의 모양을 입력받아서 도착점까지 가장 빠른 길을 찾으려고 한다. 프로그램을 작성하여 민성이를 도와주자. 입력 형식 첫줄에 미로의 크기 X, Y(1≤X, Y≤100)가 주어진다. 둘째 줄에 출발점 x, y 좌표와 도착점 x, y 좌표가 공백으로 구분하여 주어진다. 셋째 줄부터 미로의 정보가 길은 0, 벽은 1로 공백이 없이 들어온다. 출력 형식 첫줄에 출발점에서 도착점까지 가장 빠른 시간을 출력한다. 입력 예시 8 7 1 2 7 5 11111111 0000011..
[문제해결 알고리즘] BFS :: 너비우선탐색의 개념 0. BFS란? i. Breadth-First Search, 너비 우선 탐색을 말한다. 모든 경로를 탐색할건데, 각 경로를 깊게 방문하지 않고 넓게 방문할거라는 느낌만 우선 가져보자~ ii. 모든 경우의 수를 다 훑는 알고리즘이다. ( 정답을 찾을때까지 ) 모든 경우의 수를 다 탐색하는 알고리즘에는 DFS 와 BFS 가 있다. 깊이 우선 탐색(Depth-First Search)는 한 경로에 대한 탐색을 우선 완료한 다음 다른 경로를 탐색하지만, 너비 우선 탐색은 경로상 어느 정점(node)에서 다음에 방문할 수 있는 모든 경우의 노드를 전부 방문하고, 그 다음 단계로 넘어간다. (따라서 내가 이해한 바로는 몇번째 방문할 노드인지에 따라 각 노드에 Hierarchy(계층 수준)이 부여되기도 한다.) 그리고..
두 수의 최대 공약수를 구하는 알고리즘 - 유클리드 호제법의 파이썬 구현과 수학적 증명 두 수의 최대공약수를 구하는 방법? 중학교때 가장 일반적으로 배우는 방법은 두 수가 서로소가 될때까지 공통 약수로 나눠간 후 공통 약수들을 곱하여 구하는 것이다. 그치 그치 그게 제일 흔하고 직관적이지! 그런데 컴퓨터로 구현시 더 간단한 알고리즘이 있다! 바로바로 유클리드 호제법. 더 간단하지만 살짝은 추상적이다. 호제법은 서로 나눈다라는 뜻이다. 유클리드 호제법은 두 수를 서로 나누어 가며 최대공약수를 구하는 방법이다. 두 수의 최대공약수는, 두수를 서로 나눈 나머지와 두 수중 더 작은 수의 최대공약수와 같다. 그래서 두 수를 나머지가 0이 될때까지 서로 나눠가며 그 나머지끼리 최대공약수를 구하는 것이다. 예를 들어 48과 64를 생각해보면... 64와 48의 최대공약수 = 64 % 48 과 48의 최..
[코딩 알고리즘/Prime Number] 에라토스테네스의 체(Eratosthenes' Sieve) : 소수(Prime Number)를 구하는 알고리즘 최근에 코딩을 공부하기 위해서 친구가 추천해준 프로젝트 오일러(Project Euler)의 문제를 순서대로 풀고 있는 중이다. 개인적으로 프로젝트 오일러는 새로운 코딩 언어를 익히기 위해서 굉장히 좋은 도구라고 생각한다. 여기서 문제를 풀면서 다양한 조건문/반복문 사용뿐만 아니라 dynamic programming과 recursive programming 또한 연습할 수 있기 때문이다. 프로젝트 오일러 : https://projecteuler.net/about About - Project Euler The page has been left unattended for too long and that link/button is no longer active. Please refresh the page. pr..