알고리즘 공부하며 나온 개념, 규칙들 정리

구조적 프로그래밍(structured programming)
하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법.

단축 평가(short circuit evaluation)
논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피연산자의 평가를 수행하지 않는 것. (ex : ||에서 왼쪽이 true, &&에서 왼쪽이 false)

드모르간 법칙(De Morgan's laws)
각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.

x && y와 !(!x || !y)는 같다.
x || y와 !(!x&&!y)는 같다.

자료구조
자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법.

제한자 종류

• public : 모든 접근 허용
• protected : 같은 패키지(폴더)의 객체, 상속 관계의 객체 허용
• default : 같은 패키지(폴더)의 객체 허용
• private : 현재의 객체 안에서만 사용

접근 제한자 사용

• 클래스 : public, default
• 생성자 : public, protected, default, private
• 멤버 변수 : public, protected, default, private
• 멤버 메서드 : public, protected, default, private
• 지역 변수 : 접근제한자 사용 불가

난수

• Math.random()*n+m
• import java.util.Random;  Random rand = new Random();  rand.nextInt(n);
  난수는 seed라는 수의 값을 바탕으로 여러 연산을 수행하여 얻는다. Random 클래스에서는 48비트의 seed를 사용, 이 seed는 선형합동법이라는 계산법에 의해 특정 수(난수)로 바뀐다.
  

  Random rand = new Random();
  Random rand = new Random(seed);​

  • nextBoolean(), nextInt(), nextInt(n), nextLong(), nextDouble(), nextFloat()

정수 상수(10, 16, 8진수)

28		//10진수 28
0x1C		//10진수 28에 대한 16진수 표기 (1*16 + 12*1)
034		//10진수 28에 대한 8진수 표기 (3*8 + 4*1)

 

증감연산자

• 전위형 증감 연산자(++a, --a)
  식 전체를 평가하기 전체 피연산자의 값을 증가/감소시킨다.
• 후위형 증감 연산자(a++, a--)
  식 전체를 평가한 후에 피연사자의 값을 증가/감소시킨다.

소수
자신과 1 이외의 정수로 나누어떨어지지 않는 정수.

2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않는다. (n : 정수)
= n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는다.

한 해의 경과 일 수

m월 d일의 그 해 경과 일 수 = 1월, 2월, ..., m-1월의 일 수의 합 + d
(2월의 일 수는 평년은 28일, 윤년은 29일)

*지구가 태양 둘레를 한 바퀴 도는 일 수는 정확히 365일이 아님. 이를 조정하기 위해 4로 나누어떨어지는 해를 윤년으로 하여 1년을 366일로 계산. 하지만 그래도 정확하지 않으므로 100으로 나누어 떨어지고 400으로 나누어떨어지지 않는 해는 평년으로 한다.

다차원배열

int[][] x;		//x는 int[]형 배열을 가리키는 참조변수
x[0] = new int[4];	//x[0]은 int형 배열을 가리키는 참조변수
x[1] = {1, 2, 3, 4}	//x[1]은 int형 배열을 가리키는 참조변수,
x[0][0] = 5;		//x[0][0]은 int형 데이터(int형 배열의 요소)

 

메서드의 종료조건을 잘 파악하자.
1) 탐색 중에 찾고자 하는 요소가 있을 경우 (탐색 성공)
2) 탐색 끝까지 찾고자 하는 요소가 없을 경우 (탐색 실패)

for문/while문이 필요한 각각의 상황을 잘 구분하자.
ex) 특정 횟수만큼 반복해야함 => for문 사용 / 인덱스 접근은 필요없고 요소를 읽기만 할 용도 => for-each문

무한 루프는 반드시 탈출 조건인 if문이 있어야 함. (if조건 만족할 경우 break 혹은 return)

while(true){
	//...
}

for(;;){
	//...
}

do{
	//...
}while(true);

 

용도나 목적, 실행 속도, 자료구조 등을 고려하여 프로그램에 적합한 알고리즘을 선택하자.
ex) 추가/삭제가 자주 발생하는가? 단순히 검색만 수행하는가?

검색 알고리즘
데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘.

• 선형 검색(순차 검색) : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
• 이진 검색 : 일정한 규칙으로 정렬된 데이터 모임에서 아주 빠른 검색을 수행
• 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
  
  
• 배열
• 선형 리스트
• 이진검색트리

보초법

복잡도(complexity)
알고리즘의 성능을 객관적으로 평가하는 기준.

1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것 (=실행시간)
2. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것 (=메모리)
   => 적은 메모리로, 짧은 시간안에 수행하는 것이 목표

빅오표기법
O(n) : 'O-n', 'Order n', 'n의 Order'
n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)으로 표기 (n: 데이터 수)
데이터 수 n과 관계없이 한 번만 실행하는 경우 복잡도는 O(1)
컴퓨터에서 O(n/2)와 O(n), 또는 O(100)과 O(1)의 시간차는 무의미하다.

O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
*2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선.

 

 

---

• 출처 : 자료구조와 함께 배우는 알고리즘 입문 (자바 편) / Bohyoh Shibata / 이지스퍼블리싱