[알고리즘] 02. Java 기초 알고리즘 - 반복문

 

 

 

 

 

안녕하세요🖐️

 

이번시간에는 기초 알고리즘 중 하나인 반복문에 대해 간단히 알아보는 시간을 갖겠습니다~

 

 

 

 

---

반복문(루프)이란?

프로그램의 흐름을 반복하는 제어문입니다.

 

반복문의 종류엔 아래와 같이 여러 가지가 있습니다.

아래 반복문들을 차례대로 배워보겠습니다.

• while
• do ... while
• for

 

 

 

 

---

while문

while문은 주어진 조건이 성립하는 동안 처리를 반복하여 실행합니다. 실행 전에 주어진 조건이 성립하는지 계속 판단하는데, 이런 구조를 사전 판단 반복 구조 라고 부릅니다. 조건이 true면 계속 반복하고, 조건이 false면 반복을 멈추고 끝냅니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 1부터 n까지 반복하는 while문
	public void whileLoop(int n) {
		
		int i = 1;	// 반복 시작 지점
		
		while(i <= n) {		// i가 n 이하면 반복한다.
			System.out.println("while문이 " + i + "번 실행 됐습니다.");
			i++;		// 반복 할때만다 i값을 증가시켜준다.
		}
        
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 7;	// 반복될 횟수
		
		// Practice02 클래스의 whileLoop 메소드 접근
		pr.whileLoop(n);
	}

}

- 출력 결과 -

while문이 1번 실행됐습니다.
while문이 2번 실행됐습니다.
while문이 3번 실행됐습니다.
while문이 4번 실행됐습니다.
while문이 5번 실행됐습니다.
while문이 6번 실행됐습니다.
while문이 7번 실행됐습니다.

위 코드는 하나의 정수 n이 주어지고, 1부터 n까지 몇 번 반복하는지 단순히 확인하는 코드입니다.

1. n = 7이라는 정수가 주어졌을때, 첫 반복문의 조건은 1 <= 7 입니다. 1은 7 이하 이기 때문에 while 본문을 실행합니다.
   while 본문 종료 전에 i의 값을 1 증가시키고 while문을 다시 실행합니다. 
2. 두번째 반복문의 조건은 2 <= 7 이고, 마찬가지로 2는 7 이하 이기 때문에 다시 while 본문을 실행합니다. while 본문 종료 전에 i의 값을 1 증가시키고 while문을 다시 실행합니다.

이런 식으로 i값을 계속 증가시키면서 while 본문을 실행합니다.

 

아래의 그림과 표로 조금 더 설명을 진행하겠습니다.

while 문 진행 순서도와 변수의 변화

순서도에서 시작부분에 변수 i 에 1을 대입하면서 시작을 합니다. i 가 주어진 n 의 값과 비교를 했을 때, Yes면 i 를 출력하고 No일 경우에는 밖으로 빠져나갑니다.

 

주어진 n 의 값을 7이라고 가정해 보겠습니다.

i 변수의 변화에 따라 반복실행을 확인하면 i 는 1~7까지 i 출력을 진행합니다. i 가 8이 되는 순간 반복문에서 빠져나갑니다. 그리고 i 는 8일때, 반복문 실행을 안 하니, 최종 i 의 값은 8 입니다.

 

 

 

 

---

do ... while 문

do ... while문은 우선 한번 실행 후, 주어진 조건이 성립하는 동안 처리를 반복하여 실행합니다. 반드시 한번 실행 후, 주어진 조건이 성립하는지 계속 판단하는데, 이런 구조를 사후 판단 반복 구조 라고 부릅니다. 조건이 true면 다시 do 를 실행하고, 조건이 false면 반복을 멈추고 끝냅니다.

 

사전 판단 반복문인 while문, for문은 처음부터 제어식의 조건을 평가하여, true면 실행하고 false면 한 번도 실행을 하지 않습니다. 하지만 사후 판단 반복문인 do ... while문은 반드시 한 번은 실행됩니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 1부터 n까지 반복하는 do...while문
	public void doWhileLoop(int n) {
			
		int i = 1;
		do {
			System.out.println("do ... while문이 " + i + "번 실행 됐습니다.");
			i++;
		} while( i <= n );
        
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 7;	// 반복될 횟수
		
		// Practice02 클래스의 doWhileLoop 메소드 접근
		pr.doWhileLoop(n);
	}

}

- 출력 결과 -

do ... while문이 1번 실행 됐습니다.
do ... while문이 2번 실행 됐습니다.
do ... while문이 3번 실행 됐습니다.
do ... while문이 4번 실행 됐습니다.
do ... while문이 5번 실행 됐습니다.
do ... while문이 6번 실행 됐습니다.
do ... while문이 7번 실행 됐습니다.

위 코드는 하나의 정수 n이 주어지고, 1부터 n까지 몇 번 반복하는지 단순히 확인하는 코드입니다.

1. n = 7이라는 정수가 주어졌을 때,  do 본문을 먼저 실행합니다.
2. 다시 do를 실행할지 while문에서 확인합니다. 첫 while 문의 조건은 2 <= 7 입니다. 2는 7이하 이기 때문에 do 본문을 다시 실행합니다.
3. do 본문 종료 전에 i의 값을 1 증가시킵니다.
4. while문을 다시 실행합니다. 두 번째 반복문의 조건은 3 <= 7 이고, 마찬가지로 3은 7 이하 이기 때문에 다시 do문이 실행됩니다. 

이런 식으로 i값을 계속 증가시키면서 do ... while 문을 실행합니다.

 

아래의 그림과 표로 조금 더 설명을 진행하겠습니다.

do ... while 문 진행 순서도와 변수의 변화

순서도에서 시작 부분에 변수 i 에 1을 대입하면서 시작을 합니다. 먼저 반복문의 본문을 진행합니다. 그리고 i 에 1을 더하고 n 의 값과 비교를 합니다. Yes면 다시 반복문의 본문을 진행하고 No일 경우에는 밖으로 빠져나갑니다.

 

주어진 n 의 값을 7이라고 가정해 보겠습니다. 

i 변수의 변화에 따라 반복실행을 확인하면 i 는 1~7까지 i 출력을 진행합니다. i 가 8이 되는 순간 반복문에서 빠져나갑니다. 그리고 i 는 8일때, 반복문 실행을 안 하니, 최종 i 의 값은 8 입니다.

💡 do ... while 문은 최초 한번은 무조건 실행하기 때문에 n의 값을 0으로 셋팅해도 반드시 한번은 실행이 됩니다. 반드시 한번은 실행해야 할 경우에만 do ... while 문을 사용하는 게 좋습니다.

 

 

 

 

 

---

for 문

for문은 주어진 조건이 성립하는 동안 처리를 반복하여 실행합니다. 실행 전에 주어진 조건이 성립하는지 계속 판단하는 사전 판단 반복 구조 입니다. 조건이 true면 계속 반복하고, 조건이 false면 반복을 멈추고 끝냅니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 1부터 n까지 반복하는 for문
	public void forLoop(int n) {
		
		for(int i = 1; i <= n; i++) {
			System.out.println("for문이 " + i + "번 실행 됐습니다.");
		}
        
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 7;	// 반복될 횟수
		
		// Practice02 클래스의 forLoop 메소드 접근
		pr.forLoop(n);
	}

}

- 출력 결과 -

for문이 1번 실행 됐습니다.
for문이 2번 실행 됐습니다.
for문이 3번 실행 됐습니다.
for문이 4번 실행 됐습니다.
for문이 5번 실행 됐습니다.
for문이 6번 실행 됐습니다.
for문이 7번 실행 됐습니다.

 

 

for문의 형식은 아래와 같습니다.

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

• 초기화 부분 : for문을 실행하기 전에 한 번만 실행합니다. 
• 제어식 : 평가한 값이 true면 for문의 명령문을 실행합니다.
• 업데이트 부분 : 명령문을 실행한 다음에 실행합니다.

💡 for 문의 초기화 부분, 제어식, 업데이트 부분은 모두 생략이 가능합니다. 하지만 세미콜론( ; )은 생략하면 안됩니다. 또한 for 문의 초기화 부분에서 선언한 변수는 for문 안에서만 유효합니다.

 

 

 

 

 

---

다중 루프

위 내용은 단순한 반복을 수행하는 내용이었습니다. 하지만 반복 안에서 다시 반복할 경우도 있습니다. 이러한 경우 중첩되는 반복문에 따라서 이중 루프, 삼중 루프라고 부릅니다.

 

예를 들어, n까지 곱해진 곱셈표를 만들고 싶다면 다중루프로 구현할 수 있습니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 1부터 n까지 곱셈표를 출력하는 메소드
	public void multiplicationTable(int n) {
		// 바깥쪽 for문은 기준이 되는 단의 수
		for(int i = 1; i <= n; i++) {
			// 안쪽 for문은 기준이 되는 단과 1부터 n까지 곱해서 출력해줄 반복문.
			for(int j = 1; j <= n; j++) {
				/* 1부터 j까지 곱한 결과를 한 줄로 출력.
				 * 각 줄에 i * j 를 통해 증가되는 i값에 따라 1부터 n까지 증가되는 j값을 계속 곱해준다.
				 */
				System.out.printf("%5d", i * j);
			}
			// 1단씩 진행 될때마다 줄바꿈 처리
			System.out.println();
		}
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 9;	// 곱셈표를 만들 단의 수
		
		// Practice02 클래스의 multiplicationTable 메소드 접근
		pr.multiplicationTable(n);
	}

}

- 출력 결과 -

    1    2    3    4    5    6    7    8    9
    2    4    6    8   10   12   14   16   18
    3    6    9   12   15   18   21   24   27
    4    8   12   16   20   24   28   32   36
    5   10   15   20   25   30   35   40   45
    6   12   18   24   30   36   42   48   54
    7   14   21   28   35   42   49   56   63
    8   16   24   32   40   48   56   64   72
    9   18   27   36   45   54   63   72   81

위 코드를 살펴보면 바깥쪽의 for문은 변수 i 값을 1부터 n 까지 반복합니다.

바깥쪽 for문이 반복할 때마다 안쪽 for문이 1부터 n 까지 진행됩니다.

즉 바깥쪽 for문이 n회 반복을 하고, 안쪽 for문은 n * n 회 반복합니다.

 

따라서 해당 곱셈표를 출력하는 다중루프는 다음과 같이 처리됩니다.

 

 

 

 

 

 

---

실습 진행

 

● 1부터 n까지 홀수값만 더하기

Q. 하나의 정수 n이 주어졌을 때, 1부터  n까지 홀수만 더한 값은?

A. 1부터 n까지 반복문을 만들고, 반복문 본문에서 조건문을 통해 홀수를 판단하여 최종결과 값에 더해주겠습니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 1부터 n까지 홀수값만 더한 결과를 구하는 메소드
	public int totalOdd(int n) {
		// 모든 홀수값을 더한 변수
		int total = 0;
		
		// i에 1을 대입 후 i부터 n까지 반복한다. 반복이 끝날때마다 i를 1 증가시킨다. 조건이 맞으면 계속 반복한다.
		for(int i = 1; i < n; i++) {
			
			// i에 2를 나누어서 나머지 몫이 1이라면 홀수이다.
			if(i % 2 == 1) {
				
				/* total = total + i 와 같은 문법
				 * total 변수에 i를 계속 더해준다. (ex. 1 + 3 + 5 ... + n)
				 */
				total += i;
			}
		}
		
		return total;
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 10;
		
		// Practice02 클래스의 totalOdd 메소드 접근
		int total = pr.totalOdd(n);
        
		System.out.println("1부터 " + n + "까지 홀수만 더한 결과는 " + total + " 입니다.");
	}

}

- 출력 결과 -

1부터 10까지 홀수만 더한 결과는 25 입니다.

 

 

 

 

● n 단 직각삼각형 만들기

Q. 하나의 정수 n이 주어졌을 때, 왼쪽 아래가 직각인 이등변 삼각형을 출력해 주세요.

A. 바깥쪽 반복문의 변수 i 값을 1부터 n까지 실행시키고, 안쪽 반복문에서 1부터 i 까지 *을 출력하겠습니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 왼쪽 아래를 직각으로하는 n단의 직각삼각형을 출력하는 메소드
	public void makeTriangle(int n) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= i; j++) {
				/* 한줄로 1부터 i까지 한 줄로 출력.
				 * 각 줄에 증가되는 i값에 따라 1부터 i까지 증가되는 j값 만큼 계속 출력해준다.
				 */
				System.out.print("*");
			}
			// 1단씩 진행 될때마다 줄바꿈 처리
			System.out.println();
		}
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 10;
		
		// Practice02 클래스의 makeTriangle 메소드 접근
		pr.makeTriangle(n);
	}

}

- 출력 결과 -

*
**
***
****
*****
******
*******
********
*********
**********

 

 

 

● 2부터 n까지 소수 구하기

※ 소수 : 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수

Q. 하나의 정수 n이 주어졌을 때, 2부터  n까지 소수를 출력해 주세요.

A. 2부터 n까지 바깥쪽에 반복문을 만들고, 안쪽 반복문에서 1부터 자기 자신까지 나누어서 소수인지 아닌지 판별해 보겠습니다.

 

- 실습 예제 -

package com.example.practice;

public class Practice02 {
	
	// 2부터 n까지 소수를 출력하는 메소드 (효율성 증가)
	public void getPrimeNumber(int n) {
		// 바깥쪽 for문은 기준이 되는 수
		for(int i = 2; i <= n; i++) {
			// 소수 판별 변수
			boolean isPrime = true;
					
			for(int j = 1; j <= i; j++) {
				/* 1과 자기자신이 아닌 수가 나뉘었을때 나머지 값이 0 이라면 해당 i의 값은 소수가 아니다.
				 * 안쪽 반복문을 종료하고 소수가 아님을 분류하기 위해 isPrime에 false를 셋팅한다.
				 */
				if(i % j == 0 && j != 1 && j!= i) {
					isPrime = false;
					break;
				}
			}
					
			// isPrime이 false인 경우는 안쪽반복문에서 소수가 아니라고 판별이 된 경우이다. 
			if(isPrime) {
				// 2를 제외한 소수는 출력할때 앞에 콤마를 찍고 출력하기 위함.
				if(i != 2)
					System.out.printf(", %d", i);
				else
					System.out.printf("%d", i);
			}
		}
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 100;
		
		// Practice02 클래스의 getPrimeNumber 메소드 접근
		pr.getPrimeNumber(n);
	}

}

- 출력 결과 -

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

위 코드만으로도 소수의 값을 구할 수 있습니다. 하지만, 주어지는 값이 증가함에 따라 효율성이 떨어질 수 있습니다.
100의 값이 주어졌을 때, 현재 안쪽 for문이 실행된 횟수는 1257회입니다. 조금 더 효율성을 높이는 방법을 생각해 보겠습니다.

 

1. 숫자 형식이 전부 홀수입니다.
2. 소수가 아닌 수(합성수)의 경우, 그 약수 중 적어도 하나는 그 수의 제곱근보다 작거나 같습니다. 따라서 제곱근까지만 수행하면 됩니다.

 

- 수정된 코드 -

package com.example.practice;

public class Practice02 {
	
	// 2부터 n까지 소수를 출력하는 메소드
	public void upgradeGetPrimeNumber(int n) {
		if (n >= 2) {
            System.out.print("2"); // 2는 유일한 짝수 소수
        }
		
		// 바깥쪽 for문은 3부터 시작하여 홀수만 검사한다.
		for(int i = 3; i <= n; i += 2) {
			// 소수 판별 변수
			boolean isPrime = true;
			
			// 안쪽 for문은 i의 제곱근까지만 반복하여 검사한다.
			for(int j = 2; j <= Math.sqrt(i); j++) {
				if (i % j == 0) {
					isPrime = false; // 소수가 아님
                    break;
                }
			}
			
			// 소수인 경우에만 출력
			if(isPrime) {
                System.out.printf(", %d", i);
            }
		}
	}
    
	public static void main(String[] args) {
		// Practice02 클래스 인스턴스 생성 
		Practice02 pr = new Practice02();
        
		int n = 100;
		
		// Practice02 클래스의 upgradeGetPrimeNumber 메소드 접근
		pr.upgradeGetPrimeNumber(n);
	}

}

- 출력 결과 -

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

위 코드의 안쪽 for문이 실행된 횟수는 187회입니다. 이전 코드와 같은 결과이지만, 반복문의 횟수는 크게 줄어들었습니다.
만약 주어지는 n의 값이 크면 클수록 차이는 더욱더 크게 벌어질 것입니다.

 

 

 

 

 

 

 

 

이상으로 알고리즘 중 기초인 반복문에 대해 알아보는 시간을 마치겠습니다!

 

읽어주셔서 감사합니다 😊

 

---

소스 코드 바로가기