class Main{
public static void main(String[] args){
int i = 1;
System.out.println(i+3); //예1) 연산자와 피연산자로 구성
System.out.println(f()); //예2) 피연산자 없이 수식 구성
System.out.println(-5.3); //예3) 연산자 없이 수식 구성
}
public static int f(){
return 100;
}
}
02. 수식과 문장의 차이
수식: 값을 나타내는 표현
문장: 처리를 나타내는 표현
처리: 값 계산, 수행 흐름 바꾸기, 값을 화면에 출력 등
예) Python
#수식이면서 문장
3+2
#문장(어떤 하나의 값을 표현하지 않기 때문에 수식은 아님)
if k > 1:
k = 1
단계적인 조리 절차를 따르면 음식을 만들 수 있듯이, 주어진 문제도 단계적인 풀이 절차("알고리즘")를 따르면 문제의 해를 구할 수 있음
맛있고 좋은 음식 ↔ 효율적인 알고리즘
주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것
입출력: 0개 이상의 외부 입력, 1개 이상의 출력
명확성: 각 명령은 모호하지 않고 단순 명확해야 함
유한성: 한정된 수의 단계를 거친 후에는 반드시 종료해야 함
유효성: 모든 명령은 컴퓨터에서 실행 가능해야 함
(실용적 관점) 효율성
➡️ 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것
✅ 알고리즘 생성 단계
설계
표현/기술
기술 방법
일상언어
의사코드
순서도
정확성 검증
효율성 분석
✅ 자료구조와 알고리즘의 관계
자료구조
데이터 사이의 논리적 관계를 표현하고 조직화하는 방법
배열, 연결 리스트, 스택, 큐, 트리, 그래프
"효율적" 프로그램 ← 자료구조+알고리즘
자료구조에 대한 고려 없는 효율적인 알고리즘의 선택 또는 알고리즘에 대한 고려 없는 효율적인 자료구조의 선택은 무의미
02. 알고리즘 설계
🔸최대값 찾기
두 알고리즘 모두 비교 횟수가 7번으로 효율성이 같음.
Q. 어떤 수의 최대/최소값을 찾기 위해 몇 번의 비교가 필요할까? A. n→(n-1) 두 개의 데이터 중 최대값을 찾으려면 1번 비교, 세개의 데이터 중 최대값을 찾으려면 2번 비교...
🔸뒤섞인 카드에서 원하는 카드 찾기
🔸순서대로 나열된 카드에서 찾기
✅ 알고리즘 설계 기법
문제와 그에 따른 조건 등이 매우 다양 → 일반적이고 범용의 설계 기법은 없음
대표적인 설계 기법
분할정복(divide-and conquer)방법
동적 프로그래밍(dynamic programming)방법
욕심쟁이(greedy)방법
🔸분할정복 방법
순환적으로(recursively) 문제를 푸는 방법
문제의 입력을 더이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법
특징
분할된 작은 문제는 원래 문제와 동일, but 입력 크기만 작아짐
분할된 작은 문제는 서로 독립적
각 순환 호출마다 세 단계의 처리 과정을 거침
분할
주어진 문제를 여러 개의 작은 문제로 분할한다.
정복
작은 문제를 순환적으로 분할. 만약 작은 문제가 더이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구한다.
결합
작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다. ※결합 단계가 없는 문제도 존재
예) 퀵 정렬, 합병 정렬, 이진 탐색
🔸동적 프로그래밍 방법
최적화 문제의 해를 구하기 위한 상향식 접근 방법
문제의 크기가 작은 소문제에 대한 해를 구해서 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만듦
예) 모든 정점 간의 최단 경로를 구하는 플로이드 알고리즘
🔸욕심쟁이 방법
해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 각 단계에서 '가장 최선'이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라고 희망하는 방법
희망 → 각 단계의 최적해를 통해 전체적인 최적해를 만들어 내지 못할 수 있음
적용 범위는 제한적, 간단하면서도 강렬한 설계 기법
예) 거스름돈 문제, 배낭 문제
▪️ 거스름돈 문제
고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제 동전의 종류 → 500원, 100원, 50원, 10원
▪️ 배낭 문제
최대 용량 M인 하나의 배낭, n개의 물체
각 물체 i에는 물체의 무게 wᵢ와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pᵢ
배낭의 용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾는 문제
가정 → 물체를 쪼개서 넣을 수 있다
물체의 무게가 가벼운데 이익이 큰 놈부터 집어넣으면 됨. 단위 무게당 이익이 큰 놈부터!!
03. 알고리즘 분석
🔸정확성 분석
유효한 입력, 유한 시간 → 정확한 결과 생성
다양한 수학적 기법을 사용한 이론적 증명이 필요 (교과 과목을 통해 배우는 알고리즘은 정확성 검증 완료!)
🔸효율성 분석
알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
메모리 양: 공간 복잡도(space complexity)
cpu 수행 시간: 시간 복잡도(time complexity)
✅ 시간 복잡도
▪️ 알고리즘의 수행 시간
컴퓨터에서 실행시켜 완료될 때까지 걸리는 실제 시간을 측정
컴퓨터의 종류와 속도, 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 종속적 → 일반성 결여!
"알고리즘에서 단위 연산의 수행 횟수를 모두 더한 값"
입력 크기가 증가하면 수행 시간도 증가
단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현
예) f(n) = 2n^2+5n+10
입력 데이터의 상태에 종속적
평균 수행 시간: 모든 데이터가 입력될 수 있는 경우를 고려
최선 수행 시간: 어떤 데이터가 주어졌을 때 가장 빠른 수행 시간
최악 수행 시간: 데이터의 상태가 알고리즘과 안 맞아서 가장 오래 걸리는 수행 시간
✅ 점근성능
▪️ 입력 크기 n이 충분히 커짐에 따라 결정되는 성능
알고리즘을 수행하는데 수행되는 명령어들의 횟수 → 값이 작을 수록 좋은 알고리즘
▪️ 다항식의 수행 시간에서 가장 큰 영향을 미치는 것: 최고차항
계수 없이 '최고차항'만을 이용해서 표현
수행 시간의 어림값, 수행 시간의 증가 추세 → 알고리즘의 우열
🔸 점근성능의 표기법
알고리즘 수행시간 f(n)이 아무리 나빠도 cg(n)보다 나빠질 수 없음 → 최악의 수행 시간
최선의 수행 시간
최선과 최악의 시간을 동시에 표기
예)
▪️ 데이터 입력 크기가 증가해도 수행 시간 증가가 크지 않은 알고리즘이 BEST
04. 정렬 알고리즘
:선택 정렬, 버블 정렬, 삽입 정렬
📌 분포 기반 정렬이 성능이 더 좋은 이유 분포 기반 정렬은 내가 정렬하고 싶은 데이터가 어떤 분포적인 특성을 가지고 있는지에 대한 정보를 사전에 알고서 그걸 정렬에 활용→ 성능은 좋으나 일반성이 떨어짐(보통 정렬할 때 해당 데이터가 통계적으로 어떤 분포 특징을 가지고 있는지 잘 모름)
▪️ 정렬을 위한 기본 가정
✅ 선택 정렬
주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식(오름차순)
✅ 버블 정렬
왼쪽에서부터 모든 인접한 두 데이터를 차례대로 비교하여 왼쪽의 값이 더 큰 경우에는 오른쪽 값과 자리를 바꾸는 과정을 통해 정렬
예1예2
입력 데이터가 8개니까 7번(8-1)의 단계를 수행하는데 4단계부터는 자리바꿈이 발생하지 않음! == 6, 7단계는 확인하지 않아도 됨(이런 팁을 알고리즘에 적용할 수 있음)
🔸버블 정렬의 특징
선택 정렬에 비해 데이터 교환이 더 많이 발생 → 선택 정렬보다 비효율적
데이터의 입력 순서에 따라 성능이 달라짐
✅ 삽입 정렬
주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은 데이터를 바른 위치에 '삽입'해서 나열하는 방식
입력 배열을 정렬 부분과 미정렬 부분으로 구분
미정렬 부분의 가장 왼쪽에 있는 데이터("첫번째 데이터")를 꺼낸 후, 정렬된 부분에서 제자리를 찾아 삽입하는 과정을 반복
//스택 동적 변수의 배열 크기 정적 바인딩 in C++
char arr[5];
//스택 동적 변수의 배열 크기 동적 바인딩 in C
int n = 5;
char arr[n];
//힙 동적 변수의 배열 크기 동적 바인딩 in Java
char[] arr = new char[5];
//Perl 원소 참조
$walk{'Sun'};
//Perl 원소 추가, 원소 삭제
$walk{'Thu'} = 3000;
delete $walk{'Mon'};
//C++ 원소 참조
walk['Sun'];
//C++ 원소 추가, 원소 삭제
walk.insert({"Thu", 3000});
walk.erase("Mon");
04. 구조체와 공용체
✅ 구조체(structure type)
= 레코드형(record type)
데이터의 모음으로 구성된 타입
원소: 동질형/이질형 모두 가능
각기 다른 타입의 데이터라도 서로 연관이 있다면 모아놓은 것
각 원소는 이름으로 구별
이름: 각 원소의 타입으로 선언된 변수명
🔸데이터 집합
각 원소의 타입에 해당하는 데이터 집합들이 모인 집합
원소의 개수와 각 원소의 타입에 따라 다양한 타입 존재
각 원소의 타입: 단순타입, 복합타입 모두 가능
🔸연산 집합
초기화, 대입 연산
✅ 공용체(union type)
저장공간을 공유하는 데이터의 모음으로 구성된 타입
원소들의 구성 형태는 구조체와 유사함 → 각 원소는 이름으로 구별
하나의 공간을 같이 쓰기 때문에 공간 절약 가능하지만 한 원소의 값이 변경되면 다른 원소들이 영향을 받음
🔸데이터 집합
각 원소의 타입에 해당하는 데이터 집합의 합집합
각 원소의 타입에 따라 다양한 타입 존재
각 원소의 타입: 단순타입, 복합타입 모두 가능
//C, C++ → union
union uni
{
int i;
char a;
double f;
};
특정 타입의 데이터를 가지고 연산을 하면 그 연산의 결과도 항상 해당 데이터 집합 안에 존재해야 됨!
나머지 연산: mod, % (예: 7 mod 3 = 1)
비트 연산: ^, &, | 등
관계 연산: <, >, <=, >=, == != 등 → 연산의 결과 값은 논리형
✅ 실수형: 실수 데이터를 다루는 타입
🔸데이터 집합
-100.05, -8.7, 0.0, 1.234, 256.3500187 등
전체 실수 중 사용 비트의 크기에 따라 일부 범위의 실수만 표현 가능
일반적으로 부동소수점 수(floating-point number) 로 표현
📌 부동소수점 수
출처: 방송통신대학교
부호: 양수 = 0, 음수 = 1
지수부: 지수 + bias
bias는 지수부의 크기에 따라 결정됨
(2^m-1)-1
가수부: 소수점 이하 부분만 표현
가수부는 1.xxxx 형태를 갖도록 정규화를 거침
💡정수 5 vs 실수 5.0
short a = 5; //0 0000000000000101 float b = 5.0; //0 101 0100000000000000000
🔸연산 집합
사칙연산: 덧셈, 뺄셈, 곱셈, 나눗셈 → 연산 결과 값도 동일한 실수형 (예: 1.5 + 2.5 = 4.0)
float의 경우, 5E37*10.0 == 최대값 초과 → 무한대 inf
관계 연산: <, >, <=, >=, ==, != 등 → 연산 결과 값은 논리형
✅ 문자형: 하나의 문자 데이터를 다루는 타입 ('A', 'a'...)
🔸데이터 집합
ASCII: 특수기호, 구두점, 숫자, 영어 대소문자 등 128개의 문자로 구성
C, C++: char == 8비트
유니코드: 전 세계의 다양한 문자 표현 가능
Java: char == 16비트
🔸연산 집합
관계 연산: 연산의 결과 값은 논리형
'A' < 'B' == true
C, C++는 char 타입을 8비트 정수형으로 간주 → 사칙연산, 비트연산 등 가능
'A' + 32 == 65+32 → 97 == 'a'
'a' - 32 == 97-32 → 65 == 'A'
✅ 논리형: 참과 거짓의 논리 데이터를 다루는 타입
🔸데이터 집합
true(참), false(거짓)
C: _Bool = {0, 1}
C++: bool = {true, false}
Java: boolean = {true, false}
🔸연산 집합
논리곱(and), 논리합(or), 논리부정(not) 등
연산 결과 값도 동일한 논리형 → ture && false == false
✅ 열거형: 순서 관계가 있는 이름들을 데이터로 다루는 타입
🔸데이터 집합
사용자가 직접 지정한 이름들
각 이름은 0이상의 정수와 대응 → 순서 관계 성립
예) C, C++ enum 타입
/*
열두 달의 이름
개발자 입장에서는 이름을 사용했지만 컴퓨터 내부에서는 나열된 순서대로 이름마다 숫자를 대응
enum Year {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
*/
enum Year {Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec};
//각 이름에 대응되는 정수도 사용자가 지정 가능
enum Year {Jan=1, Feb, Mar, Apr=10, May=15, Jun=1, Jul, Aug, Sep, Oct, Nov, Dec};
🔸연산 집합
관계 연산: 연산 결과 값은 논리형
C: 대응되는 정수 값에 대한 사칙연산도 가능
#include <stdio.h>
int main()
{
enum Year {Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec};
enum Year Go;
for(Go=Jan; Go<=Dec; Go++)
printf("%d\n", Go); // 출력: 0 1 2 3 4 5 6 7 8 9 10 11
return 0;
}
The server cannot be started because one or more of the ports are invalid. Open the server editor and correct the invalid ports. :실행시킨 톰캣 포트 번호가 유효하지 않아서 발생한 에러
1. 이클립스 하단에 있는 서버 탭에서 등록한 톰캣을 더블클릭 한다.
2. Tomcat admin port란에 사용하지 않는 포트 번호를 입력한다. (8005, 8009...)
