Do it 자료구조와 함께 배우는 알고리즘 입문 자바편을 읽고 정리한 내용입니다.
알고리즘이란?
문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합
알고리즘 요건
알고리즘이 프로그램의 기반으로 제대로 사용되기 위해서는 다음 조건을 만족해야 한다.
- 입력과 출력 (Input/Output)
- 정확성 (Correctness)
- 유한성 (Finiteness)
- 명확성 (Definiteness)
- 유효성 (Effectiveness)
- 입력과 출력 (Input/Output)
- 외부로 부터 0개 이상의 입력을 받아들이고 1개 이상의 결과를 출력한다.
- 외부에서 받은 입력이 없는 경우에는 알고리즘 내부에서 자체적으로 생성
- 정확성 (Correctness)
- 문제에서 허용하는 범위 내에서는 모든 경우의 가능한 입력에 대해 정확한 출력을 생성해야 한다.
- 그러나, 모든 입력에 대한 테스트가 불가능하고 문제가 복잡한 경우 증명과정이 난해하고 방대하여 오류를 완전히 배제할 수 없다는 문제점이 있다.
- 명확성 (Definiteness)
- 알고리즘에 포함된 모든 명령어들과 절차는 정확하고 명료해야 한다.
- 유효성 (Effectiveness)
- 알고리즘에서 요구하는 연산은 이산적인 컴퓨터에서 처리될 수 있는 계산이어야 한다.
순서도
처리하고자 하는 문제의 수서와 상호간의 관계를 기호를 사용하여 표현한 그림
순서도의 기호
반복
어떤 조건이 성립하는 동안 반복해서 수행하는 것
while문 반복
while(제어식) 명령문- 사전 판단 반복 구조 : 실행 전 반복을 계속할지 판단
for문 반복
for(초기화부분; 제어식; 업데이트부분) 명령문- 하나의 변수를 사용하는 반복문은 while문보다 for문을 사용하는 것이 좋다.
- 사전 판단 반복 구조
do while문 반복
do문 while(제어식);- 사후 판단 반복 : do문은 루프 본문을 한 번 실행한 뒤에 반복을 계속할지 판단
사전 판단 반복과 사후 판단 반복의 차이점
- 사전 판단 반복
- while문, for문
- 처음 제어식을 평가한 결과가 0(false)면 루프 본문을 한 번도 실행하지 않는다.
- 사후 판단 반복
- do while문
- 루프 본문이 반드시 한 번은 실행된다.
구조적 프로그래밍
- 하나의 입구, 하나의 출구만 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법
- 순차, 선택, 반복 3종류의 제어흐름을 사용
논리 연산자의 단축평가
논리 연산의 식 전체 평가의 결과가 왼쪽 피연산자의 평가 결과만으로도 정확하다면 오른쪽 피연산자의 평가를 수행하지 않는 것
||왼쪽 피연산자의 평가 결과가true면 단축평가&&왼쪽 피연사자의 평가 결과가false면 단축평가
드모르간 법칙
각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다는 법칙
(x && y) == !(!x || !y);
(X || y) == !(!x && !y);다중 루프
반복문 안에 다시 반복
곱셈표
// 곱셈표
public class Multi99Tabel {
public static void main(String[] args) {
for(int i=1; i<=9; i++) {
for(int j=1; j<=9; j++) {
System.out.printf("%3d", i*j);
}
System.out.println();
}
}
}위의 코드는 다음과 같이 처리된다.
i가 1일 때 : j를 1 => 9로 증가시키면서 1 * j를 출력한다. 그리고 줄을 바꾼다.
i가 2일 때 : j를 1 => 9로 증가시키면서 2 * j를 출력한다. 그리고 줄을 바꾼다.
i가 3일 때 : j를 1 => 9로 증가시키면서 3 * j를 출력한다. 그리고 줄을 바꾼다.
i가 4일 때 : j를 1 => 9로 증가시키면서 4 * j를 출력한다. 그리고 줄을 바꾼다.
.
.- 바깥쪽의 for문(i)은 for문은 세로 방향(행)에 대한 반복이다.
- 안쪽의 for문(j)은 각 행의 가로 방향(열)에 대한 반복이다.
이를 그림으로 나타내면 다음과 같다.
직각 이등변 삼각형
// 직각 이등변 삼각형
public class TriangleLB {
public static void main(String[] args){
Scanner scan = new Sacnner(System.in);
int n;
System.out.println("왼쪽 아래가 직각인 이등변 삼각형을 출력합니다.");
do {
System.out.print("몇 단 삼각형입니까? : ");
n = scan.nextInt();
}while ( n <= 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++)
System.out.print('*');
System.out.println();
}
}
}위 코드는 다음과 같이 처리된다
i가 1 일 때 : j를 1 => 1로 증가시키면서 *를 출력한다. 그리고 줄을 바꾼다.
i가 2 일 때 : j를 1 => 2로 증가시키면서 *를 출력한다. 그리고 줄을 바꾼다.
i가 3 일 때 : j를 1 => 3로 증가시키면서 *를 출력한다. 그리고 줄을 바꾼다.
i가 4 일 때 : j를 1 => 4로 증가시키면서 *를 출력한다. 그리고 줄을 바꾼다.
.
.이를 그림으로 나타내면 다음과 같다.
Faithfulness makes all things possible!