조이의 개발 성장 다이어리

효율적인 알고리즘을 짜려면? 알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터의 자원(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..

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..