2장 · 선택과 반복

if, while and for

프로그램은 문장을 차례대로 하나씩 실행합니다. 이 순서를 바꾸는 것이 두 가지 있습니다. 선택은 어떤 문장을 실행할지 고르고, 반복은 문장을 다시 실행합니다.

그림의 프로그램은 n = 5에서 시작합니다. n이(가) 1이 아닌 동안, 짝수이면 n을(를) 반으로 나누고 홀수이면 세 배로 한 다음 1을 더하며, 한 단계를 셉니다. 맨 위의 마름모는 반복문의 질문이고, 그 아래 마름모는 if의 질문입니다. 빨간 토큰은 실행 지점이며, 옆의 코드는 실행 중인 줄을 밝혀 줍니다.

int n = 5; int steps = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } steps++; } System.out.println(steps);

n은(는) 5, 16, 8, 4, 2, 1(으)로 변합니다. 반복문의 조건은 6번 검사되며, true가 5번, 그다음 false가 한 번 나오고, 프로그램은 5을(를) 출력합니다.

이 장은 AP Computer Science A의 2단원이며, 객관식 점수의 25–35%를 차지합니다. 내용은 불 식과 if 문(2.1–2.6), while과 for 반복문(2.7–2.8), 이를 이용한 표준 알고리즘(2.9–2.10), 반복문 안의 반복문(2.11), 문장이 몇 번 실행되는지 세기(2.12)입니다.

2.1 · 선택과 반복을 쓰는 알고리즘

세 가지 구성 요소

모든 알고리즘은 세 가지로 만들어집니다. 순차(단계를 순서대로), 선택(판단), 반복(반복문)입니다.

선택은 알고리즘이 계속되는 방식이 참인지 거짓인지의 판단에 달려 있을 때 일어납니다. 반복은 원하는 결과에 이를 때까지 어떤 과정을 되풀이하는 것입니다. 둘 다 일상의 지시에 나옵니다. “비가 오면 우산을 가져가라”는 선택이고, “설탕이 녹을 때까지 저어라”는 반복입니다.

알고리즘은 말로 쓰거나 순서도로 그릴 수 있습니다. 순서도는 단계마다 상자 하나, 참인지 거짓인지의 판단마다 마름모 하나, 반복을 위해 위로 되돌아가는 화살표로 이루어집니다. 그림은 이제 같은 알고리즘을 말로 씁니다. “n은 짝수인가?”, “반으로 나눈다”, “단계를 하나 센다”입니다. 코드는 정확히 같은 내용을 Java로 말합니다.

단계의 순서가 결과를 바꿉니다. 다음 두 코드 조각에는 같은 문장이 들어 있습니다.

int x = 3; x = x * 2; x = x + 1;

int x = 3; x = x + 1; x = x * 2;

첫 번째는 x을(를) 7에, 두 번째는 8에 남깁니다. 그림에서 단계를 세는 것을 반복문 안이 아니라 반복문 뒤에서 하면, 반복문이 아무리 오래 돌아도 1이 출력됩니다.

2.2 · 불 식

관계 연산자

불 식은 true 또는 false 두 값 중 하나로 계산됩니다. 가장 간단한 것은 관계 연산자로 두 값을 비교하는 식입니다.

==와(과) !=은(는) 두 값이 같은지 다른지 검사합니다. <, >, <=, >=은(는) 숫자를 비교합니다. int, double, boolean 같은 기본 자료형에서 ==은(는) 실제 값을 비교합니다. 참조 자료형에서는 참조를 비교하여, 두 변수가 같은 객체를 참조하는지 알아봅니다(2.6).

그림에서 a은(는) 7을(를) 담고 있고 b은(는) 4, 7, 9의 값을 가집니다. 비교할 때마다 블록이 하나 만들어지며, true이면 빨간색입니다.

=은(는) 대입하고, ==은(는) 비교합니다. 불 결과는 다른 값처럼 저장할 수 있습니다. boolean same = a == b;

2.3 · if 문

단방향 선택과 양방향 선택

선택문은 문장의 순차 실행을 바꿉니다. if 문은 불 식의 값에 따라 서로 다른 코드 조각을 실행합니다.

단방향 선택(if)에는 코드 조각이 하나 있으며, 조건이 참일 때만 실행됩니다.

if (temp >= 30) { System.out.println("hot"); } System.out.println("done");

temp이(가) 34이면 hot then done을(를) 출력하고, 22이면 done만 출력합니다. 마지막 줄은 if 뒤에 있으므로 항상 실행됩니다.

양방향 선택(if-else)에는 코드 조각이 두 개 있습니다. 조건이 참이면 if의 본문, 거짓이면 else의 본문입니다. 둘 중 정확히 하나만 실행됩니다.

if (temp >= 30) { System.out.println("hot"); } else { System.out.println("mild"); } System.out.println("done");

그림은 온도 두 개를 이 코드에 보냅니다. 34에서는 토큰이 참 쪽 길로 가서 hot을(를) 출력하고, 22에서는 거짓 쪽 길로 가서 mild을(를) 출력합니다. 그다음 둘 다 done을(를) 출력합니다.

2.4 · 다방향 선택

if, else if, else

다방향 선택(if-else-if)은 일련의 조건을 순서대로 검사합니다. 처음으로 참인 조건의 코드 조각이 실행되며, 실행되는 조각은 많아야 하나입니다.

if (score >= 90) { grade = "A"; } else if (score >= 80) { grade = "B"; } else if (score >= 70) { grade = "C"; } else { grade = "F"; }

그림은 점수 세 개를 이 사슬에 떨어뜨립니다. 83은(는) score >= 90에서 걸러지지 않고 score >= 80을(를) 통과하여 잡힙니다. 등급은 "B"입니다. 그 아래 조건은 검사하지 않습니다. 95은(는) 첫 번째 관문 "A"에서 잡힙니다. 64은(는) 세 조건을 모두 통과하지 못하므로 마지막 else가 실행되어 "F"이(가) 됩니다. 마지막 else가 없으면 모든 조건을 통과하지 못한 값은 어떤 코드 조각도 실행하지 않습니다.

처음으로 참인 조건이 이기므로 순서가 중요합니다. score >= 70을(를) 먼저 검사하면 95은(는) "C"을(를) 받습니다. 70 이상인 점수는 모두 첫 번째 관문에서 멈추기 때문입니다. 가장 까다로운 검사를 먼저 두세요.

2.4 · 중첩 if 문

if 안의 if

중첩 if 문은 다른 if, if-else, if-else-if 문 안에 들어 있는 if, if-else, if-else-if 문입니다.

if (age >= 16) { if (hasPermit) { System.out.println("may drive"); } else { System.out.println("needs a permit"); } } System.out.println("done");

안쪽 조건은 바깥쪽 조건이 참일 때만 계산됩니다. 그림은 세 사람을 통과시킵니다. 나이가 17이고 면허증이 있으면 둘 다 통과하여 may drive을(를) 출력합니다. 나이가 17이고 면허증이 없으면 바깥쪽 검사는 통과하고 안쪽 검사에서 걸립니다. needs a permit 나이가 14이면 바깥쪽 검사에서 걸리므로 토큰은 상자 전체를 돌아 나가고, hasPermit은(는) 아예 살펴보지도 않으며 done만 출력됩니다.

else가 어느 if에 속하는지는 중괄호가 정합니다. 여기서 else는 바깥쪽 중괄호 안에 있으므로 if (hasPermit)와(과) 짝을 이룹니다. 16 미만인 사람은 면허증에 관한 메시지를 전혀 받지 못합니다.

2.5 · 복합 불 식

!, &&, ||

논리 연산자 !(not), &&(and), ||(or)는 불 식들을 결합하여 그 자체로 참 또는 거짓인 하나의 식을 만듭니다.

!a은(는) a이(가) 거짓일 때 참이고, 그렇지 않으면 거짓입니다. a && b은(는) 둘 다 참일 때만 참입니다. a || b은(는) a이(가) 참이거나, b이(가) 참이거나, 둘 다 참일 때 참입니다. 그림은 모든 조합을 한 행씩 살펴봅니다.

우선순위는 !이 먼저이고, 그다음 &&, 그다음 ||입니다. 따라서 a = false, b = true, c = false일 때 식 !a || b && c은(는) (!a) || (b && c)을(를) 뜻하며 결과는 true입니다. 이것을 (!a || b) && c(으)로 묶으면 false이(가) 됩니다. 괄호를 쓰면 순서가 분명해집니다.

관계 연산자가 논리 연산자보다 먼저이므로 x > 0 && x < 10은(는) 먼저 비교하고 나중에 결합합니다. 0과 10 사이에 있는 모든 x에 대해 참입니다. 0과 10은 포함하지 않습니다.

2.5 · 단락 평가

오른쪽은 실행되지 않을 수도 있음

&& 또는 ||의 왼쪽 피연산자만으로 결과가 이미 정해지면, Java는 오른쪽을 계산하지 않습니다. 이것이 단락 평가입니다.

false && anything은(는) 거짓이고 true || anything은(는) 참입니다. 오른쪽이 무엇이라고 하든 마찬가지입니다. 그래서 오른쪽은 건너뜁니다. 그림은 식 두 개를 계산합니다. 처음에는 x = 4, 그다음에는 x = 0일 때입니다.

x != 0 && 10 / x > 2 x == 0 || 10 / x > 2

x = 4일 때는 두 식 모두 양쪽이 실행됩니다. 10 / 4은(는) 2(정수 나눗셈)이고 2보다 크지 않으므로 첫 번째 식은 false이고 두 번째도 그렇습니다.

x = 0일 때는 x != 0이(가) 거짓이므로 첫 번째 식은 곧바로 false이고, x == 0은(는) 참이므로 두 번째 식은 곧바로 true입니다. 어느 쪽에서도 10 / x은(는) 실행되지 않으며, 오히려 잘된 일입니다. int을(를) 0으로 나누면 ArithmeticException이(가) 발생하기 때문입니다.

그래서 왼쪽 피연산자가 보호 장치 역할을 합니다. 순서를 반대로 쓰면 10 / x > 2 && x != 0은(는) 먼저 나누기를 하여 x이(가) 0일 때 멈춥니다.

2.6 · 동치인 불 식

진리표와 드모르간의 법칙

두 불 식이 모든 경우에 같은 값으로 계산되면 두 식은 동치입니다. 입력의 모든 조합에 대한 행이 있는 진리표로 이를 증명할 수 있습니다.

드모르간의 법칙은 두 가지 동치를 줍니다.

!(a && b) 은(는) !a || !b 와(과) 동치 !(a || b) 은(는) !a && !b 와(과) 동치

!을(를) 괄호 안으로 넣으려면 각 부분을 부정하고 &&을(를) ||(으)로, 또는 ||을(를) &&(으)로 바꿉니다. 그림에서 두 번째 식의 각 열이 첫 번째 식 위로 미끄러져 들어가며, 모든 행에서 색이 일치합니다.

연산자를 바꾸는 것을 잊으면 성립하지 않습니다. !(a && b)와(과) !a && !b은(는) 4개 행 중 2개 행에서 다릅니다. 부정한 비교는 연산자가 뒤집힙니다. !(x > 5)은(는) x <= 5입니다. 따라서 !(x >= 1 && x <= 10)은(는) x < 1 || x > 10과(와) 동치입니다.

2.6 · 객체 비교

==와 equals

서로 다른 두 변수가 같은 객체에 대한 참조를 가질 수 있습니다. 참조에 쓰는 ==와(과) !=은(는) 두 객체의 내용이 같은지가 아니라 같은 객체를 참조하는지 묻습니다.

String s1 = new String("atlas"); String s2 = s1; String s3 = new String("atlas"); String s4 = null;

s2 = s1은(는) 참조를 복사하므로 s1와(과) s2은(는) 한 객체를 가리킵니다. s1 == s2은(는) true입니다. s3은(는) 글자가 같은 두 번째 객체를 참조합니다. s1 == s3은(는) false입니다.

클래스는 흔히 두 객체가 언제 같다고 볼지 알려 주는 equals 메서드를 정의하며, 보통 속성을 비교합니다. 줄의 메서드는 문자를 비교하므로 s1.equals(s3)은(는) true입니다. 문자열은 equals(으)로 비교하고, ==(으)로는 절대 비교하지 마세요.

참조가 객체를 아예 참조하는지 알아보려면 null와(과) == 또는 !=(으)로 비교할 수 있습니다. s4 == null은(는) true입니다. (equals 메서드를 오버라이딩하는 것은 과정 범위 밖입니다.)

2.7 · while 반복문

검사하고, 실행하고, 다시 검사

반복은 되풀이의 한 형태입니다. 반복문은 불 식이 참인 동안 코드 조각을 0번 이상 되풀이합니다.

while 반복문에서는 첫 번째를 포함하여 본문을 한 번 지날 때마다 그 전에 불 식을 계산합니다. 참인 동안 본문이 실행되고, 거짓이 되면 반복문이 끝나 프로그램은 그 뒤로 이어집니다.

int sum = 0; int k = 1; while (k <= 4) { sum += k; k++; } System.out.println(sum);

추적표는 조건을 검사할 때마다 변수를 기록합니다. 그림은 이 표를 한 행씩 채웁니다.

조건은 5번 검사되고 본문은 4번 실행됩니다. 마지막 검사가 거짓이 되는 검사입니다. 반복문은 k = 5(으)로 끝나며 10이(가) 출력됩니다.

2.7 · 잘못되는 반복문

한 번도 안 돎, 끝없이 돎, 한 번 모자람

반복문 버그 대부분은 세 가지 중 하나입니다. 반복문이 한 번도 실행되지 않거나, 멈추지 않거나, 한 번 더 또는 한 번 덜 실행됩니다.

불 식이 처음부터 거짓이면 본문은 한 번도 실행되지 않습니다. k이(가) 10인 while (k < 5)은(는) 한 번 검사하고 넘어갑니다(맨 윗줄).

무한 반복문은 불 식이 언제나 참으로 계산될 때 생깁니다. 가운데 줄에서 k은(는) 1, 3, 5, 7, 9, …으로 변하고 6이 되는 일이 없으므로 while (k != 6)은(는) 거짓이 되지 않습니다. 본문이 조건에 있는 변수를 전혀 바꾸지 않는 반복문도 마찬가지입니다.

off-by-one 오류는 반복문이 한 번 더 또는 한 번 덜 실행되는 오류입니다. 1부터 5까지 출력하려던 맨 아래 반복문은 1234을(를) 출력합니다. while (k < 5)은(는) 5 앞에서 멈춥니다. k <= 5(으)로 고칩니다.

int k = 1; while (k < 5) { System.out.print(k); k++; }

반복문은 가장자리를 확인하세요. 첫 번째 반복, 마지막 반복, 그리고 반복을 끝내는 검사입니다.

2.8 · for 반복문

초기화, 불 식, 갱신

for 반복문은 횟수를 세는 반복문의 세 부분인 초기화, 불 식, 갱신을 헤더에 둡니다.

for (int i = 0; i < 3; i++) { System.out.println(i); }

초기화는 첫 번째 검사 전에 한 번 실행됩니다. 여기서 설정한 변수가 반복문 제어 변수입니다. 불 식은 초기화 직후에 계산되고, 이후에는 갱신할 때마다 다시 계산되어 거짓이 될 때까지 이어집니다. 반복할 때마다 갱신은 본문 전체가 끝난 뒤, 다음 검사 전에 실행됩니다.

그림의 토큰은 초기화 → 검사 → 본문 → 갱신 → 검사 … 순으로 움직입니다. 각 지점 아래의 횟수는 초기화 1, 검사 4, 본문 3, 갱신 3입니다. 0, 1, 2을(를) 출력하며, 각각 한 줄에 하나씩입니다.

for 반복문은 같은 동작을 하는 while 반복문으로 다시 쓸 수 있고, 그 반대도 됩니다.

int i = 0; while (i < 3) { System.out.println(i); i++; }

한 가지 차이가 있습니다. for 헤더에서 선언한 i은(는) 반복문 안에서만 존재하고, while 반복문 앞에서 선언하면 반복문이 끝난 뒤에도 남아 있습니다.

2.9 · 자릿수와 나누어떨어짐

% 10, / 10, % k

나머지 연산자를 쓰는 표준 알고리즘이 두 가지 있습니다. 정수를 한 자리씩 분해하기와 한 정수가 다른 정수로 나누어떨어지는지 검사하기입니다.

양수 int n에서 n % 10은(는) 마지막 자리 숫자이고, n / 10(정수 나눗셈)은(는) 그 숫자를 뗀 n입니다. n이(가) 0이 될 때까지 반복합니다.

int n = 3725; int sum = 0; int max = 0; int odd = 0; while (n > 0) { int d = n % 10; sum += d; if (d > max) { max = d; } if (d % 2 == 1) { odd++; } n /= 10; }

그림은 3725의 자리 숫자를 오른쪽부터 하나씩 떼어 냅니다. 5, 2, 7, 3이며, 각 숫자는 d을(를) 거칩니다.

a % b == 0은(는) a이(가) b(으)로 나누어떨어질 때 정확히 참입니다. 3725 % 5은(는) 0이므로 3725은(는) 5(으)로 나누어떨어집니다. 3725 % 3은(는) 2이므로 3(으)로 나누어떨어지지 않습니다. 2로 같은 검사를 하면 짝수와 홀수가 나뉘며, 반복문의 d % 2 == 1이(가) 그렇게 합니다.

2.9 · 합, 평균, 극값, 개수

반복문이 도는 동안 누적하기

표준 알고리즘 세 가지를 더 알아봅니다. 모두 반복문 앞에서 선언한 변수에 값을 두고 반복문 안에서 갱신합니다. 합, 최솟값 또는 최댓값, 개수입니다.

합은 0에서 시작해 각 값을 더합니다. sum += d. 3725일 때 sum는 17으로 끝납니다.

평균은 합을 값의 개수로 나눈 것입니다. 정수 나눗셈에 주의하세요.

double avg = (double) sum / 4; int avgInt = sum / 4;

avg는 4.25이고, avgInt는 4으로 소수 부분이 버려집니다. 나누기 전에 형변환해야 하며, 나눈 뒤에 하면 안 됩니다.

최댓값은 지금까지 가장 큰 값을 가지고 있다가 더 큰 값이 나오면 바꿉니다. if (d > max). 여기서 max는 7으로 끝납니다. 첫 번째 값에서 시작하거나, 어떤 실제 값도 그보다 작을 수 없는 값에서 시작합니다. 0이 통하는 것은 각 자릿수가 음수가 아니기 때문일 뿐이며, 일반적으로는 Integer.MIN_VALUE을 씁니다. 최솟값은 그 반대로 Integer.MAX_VALUE에서 시작하고 <를 검사합니다. 가장 작은 자릿수는 2입니다.

기준을 만족하는 횟수인 개수는 0에서 시작해 if 안에서 1씩 더합니다. if (d % 2 == 1)은 홀수인 자릿수를 세며, 그 결과는 3개입니다.

2.10 · String 알고리즘

뒤집기와 부분 문자열 세기

String 알고리즘은 문자열을 따라 인덱스를 옮기며 각 위치에서 부분 문자열을 가져옵니다. 새 문자열을 만들거나, 어떤 성질을 가진 부분 문자열을 검사하거나 셀 때 씁니다.

문자열을 뒤집으려면 각 문자를 지금까지 만든 문자열의 앞에 붙입니다. substring(i, i + 1)는 인덱스 i에 있는 한 문자입니다.

String word = "drawer"; String rev = ""; for (int i = 0; i < word.length(); i++) { rev = word.substring(i, i + 1) + rev; }

rev는 "d", "rd", "ard", "ward", "eward", "reward" 늘어납니다. (rev = rev + word.substring(i, i + 1)는 단어를 그대로 복사합니다.)

기준을 만족하는 부분 문자열을 세려면 창을 밀어 가며 하나씩 검사합니다.

String s = "banana"; int count = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.substring(i, i + 2).equals("an")) { count++; } }

창 substring(i, i + 2)은 "ba", "an", "na", "an", "na"을 봅니다. 2가 일치하므로 count는 2입니다. 마지막 창은 인덱스 4에서 시작하므로 i는 s.length() - 1 미만에서 멈춰야 합니다. 한 걸음 더 가면 substring(5, 7)가 끝을 넘어 StringIndexOutOfBoundsException을 던집니다.

부분 문자열은 equals로 비교합니다. 어떤 부분 문자열이 그 성질을 가졌는지 알아보려면 같은 반복문을 처음 찾은 곳에서 멈추게 할 수 있고, indexOf는 주어진 부분 문자열이 처음 나오는 위치를 반환하며 어디에도 없으면 −1을 반환합니다.

2.11 · 중첩 반복

반복문 안의 반복문

중첩 반복은 다른 반복문의 본문 안에 있는 반복문입니다. 안쪽 반복문은 자신의 반복을 모두 마친 뒤에야 바깥쪽 반복문이 다음 반복으로 넘어갑니다.

for (int r = 0; r < 3; r++) { for (int c = 0; c < 4; c++) { System.out.print(r * c + " "); } System.out.println(); }

r = 0일 때 안쪽 반복문은 c를 0부터 3까지 돌립니다. 그다음 println가 줄을 끝내고, 그제야 r가 1이 됩니다. 그림은 격자를 행마다 칸 하나씩 밝혀 줍니다. 안쪽 본문은 3 × 4 = 12번 실행되며 다음을 출력합니다.

0 0 0 0 0 1 2 3 0 2 4 6

안쪽 반복문의 범위는 바깥쪽 변수에 따라 달라질 수 있습니다. 여기서 안쪽 반복문은 r + 1번 실행되므로 반복 횟수는 1, 2, 3, 4입니다.

int count = 0; for (int r = 0; r < 4; r++) { for (int c = 0; c <= r; c++) { count++; } }

count는 10로 끝나, 직사각형이 아니라 삼각형이 됩니다.

2.12 · 비공식 실행 시간 분석

문장이 몇 번 실행되는지 세기

문장 실행 횟수는 한 문장이 실행되는 횟수입니다. 보통 몇 번의 반복을 추적하고 반복문을 따져 보며 비공식적으로 구합니다.

for (int i = 0; i < n; i++) { count++; }

i가 0부터 n − 1까지일 때 count++는 n번 실행됩니다. 검사 i < n는 n + 1번 실행되는데, 반복을 끝내기 위해 한 번 더 실행되기 때문입니다.

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; } }

중첩된 경우 바깥쪽 n번의 반복마다 안쪽 반복문이 n번 실행되므로 count++는 n × n번 실행됩니다. n = 6일 때는 6번 대 36번이고, n = 8일 때는 8번 대 64번입니다. n가 커짐에 따라 그림도 둘 다 늘어납니다. n를 두 배로 하면 한쪽은 두 배, 다른 쪽은 네 배가 됩니다.

횟수는 반복문의 범위에서 셉니다. for (int i = 1; i <= n; i++)도 n번 실행되고, 1에서 시작하는 i < n는 n − 1번 실행됩니다. 지난 쪽의 삼각형 같은 경우는 1 + 2 + … + n번 실행됩니다. 이런 횟수를 비교하면 스톱워치 없이도 어느 반복문이 더 빠른지 말할 수 있습니다.