juju의 컴공일지

📌정렬 Sorting 주어진 레코드를 원하는 키 필드 값의 순서대로 나열하는 작업 ✔️내부 정렬 (Internal Sort) 레코드의 리스트를 주메모리에서 처리 레코드의 수가 메모리에 모두 적재될 정도로 적으면 내부 정렬로 충분 ✔️외부 정렬 (External Sort) 하드 디스크와 같은 별도의 보조 기억장치를 사용하여 처리 레코드의 수가 주메모리의 크기보다 많을 경우 외부 정렬 + 내부정렬 필요 ❓성능은? 키 값의 비교 횟수, 데이터 이동 횟수에 의해 평가됨 ✔️대표적인 내부 정렬 알고리즘 종류 선택 정렬 (Selection Sort) 버블 정렬 (Bubble Sort) 삽입 정렬 (Insertion Sort) 퀵 정렬 (Quick Sort) 쉘 정렬 (Shell Sort) 힙 정렬 (Heap Sor..

📌 수식( Expression )의 구성 연산자 ( Operator ) + 피연산자 ( Operand ) ✔️ 연산자의 종류 산술 ( Arithmetic ) 논리 ( Logical ) 대입 ( Assignment ) ✔️ 피연산자의 종류 변수 ( Variable ) 상수 ( Constant ) 👉 수식의 표기법은 피연산자에 대한 연산자의 위치에 따라 나뉜다 표기법 수식 중위 표기법 ( Infix ) a / b - c + d * e - a * c 후위 표기법 ( Postfix ) a b / c - d e * + a c * - 전위 표기법 ( Prefix ) - + - / a b c * d e * a c ❗️ 중위 표기법 -수식 안에 여러개의 연산자가 존재할 경우 -각 연산자의 연산 순위가 높은 부분이 우선..

📌 스택 Stack 선형 리스트의 특별한 형태 책 또는 접시 같은 것들을 쌓아두었다고 생각 접시를 쌓을 때 쌓게 되면 맨 위에 쌓고 뺄 때도 맨 위에서 빼게 된다는 것 기억 👉 Stack 은 LIFO Last In First Out : 나중에 들어간 원소가 가장 먼저 나온다 ❓어디에 사용 함수 호출 관리, function call , 문법 검사 syntax checking , 연산식 평사 expression evaluation ✔️ push : 원소를 추가하는 연산 ✔️ Pop : 원소를 삭제하는 연산 연산 Stack ( 0,1,2,3,4,5) top 초기 상태 -1 PUSH a a 0 PUSH b a b 1 PUSH c a b c 2 POP c a b 1 PUSH d,e a b d e 3 POP e a..

📌 다차원 배열 (multi-dimensional array) 2차원 이상의 배열 ex) A[10][9][8] => 선언된 총 배열원소의 개수는 10 * 9 * 8 = 720 ✔️ 행 우선 순서 row-major ✔️ 열 우선 순서 column-major 행 우선 열 우선 A[0][0] A[0][0] A[0][1] A[1][0] A[1][0] A[2][0] A[1][1] A[0][1] A[2][0] A[1][1] A[2][1] A[2][1] 👉 int A[3][2] 일 경우 열 우선 순위는 가장 왼쪽 차원의 인덱스 값이 증가 행 우선 순위는 가장 오른쪽 차원의 인덱스 값이 증가 ✔️ 배열의 표현 및 주소는 base address a, 각 원소의 s 바이트 할당, 👉 A[n][m]으로 선언된 2차원 배열에..

✔️시간 복잡도 (Time Complexity) 프로그램이 수행을 완료하는데 걸리는 시간 👉 컴파일 시간 (Compile Time) 👉 실행 시간 (Execution Time) 컴파일은 완료되고 나면 더 이상 수행이 되지 않으므로 시간 복잡도 평가에서 더 중요한건 ❗️실행 시간이다 ✔️시간 복잡도 계산 물리적인 프로그램 실행 시간을 측정하는 것도 가능 but 측정하는 하드웨어 환경에 따라 결과가 달라질 수 있음 => 실제 수행 시간보다 실행해야 할 명령문의 수를 세어 시간 복잡도를 계산하는 방법 => 객관적 ❓명령문의 수를 측정하는 방법 1. 카운터 변수 (Counter variable) 를 프로그램 내에 포함시켜 측정 2. 실행 명령문 표 (Execution step count table)을 사용하여 ..

📌 Performance Evaluation 설계한 프로그램이 구현되면 성능 평가가 필요 ✔️프로그램이 requirement 만족하는가 ✔️오류 없이 올바르게 동작하는가 ✔️효율적으로 구현 되었는가 📌 성능 분석 기준 👉 공간 복잡도 (space complexity) 프로그램이 수행을 완료하는데 필요로 하는 메모리의 양 (memory space) 👉 시간 복잡도 (time complexity) 프로그램이 수행을 완료하는데 걸리는 시간 (computation time) ✔️공간복잡도 (space complexity) 알고리즘 실행에 필요한 메모리 공간의 양 요구하는 시점에 따라 2가지 공간으로 나뉜다 👉 고정 메모리 공간 (fixed memory space) 프로그램이 실행되기 전 결정되는 요소 ex) 프..

✔️ 하노이타워 📌 조건 1. 한번에 하나의 원판만 옮길 수 있다 2. 큰 원판이 작은 원판 위에 올라 갈 순 없다 👉 알고리즘은 다음과 같다 세개의 기둥 A,B,C 가 있고 기둥 A 에서 B로 n개의 원판을 옮긴다고 할 때 1. 기둥 A에서 n-1개개의 원판을 C로 먼저 옮긴다 2. 기둥 A에 남은 1개 B로 옮긴다 3. 기둥 C에 있는 n-1개의 기둥을 재귀함수를 이용해 기둥 B로 옮긴다 (1-2번처럼) ❗️이 알고리즘은 원판의 수가 n개일 때 2^n -1 이동 횟수 필요 원판의 수가 1개라면 기둥 a->b 로 이동시키고 종료 원판의 수가 2개 이상이라면 n-1개의 원판을 기둥 c->b로 이동시킴 c = 6-a-b (Ex. a=1,b=2 일때 c 는 6-1-2=3번기둥이다) // #include in..

이진탐색이 생각보다 굉장히 중요하다고 들었다 자료구조의 초반에 나오지만 어쩌면 기본 중에 기본이고 기업 코딩 테스트에서들도 이를 기반으로 한 테스트들이 나온다고 하던데 🤔 ✔️ 순차 탐색 알고리즘 (sequential search) 어떤 항목을 찾기위해서 가장 단순하게 탐색하는 알고리즘 원하는 항목을 찾을 때까지 순차적으로 다음 항목과 반복해서 비교하는 방법 장점 👉 항목들이 정렬될 필요없이 바로 적용 가능 단점 👉 탐색 성능 편차가 심함 (정렬이 되어 있을 때랑 안 되어 있을 때) 평균 비교 횟수 👉 n/2 ✔️ 이진탐색이란 (Binary Search) 정렬된 데이터들에서 중간값(median)과 크기를 비교하고, 그 결과에 따라서 발견이 될 것 같은 가능성이 있는 리스트에서만 이 과정을 반복하는 탐색 ..

✔️ 재귀호출 (recursion) 함수가 실행 중 자기 자신을 다시 호출하는 것 👉 시스템 입장에서는 함수 실행 중에 새로운 함수가 불리는 것과 동일 (프로그래머가 볼 때는 아, 재귀 함수구나! 알 수 있지만 ~) 👉 이럴 때 기존에 수행중인 함수의 context인 지역변수(local variable) , 복귀주소(return address) 등의 정보를 활성 레코드(activation record)에 저장하여 보관하여야 한다 ❓활성 레코드란? 함수의 환경 정보를 담고 있는 구조체이다. 실행되는 함수마다 1개씩 생성되어 시스템 스택(system stack) 에서 저장, 관리됨 , ❓시스템 스택이란? 함수 호출(procedure call) 을 관리하기 위해 os운영체제에서 사용하는 스택을 말한다. 활성레..

지금까지 배운 구조체 struct 와 배열 array을 이용하여 볼링게임 코드를 짜보자 📌 Question 볼링의 규칙은 다음과 같다 1. 스트라이크 : 이후 2번의 공을 던져서 넘어진 핀의 수를 더해서 계산 2. 스페어 : 이후 던지는 공의 점수를 더해서 계산 3. 1번과 2번에 해당 안되면 해당 때에 넘어진 핀 수 더해서 계산 4. 마지막 10프레임에 스트라이크 또는 스페어 처리가 되었다면 한번 더 던질 수 있음 => game 구조체 선언 후 이 구조체 내에 배열을 선언하자 #define MAX_GAME 10 #define STRIKE 0 #define SPARE 1 #define NONE 2 #include typedef struct game{ int first; int second; int res..