조이의 개발 성장 다이어리

하노이탑 문제 막대 A, B, C가 있고 막대 A에 아래에서부터 크기가 큰 순서대로 원판이 쌓여있다. 막대 A의 원판들을 막대 C에 옮겨야한다. 이 때 지켜야할 3가지 조건이 있다. 한 번에 하나의 원판만 이동할 수 있다. 맨 위에 있는 원판만 이동할 수 있다. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 이 역시 앞의 조건들을 지켜야 한다. 원판이 3개일 경우 A에서 C로 이동하는 과정을 그림으로 그리면 다음과 같다. 원판의 개수가 n개라고 할 경우, 다음과 같이 단순하게 생각할 수 있다. A에 쌓여있는 위에서부터 n-1개의 원판을 B에 이동하고, 제일 밑에 있는 하나의 원판을 C로 옮긴다. 그리고 다음으로 B에 있던 n-1개의 원판을 C로 옮긴다. 이를..

순환(recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ex 1) 팩토리얼 int factorial(int n) { if (n

최악의 경우(worst case) ★ 알고리즘의 수행 시간이 가장 오래 걸리는 경우 => 시간 복잡도의 척도 최선의 경우(best case) 알고리즘의 수행 시간이 가장 적게 걸리는 경우 평균적인 경우(average case) 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 수행 시간 EX) 순차 탐색(sequential search)의 경우 ※ 순차탐색 : 찾고자 하는 항목을 배열의 첫 번째부터 마지막까지 비교하면서 찾아내는 탐색방법 최선의 경우 : 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우 : 비교 횟수가 1번이므로 O(1) 5 9 10 17 21 29 33 37 38 43 최악의 경우 : 찾고자 하는 숫자가 배열의 맨 끝에 있는 경우 : 비교 횟수가 n번이므로 O(n..

효율적인 알고리즘을 짜려면? 알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터의 자원(ex:메모리)을 덜 사용하도록 짜야한다. -> 즉, 알고리즘을 짤때 수행시간과 기억공간을 분석하여 시간 효율성과 공간 효율성을 고려해야함 공간 복잡도(space complexity) 알고리즘이 사용하는 기억 공간 분석 시간 복잡도(time complexity) ★ 알고리즘의 수행 시간 분석 => 알고리즘의 효율성을 이야기할때 주로 시간 복잡도를 고려 절대적인 수행 시간을 나타내는 것이 아닌 알고리즘을 이루는 연산이 몇 번 수행되는지를 숫자로 표시함 시간 복잡도 함수 : 연산의 수행 횟수는 보통 입력의 개수에 따라 달라지기 때문에 n에 대한 함수로 나타냄. 이 함수를 시간복잡도 함수라고 하며 T(n)으로..

프로그램 = 자료구조 + 알고리즘 자료구조(data structure) 프로그램에서 자료를 정리하여 보관하는 구조(배열, 스택, 큐...) 알고리즘(algorithm) 컴퓨터로 문제를 해결하기 위한 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 기술한 것 특정한 일을 수행하는 명령어들의 집합 알고리즘의 조건 입력 : 0개 이상의 입력이 존재해야 한다 출력 : 1개 이상의 출력이 존재해야 한다 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다 유효성 : 각 명령어들은 실행 가능한(프로그래밍 언어로 바꿀수 있는) 연산이어야 한다. 자료형 : 데이터 + 데이터 간에 가능한 연산 추상 자료형..

"프로그램 = 자료구조 + 알고리즘" 자료구조란? 컴퓨터 프로그램에서 자료들을 정리하여 보관하는 구조 예시 자료구조 물건을 쌓아서 보관하는 것 스택 마트 계산대의 대기 줄 큐 버킷 리스트 리스트 영어사전 사전 지도 그래프 컴퓨터의 디렉토리 구조 트리 알고리즘이란? 컴퓨터 프로그램에서 문제를 해결하는 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것 알고리즘이 되기 위한 조건 1. 입력 : 0개 이상의 입력 2. 출력 : 1개 이상의 출력 3. 명백성 : 각 명령어의 의미는 모호하지않고 명확해야한다. 4. 유한성 : 한정된 수의 단계 후에는 프로그램이 반드시 종료되어야 한다. 5. 유효성 : 각 명령어들은 글을 통해서 혹은 컴퓨터로 실행..

문자열을 입력받아 그 안의 첫 번째 단어를 출력하는 프로그램을 작성하시오. 입력: 123word 출력: word 입력: 123apple45pear 출력: apple #include #define TRUE 1 #define FALSE 0 int main(void) { char str[20]; char word[20]; int i, j = 0; int isFound = FALSE; scanf("%s", str); for (i = 0; str[i] != '\0'; i++) { if ((str[i] >= 'a' && str[i] ='A' && str[i]

정렬되어 있는 알파벳(모두 소문자)으로 이루어진 문자열 word1과 문자열 word2을 merge 하여 answer 배열에 넣는 함수 solution을 작성하시오. word1과 word2내에서는 문자 중복이 없으며 word1과 word2간에 중복된 문자는 둘 중 하나만 answer 배열에 넣도록 한다. 입력: abcxy dcz 출력: abcdexyz 입력: abc bcde 출력: abcde #include #include #include char answer[20]; char* solution(char* word1, char* word2) { int i = 0, idx1 = 0, idx2 = 0; //idx1: word1의 인덱스 idx2: word2의 인덱스 // word1이나 word2가 끝날 때까지..

정수 집합 a, b 에 대해서 집합 a 가 집합 b 의 subset 이면 1 아니면 0 을 리턴하는 함수 isSubset 을 정의하라. main 함수에서는 a 를 읽고(크기를 읽은 후 각각의 원소) b 를 같은 방법으로 읽고 a 가 b 의 부분집합이면 1 을 아니면 0 을 출력한다. aSize 와 bSize 는 각각 집합 a 와 b 의 크기이다. 입력 : 2 10 20 3 20 30 10 출력: 집합 A는 집합 B의 부분집합이다 입력 : 2 10 20 3 10 22 33 출력: 집합 A는 집합 B의 부분집합이 아니다 #include #define MAX_SET_SIZE 100 int hasElement(int set[], int size, int element) { int i = 0; for (i = 0..

#include #define X_VALUE 5 //2차원 배열의 행의 수 #define Y_VALUE 5 //2차원 배열의 열의 수 int main(void) { int i; int j; int grid[X_VALUE][Y_VALUE]; int n[X_VALUE][Y_VALUE] = { 0 }; // grid입력 for (i = 0; i = 0) n[i][j] += grid[i - 1][j..