Posts Do it! 자료구조와 함께 배우는 알고리즘 #1장 기본 알고리즘
Post
Cancel

Do it! 자료구조와 함께 배우는 알고리즘 #1장 기본 알고리즘

Sep 26, 2020 2020-09-26T00:00:00+08:00 by hayeon_kim
22 min

Do it 자료구조와 함께 배우는 알고리즘 1장을 읽고 푼 연습문제 코드와 내용을 정리하였습니다.

알고리즘이란?

문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합을 말한다.

  • 순차적(concatenation) 구조: 여러 문장(프로세스)이 순차적으로 실행되는 구조
  • 선택(selection) 구조: () 안에 있는 식의 평가 결과에 따라 프로그램의 실행 흐름을 변경하는 if문

System.int: 키보드와 연결된 표준 입력 스트림

stdIn: System.in에서 문자나 숫자를 꺼내는 장치

세 값의 최댓값

Q1. 네 값의 최댓값을 구하는 m4 메서드를 작성한다.

1
2
3
4
5
6
7

static int max4 (int a, int b, int c, int d) {
    int max = a;
    if (b > max) b = max;
    if (c > max) c = max;
    if (d > max) d = max;
    return max;
}

Q2. 세 값의 최솟값을 구하는 min3 메서드를 작성한다.

1
2
3
4
5
6

static int min3 (int a, int b, int c) {
    int min = a;
    if (b < min) min = b;
    if (c < min) min = c;
    return min;
}

Q3. 네 값의 최솟값을 구하는 min4 메서드를 작성한다.

1
2
3
4
5
6
7

static int min4 (int a, int b, int c, int d) {
    int min = a;
    if (b < min) min = b;
    if (c < min) min = c;
    if (d < min) min = d;
    return min;
}

Q4. 세 값의 대소 관계 13종류의 모든 조합에 대해 중앙값을 구하여 출력하는 프로그램을 작성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

package com.monica.doit.chap01;

public class Exam0104 {
	static int median3 (int a, int b, int c) {
		if (a >= b)
			if (b >= c)
				return b;
			else if (a <= c)
				return a;
			else
				return c;
		else if (a > c)
			return a;
		else if (b > c)
			return c;
		else
			return b;
	}
	
	public static void main(String[] args) {
		System.out.println("median3(3,2,1) =" + median3(3,2,1));
		System.out.println("median3(3,2,2) =" + median3(3,2,2));
		System.out.println("median3(3,1,2) =" + median3(3,1,2));
		System.out.println("median3(3,2,3) =" + median3(3,2,3));
		System.out.println("median3(2,1,3) =" + median3(2,1,3));
		System.out.println("median3(3,3,2) =" + median3(3,3,2));
		System.out.println("median3(3,3,3) =" + median3(3,3,3));
		System.out.println("median3(2,2,3) =" + median3(2,2,3));
		System.out.println("median3(2,3,1) =" + median3(2,3,1));
		System.out.println("median3(2,3,2) =" + median3(2,3,2));
		System.out.println("median3(1,3,2) =" + median3(1,3,2));
		System.out.println("median3(2,3,3) =" + median3(2,3,3));
		System.out.println("median3(1,2,3) =" + median3(1,2,3));
	}
}

Q5. 중앙값을 구하는 2개의 메서드 중 1번이 더 효율적인 이유는 무엇인가?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 1번
static int median3 (int a, int b, int c) {
    if (a >= b)
        if (b >= c)
            return b;
    else if (a <= c)
        return a;
    else
        return c;
    else if (a > c)
        return a;
    else if (b > c)
        return c;
    else
        return b;
}

// 2번
static int med3(int a, int b, int c) {
    if ((b >= a && c <= a) || b <= a && c >= a))
        return a;
    else if ((a > b && c < b) || (a < b && c > b))
        return b;
    return c;
}

2번 방법의 경우 위에 if문에서 실행했던 비교 (b>=a, c<=a 등)을 아래 else if 문에서 또 비교하고 있으므로, 이미 나온 결론을 또 연산하고 있다. 따라서 1번의 경우 최악의 시나리오일 때 최대 3번의 비교를 한다. 그러나 2번의 경우 med3함수는 최악의 시나리오일 때 5번의 비교를 한다. 따라서 2번 방법이 효율이 떨어진다.

조건 판단과 분기

1
2
3
4
5
6
7

// if ~ else if ~ else 문
if (n > 0)
    System.out.println("이 수는 양수입니다.");
else if (n < 0)
    System.out.println("이 수는 음수입니다.");
else 
    System.out.println("이 수는 0입니다.");

3개의 분기로 나눠진다.

1
2
3
4
5
6
7
8
9
10
11

// if ~ else if ~ else if문
if (n == 1)
    System.out.println("이 수는 1입니다.");
else if (n == 2)
    System.out.println("이 수는 2입니다.");
else if (n == 3)
    System.out.println("이 수는 3입니다.");
/*
else
;
*/  // 공백문: 실제로 아무것도 하지 않는 문장

4개의 분기로 나눠진다

순서도의 기호

순서도: 문제에 대한 정의/분석/해법을 그림으로 표현

flowchart

  • 데이터(data): 데이터의 입력과 출력을 나타낸다.
  • 처리(process): 여러 종류의 처리를 담당한다. 즉 정보의 값, 자료형, 위치를 바꾸도록 정의한 연산이나 연산 집합의 실행 또는 연속적인 몇 가지 흐름 가운데 하나의 방향을 결정하는 연산 집합이나 연산군의 실행을 나타낸다.
  • 미리 정의한 처리(predefined process): 는 서브 루틴 및 모듈 등 다른 곳에서 이미 정의한 하나 이상의 연산 또는 명령어들로 이루어진 처리를 나타낸다.
  • 판단(decision): 하나의 입구와 하나 이상을 선택할 수 있는 출구가 있고, 기호에서 정의한 조건을 평가하여 하나의 출구를 선택하는 판단 기능(스위치형 기능)을 나타낸다. 주로 예상되는 평가 결과의 경로를 선 가까이에 쓴다.
  • 루프 범위(loop limit): 두 부분으로 구성되어 루프의 시작과 종료를 나타낸다. 기호의 두 부분에는 같은 이름(루프에 대한 임의의 이름)을 사용한다. 루프의 시작 기호(반복 전에 판단하는 경우) 또는 종료 기호(반복 후에 판단하는 경우) 안에 초기값, 증갓값, 종룟값(종료 조건)을 표기한다.
  • 선(line): 제어의 흐름을 나타낸다. 주로 흐름의 방향을 분명히 나타내고자 할 때 화살표를 붙이는데, 순서도에 작성할 때도 보기 슆게 화살표를 붙이기도 한다.
  • 단말(terminator): 외부 환경으로 나가거나 외부 환경에서 들어오는 것을 나타낸다. 예를 들어 프로그램 흐름의 시작과 종료를 나타낸다.

반복

어떤 조건이 성립하는 동안 처리를 반복하여 실행하는 것을 반복 구조(루프)라고 한다.

while문 반복

  • while(제어식) 명령문
  • 실행 전에 반복을 계속할 지 판단하는 사전 판단 반복 구조

Q6. 실습 1-4에서 while문이 종료될 때 변수 i 값이 n + 1이 됨을 확인한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Exam0106 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    System.out.println("1부터 n까지의 합을 구합니다.");
    System.out.print("n의 값: ");
    int n = in.nextInt();

    int sum = 0;
    int i = 1;
    while (i <= n) {
      sum += i;
      i++;
    }

    System.out.println("1부터 " + n + "까지의 합은 " + sum + "입니다.");
    System.out.println("i는 " + i + "입니다.");
  }
}

for문 반복

  • for(초기화부분; 제어식; 업데이트부분) 명령문

  • 하나의 변수를 사용하는 반복문은 while문보다 for문을 사용하는 것이 좋다.
  • 초기화 부분, 제어식, 업데이트 부분은 생략이 가능하다. 세미콜론은 생략하면 안 된다.
  • for의 초기화 부분에서 선언한 변수는 for문 안에서만 유효하다.
    • for문 종료 후에도 변수를 사용하려면 for문 바깥에서 변수 선언
  • 사후 판단 반복

Q7. n이 7이면 ‘1 + 2 + 3 + 4 + 5 + 6 + 7 = 28’로 출력하는 프로그램을 작성한다.

1
2
3
4
5
6
7
8
9
10
11

public class Exam0107 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += i;
    }
    System.out.println(sum);
  }
}

Q8. 1부터 10까지의 합은 (1 + 10) * 5와 같은 방법으로 구할 수 있다. 가우스의 덧셈 방법을 이용하여 1부터 n까지의 ㅈ정수 합을 구하는 프로그램을 작성한다.

1
2
3
4
5
6
7
8

public class Exam0108 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int result = (n + 1) * (n / 2) + (n % 2 == 0 ? 0 : n / 2 + 1);
    System.out.println(result);
  }
}

Q9. 정수 a, b를 포함하여 그 사이의 모든 정수의 합을 구하여 반환하는 메서드를 작성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Exam0109 {
  public static void main(String[] args) {
    System.out.println(sumof(1, 10));
  }

  public static int sumof(int a, int b) {
    int result = 0;
    for (int i = (a < b ? a : b); i <= (a < b ? b : a); i++) {
      result += i;
    }
    return result;
  }
}

do while문 반복

  • do문 while(제어식);
  • 사후 판단 반복

사전 판단 반복과 사후 판단 반복의 차이점

  • 사전 판단 반복
    • while문, for문
    • 제어식이 false이면 루프 본문은 한 번도 실행되지 않는다.
  • 사후 판단 반복: 루프 본문이 반드시 한 번은 실행된다.
    • do while문

Q10. 두 변수 a, b에 정수를 입력하고 b-a를 출력하는 프로그램을 작성하라. 단, 변수 b에 입력한 값이 a 이하면 변수 b의 값을 다시 입력받는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Exam0110 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a, b;

    while (true) {
      a = sc.nextInt();
      b = sc.nextInt();
      System.out.println("a의 값: " + a);
      System.out.println("b의 값: " + b);
      if (b > a)
        break;
      System.out.println("a보다 더 큰 값을 입력하세요!");
    }
    System.out.println("b - a는 " + (b - a) + "입니다.");
  }
}

Q11. 양의 정수를 입력하고 자릿수를 출력하는 프로그램을 작성한다. 예를 들어 135를 입력하면 ‘그 수는 3자리입니다’라고 출력하고, 1314를 입력하면 ‘그 수는 4자리입니다.’라고 출력하게 만든다.

1
2
3
4
5
6
7
8
9
10
11
12

public class Exam0111 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int count = 0;
    while (n > 0) {
      n /= 10; 
      count++;
    }
    System.out.printf("그 수는 %s자리입니다.", count);
  }
}

구조적 프로그래밍(structured programming)

  • 하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법
  • 순차, 선택, 반복이라는 3종류의 제어 흐름을 사용한다.

논리연산자의 단축 평가(short circuit evaluation)

논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피연산자의 평가를 수행하지 않는데, 이를 단축 평가(short circuit evaluation)라고 한다.

  • || 연산자의 왼쪽 피연산자를 평가한 값이 true면 오른쪽 피연산자는 평가하지 않는다.
  • && 연산자의 왼쪽 피연산자를 평가한 값이 false면 오른쪽 피연산자는 평가하지 않는다.

드모르간 법칙

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

1
2

(x && y) == !(!x || !y);
(x || y) == !(!x && !y);

image

다중루프

반복문 안에서 다시 반복될 수 있다.

1
2
3
4
5
6
7

// 곱셈표 출력
public static void main(String[] args) {
  for(int i = 1; i <= 9; i++) {
    System.out.printf("%3d", i*j);
  }
  System.out.println();
}

다음은 위의 코드의 순서도와 i와 j의 변화를 나타낸 그림이다.

image

  • 바깥쪽의 for문(행루프)은 변수 i의 값을 1부터 9까지 증가시키며, 각각의 반복은 표의 1행, 2행 … 9행에 해당한다. 즉 바깥쪽의 for문은 세로 방향에 대한 반복이다.
  • 안쪽의 for문(열루프)은 각 행의 가로 방향에 대한 반복이다.

Q12. 왼쪽에 곱하는 수가 있는 곱셈표를 출력하는 프로그램을 작성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Exam0112 {
  public static void main(String[] args) {
    System.out.print("  |");
    for (int i = 1; i <= 9; i++) {
      System.out.printf("%3d", i);
    }
    System.out.println();
    System.out.println("--+---------------------------");
    for (int i = 1; i <= 9; i++) {
      System.out.printf("%d |", i);
      for (int j = 1; j <= 9; j++) {
        System.out.printf("%3d", i * j);
      }
      System.out.println();
    }
  }
}

Q13. 곱셈이 아니라 덧셈을 출력하는 프로그램을 작성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Exam0113 {
  public static void main(String[] args) {
    System.out.print("  |");
    for (int i = 1; i <= 9; i++) {
      System.out.printf("%3d", i);
    }
    System.out.println();
    System.out.println("--+---------------------------");
    for (int i = 1; i <= 9; i++) {
      System.out.printf("%d |", i);
      for (int j = 1; j <= 9; j++) {
        System.out.printf("%3d", i + j);
      }
      System.out.println();
    }
  }
}

Q14. 입력한 수를 한 변으로 하는 정사각형을 * 기호로 출력하는 프로그램을 작성한다.

1
2
3
4
5
6
7
8
9
10

public class Exam0114 {
  public static void main(String[] args) {
    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        System.out.print("*");
      }
      System.out.println();
    }
  }
}

직각 이등변 삼각형 출력

1
2
3
4
5

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= i; j++)
    System.out.print('*');
  System.out.println();
}

image

  • 바깥쪽 for문(행루프)은 변수 i의 값을 1부터 n까지 증가시킨다. 이는 삼각형의 각 행에 대한 세로 방향 반복이다.
  • 안쪽 for문(열루프)은 변수 j의 값을 1부터 i까지 증가시키면서 출력한다.
  • 이 삼각형을 위부터 1행~n행이라고 하면 i행에 i개의 별을 출력하고 마지막 n행에 n개의 별을 출력한다.

Q15. 직각 이등변 삼각형을 출력하는 메서드를 작성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

public class Exam0115 {

  // 실행메서드
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    triangleLB(n);
    triangleLU(n);
    triangleRU(n);
    triangleRB(n);
  }
  
  // 왼쪽 아래가 직각인 이등변 삼각형을 출력
  public static void triangleLB(int n) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= i; j++) {
        System.out.print("*");
      }
      System.out.println();
    }
  }
  
  // 왼쪽 위가 직각인 이등변 삼각형을 출력
  public static void triangleLU(int n) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n - i + 1; j++) {
        System.out.print("*");
      }
      System.out.println();
    }
  }
  
  // 오른쪽 위가 직각인 이등변 삼각형을 출력
  public static void triangleRU(int n) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= i - 1; j++) {
        System.out.print(" ");
      }
      for (int j = n; j >= i; j--) {
        System.out.print("*");
      }
      System.out.println();
    }
  }
  
  // 오른쪽 아래가 직각인 이등변 삼각형을 출력
  public static void triangleRB(int n) {
    for(int i = 1; i <= n; i++) {
      for (int j = n - 1; j >= i; j--) {
        System.out.print(" ");
      }
      
      for (int j = 1; j <= i; j++) {
        System.out.print("*");
      }
      System.out.println();
    }
  }
}

Q16. n단의 피라미드를 출력하는 메서드 작성

1
2
3
4
5
6
7
8
9
10
11
12

public static void spira(int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = n - 1; j >= i; j--) {
      System.out.print(" ");
    }

    for (int j = 1; j <= 2 * i - 1; j++) {
      System.out.print("*");
    }
    System.out.println();
  }
}

Q17. 아래를 향한 n단의 숫자 피라미드를 출력하는 메서드 작성

1
2
3
4
5
6
7
8
9
10
11
12

public static void npira(int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = n; j >= i; j--) {
      System.out.print(" ");
    }

    for (int j = 1; j <= 2 * i - 1; j++) {
      System.out.print(i % 10);
    }
    System.out.println();
  }
}

n이 4일 때의 실행 결과는 다음과 같다.

1
2
3
4

    1
   222
  33333
 4444444
do-it
do-it java
This post is licensed under CC BY 4.0 by the author.
Recent Update
Contents

코어 자바스크립트 #2.7: 형변환

이산수학 #1강: 명제

Loading comments from Disqus ...