조이의 개발 성장 다이어리

최악의 경우(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)으로..

문자열을 입력받아 그 안의 첫 번째 단어를 출력하는 프로그램을 작성하시오. 입력: 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..

Tic-Tac-Toe : 3x3으로 이루어진 게임판에서의 오목게임 O와 X를 번갈아 그리며 가로, 세로, 대각선에서 심볼 3개가 먼저 만들어지면 우승한다. 입력: Tic-Tac-Toe에 입력할 심볼의 좌표값을 번갈아 입력한다. 출력: O 혹은 X가 그려진 게임판이 출력되며 둘 중에 한명이 우승한 경우 누가 우승했는지 출력하고 종료한다. 입력 프롬트 입력값 Player X(행 열): Player O(행 열): Player X(행 열): Player O(행 열): Player X(행 열): 1 1 0 0 0 1 1 0 2 1 입력 프롬트 입력값 Player X(행 열): Player O(행 열): Player X(행 열): Player O(행 열): Player X(행 열): 2 2 1 1 2 1 1 2 2..

입력 : 지뢰는 문자 *로 하고 일반 셀은 #로 입력 출력 : 지뢰가 설치되어 있지 않은 셀 위치에 주변 지뢰의 개수 출력 EX) 입력 : ##### #*### ##*## #*### ###*# 출력: 11100 1*210 23*10 1*321 112*1 입력과 출력할 때 모두 2차원 배열 사용 #include #define X_VALUE 5 //2차원 배열의 행의 수 #define Y_VALUE 5 //2차원 배열의 열의 수 void readBombInfo(char grid[][Y_VALUE + 1]) { int i; // grid 및 지뢰 정보 입력 for (i = 0; i < X_VALUE; i++) scanf("%s", grid[i]); } void countBomb(char grid[][Y_VAL..

#include #include #define MAX_SET_SIZE 10 #define HAVE_ELEMENT 1 #define DO_NOT_HAVE_ELEMENT 0 int hasElement(int set[], int size, int element); int setUnion(int set1[], int size1, int set2[], int size2, int setResult[]); int setIntersecton(int set1[], int size1, int set2[], int size2, int setResult[]); int setComplements(int set1[], int size1, int set2[], int size2, int setResult[]); void print..