함수 복습하기
main 함수에서 다른 함수를 호출하고 나서 해당 함수가 종료되거나 또는 return 되면 main 함수로 돌아간다. (아마도 최초의 다른함수들을 호출한 곳은 main 일것이다.)
return 키워드를 통해 나를 호출하기 전에 함수로 실행 프로세스를 넘겨준다라는 의미였다.
함수마다 공간이 다른 공간이기 때문에 같은 지역변수 이름이 허용된다.
재귀함수
대부분의 인터넷 설명을 보다보면 재귀함수는 자기 자신을 호출하는 것이라고 표현한다.
하지만 실상은 반은 맞고 반은 틀린 말이다. 해당 표현으로 이해를 하게되면 결국 같은 함수로 오해하여 이해할수 있기 떄문이다.
재귀함수란 흔히 나 자신을 호출하는 함수라고 많이들 이야기 하지만 실제로는 코드가 재활용 되어
같은 이름의(다른함수)를 또 호출하는 것이다.
결론적으로 코드만 같고 다른 함수로 이해 하면 구조를 파악하기 쉽다.
장단점
장점
변수를 여럿 만들 필요가 없다.
예를들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있습니다.
while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해집니다.
단점
지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야합니다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.
함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
#include <iostream>
// ABC -> test -> main 순서로 빼줘야한다
// 가장 나중에 들어온 데이터가 가장 먼저 빠져나가는 것 = stack
// 재귀함수란 흔히 나 자신을 호출하는 함수라고 많이들 하지만
// 실제로는 코드가 재활용되어 함수를 호출하는 것이다.
// 즉 main -> test -> test -> test .......
// 계속해서 스택이 쌓이는 것이다.
// 아래의 코드를 F5 하면 'Stack Overflow' 표시가 나온다
void test(int x)
{
// 무한정 호출되는 함수를 방지해야 하는 게 급선무이다.
// test(x);
// 아래의 함수를 호출하면 4025번까지 호출되고나서 stack Overflow 된다
// test(x + 1);
if (x == 3)
{
return;
// test(2) 로 돌아감 -> test(1) -> ... main 으로 돌아감
}
test(x + 1);
std::cout << x;
}
char main() {
test(0);
return 0;
}
C++
복사
#include <iostream>
void test(int x) {
if (x == 4) {
return;
}
std::cout << x;
test(x + 1);
}
char main() {
test(0);
return 0;
}
C++
복사
#include <iostream>
int arr[5] = { 5, 7, 1, 2, 3 };
void test(int x) {
if (x == 5) {
return;
}
std::cout << arr[x] << " " << std::endl;
test(x + 1);
std::cout << arr[x] << " " << std::endl;
}
char main() {
test(0);
return 0;
}
C++
복사
#include <iostream>
void test(int x) {
// x 값이 0보다 작아지면 return 합니다.
if (x < 0) {
return;
}
// 1. 여기서부터 실행됩니다.
std::cout << x << " " << std::endl;
test(x - 1);
// 3. 다시 거꾸로 출력. 단, x가 0이 아닐 때에만 실행합니다
if (x > 0) {
std::cout << x << " " << std::endl;
}
}
char main() {
// 변수 x 입력 받기
int x;
std::cin >> x;
// x값부터 test 실행
test(x);
return 0;
}
C++
복사
#include <iostream>
int arr[8] = { 3,7,4,1,9,4,6,2 };
void test(int x) {
if (x < 0) {
return;
}
std::cout << arr[x] << " ";
test(x - 1);
if (x > 0) {
std::cout << arr[x] << " ";
}
}
char main() {
int x;
std::cin >> x;
test(x);
return 0;
}
C++
복사
재귀함수를 이용한 배열 순회
// 문제
// 출력결과 : 0 1 2 3
int arr[5] = { 5,7,1,2,3 };
void test(int x)
{
// 무한정 호출되는 함수를
// 방지해야 하는게 급선무이다.
if (x == 3)
{
return;
}
std::cout << arr[x];
test(x + 1);
}
int main()
{
test(0);
return 0;
}
C++
복사
연습문제
무한 재귀 막기
문제 1번
아래 그림과 같이 재귀 함수를 구현해주세요.
(전역변수를 쓰지 않습니다)
입출력 값이 없는 문제입니다.
•
---------------------------------------
Trace 연습을 많이 해야합니다.
F10, F11, ctrl + F10 버튼을 이용해서
능숙해지도록 연습을 꼭 해보세요!!
Level20 번지점프 [난이도 : 3]
문제 2번
숫자 n을 입력 받으세요.
숫자 n부터 0까지 Count down 했다가
다시 돌아오는 수를 출력 하시면 됩니다.
ex) 4
4 3 2 1 0 1 2 3 4
ex ) 6
6 5 4 3 2 1 0 1 2 3 4 5 6
입력 예제
4
출력 결과
4 3 2 1 0 1 2 3 4
마이클잭슨 무브먼트
문제 3번
마이클잭슨은 앞으로 갔다가 뒤로가는 백스탭 춤을 추곤합니다.
이 무브먼트(움직임)를 재귀를 사용해 출력 해주세요.
만약,
3 5 4 6 2 9 를 입력 받으면
3 5 4 6 2 9 2 6 4 5 3 이 출력 됩니다.
입력 예제
1 2 3 4 5 6
출력 결과
1 2 3 4 5 6 5 4 3 2 1
마이클잭슨 무브먼트
문제 3번
마이클잭슨은 앞으로 갔다가 뒤로가는 백스탭 춤을 추곤합니다.
이 무브먼트(움직임)를 재귀를 사용해 출력 해주세요.
만약,
3 5 4 6 2 9 를 입력 받으면
3 5 4 6 2 9 2 6 4 5 3 이 출력 됩니다.
입력 예제
1 2 3 4 5 6
출력 결과
1 2 3 4 5 6 5 4 3 2 1
두칸씩 점프하기
문제 4번
다음과 같이 동작하는 프로그램을 작성해 주세요
한번 재귀호출 될 때 마다, 2씩 증가됩니다.
그리고 3번 재귀 함수 진입 후, 리턴되면서 값을 출력 하면 됩니다.
만약 1을 입력받았다면,
출력 결과 : 7 5 3 1
입력 예제
1
출력 결과
7 5 3 1
다섯글자 순차/역순으로 출력
문제 5번
다섯 글자를 배열에 넣어주세요.
그리고 0번~4번 index까지 출력 하고
4번~0번 index까지 출력하는 프로그램을
재귀호출로 만들어 주세요
입력 예제
abcde
출력 결과
abcde
edcba
문제 6번
a, b 숫자 2개를 입력 받고,
재귀호출을 이용하여
a --> b --> a 까지 출력 해 주세요.
ex ) 3 9
3 4 5 6 7 8 9 8 7 6 5 4 3
입력 예제
3 9
출력 결과
3 4 5 6 7 8 9 8 7 6 5 4 3
문제 7번
index 숫자 한개를 입력받으세요
해당 index부터 0번 index까지 출력 한 후
0번 index부터 입력받은 index까지 출력 하는 프로그램을 작성 해 주세요.
재귀호출을 이용하여 문제를 풀어주세요.
ex ) 3
1 4 7 3 7 4 1
입력 예제
3
출력 결과
1 4 7 3 7 4 1
문제 8번
숫자 1개를 입력받고
그 숫자가 0이 될때까지 2로 나누어 주세요
0이 된 이후에는 return하기 시작하여
되돌아 가는 값을 출력 하면 됩니다.
ex) 17
1 2 4 8 17
입력 예제
17
출력 결과
1 2 4 8 17
훈련문제
문제 1번
그림과 같이 동작하는 프로그램을 만들어주세요. (입출력 값 없음)
앞으로 돌진하는 계단
문제 2번
한 문장을 입력 받으세요.(최대 10글자)
그리고 예제와 같이 계단식으로 출력하세요.
중첩 2중 for문을 이용해서 풀어주세요
for문을 돌리는 방향 및 순서를 유의 해 주세요
입력 예제
78ATQP
출력 결과
P
QP
TQP
ATQP
8ATQP
78ATQP
절반 나누기
문제 3번
한 문장을 입력 받으세요.(최대 10글자)
그리고 문장의 길이/2 를 하여 2등분 해주세요.
예를들어 "ABCDEAB" 문장을 2등분하면 7/2=3 이므로
0~2번 index 글자: ABC
3~6번 index 글자: DEAB
이렇게 2등분 할 수 있습니다.
이렇게 나누어진 두 문장이 동일한 문장인지 확인하는 프로그램을 작성 해주세요.
ex1)
입력: ABCABC
출력: 동일한문장
ex2)
입력: ABCDEAB
출력: 다른문장
입력 예제
ABCABC
출력 결과
동일한문장
문제 4번
두 비트배열을 입력 받아주세요.
두 비트배열을 겹쳤을때,
색칠한 부분이 겹치면, "걸리다" 출력
겹치는 부분이 없다면, "걸리지않는다" 라고 출력 해주세요.
(색칠된곳은 1 로 입력을 받고, 색칠안된곳은 0 으로 입력 받으면 됩니다)
입력 예제
1 1 1 1
1 0 0 1
1 0 0 0
0 0 1 0
0 0 0 0
0 0 0 0
1 1 1 1
0 1 0 0
출력 결과
걸리다
문제 5번
문자 1개를 입력받으세요
ASCII코드값 기준 입력 받은 문자에서 부터 -3 문자부터 +3 문자까지 출력하면 됩니다.
만약 G를 입력받았다면 DEFGHIJ 를 출력하면 됩니다.
만약 N를 입력받았다면 KLMNOPQ 를 출력하면 됩니다.
그런데 만약 출력해야 하는 문자가 A 이전이라면, Z를 출력하면 되고,
만약 출력해야 하는 문자가 Z 다음 문자라면 A를 출력하면 됩니다.
따라서
만약 Y를 입력받았다면 VWXYZAB 를 출력하면 되고,
만약 B를 입력받았다면 YZABCDE를 출력하면 됩니다.
입력 예제
Y
출력 결과
VWXYZAB
문제 6번
숫자 7개를 배열에 입력 받아주세요.
1층 3번 index까지 출력
2층 4번 index까지 출력
3층 5번 index까지 출력
4층 6번 index까지 출력
ex)
3 5 7 1 4 2 8 을 입력 받았다면 아래와 같이 출력 하면 됩니다.
3 5 7 1
3 5 7 1 4
3 5 7 1 4 2
3 5 7 1 4 2 8
중첩 2중 for문을 활용해서 출력 해주세요.
입력 예제
3 5 7 1 4 2 8
출력 결과
3 5 7 1
3 5 7 1 4
3 5 7 1 4 2
3 5 7 1 4 2 8
문제 7번
한문장을 입력 받으세요.
한문장을 아래와 같이 출력 해주세요.
ex)
[입력]
BBQWORLD
[출력]
B
BB
BBQ
BBQW
BBQWO
BBQWOR
BBQWORL
BBQWORLD
ex)
[입력]
GDPK
[츨력]
G
GD
GDP
GDPK
입력 예제
BBQWORLD
출력 결과
B
BB
BBQ
BBQW
BBQWO
BBQWOR
BBQWORL
BBQWORLD
문제 8번
정렬되어 있는 네칸짜리 두 배열에 각각 숫자 4개씩 입력 받습니다.
두배열에 있는 8개 숫자들을 합쳐 하나의 배열에 정렬된 상태로 넣으려고 합니다.
아래의 알고리즘으로 동작되도록 코딩해주세요.
입력 예제
1 3 3 7
2 3 4 6
출력 결과
1 2 3 3 3 4 6 7
문제 9번
위 배열을 하드코딩 해주세요. 패턴 size를 입력 받으세요.
만약 2,2 를 입력 받았다면
2x2
패턴을 적용 시키면 됩니다.
그리고 패턴을 적용시키면 합을 구할 수 있습니다.
ex) 2,2 size의 패턴을 0,0에 적용시키면 합은 3+5+3+3= 14 입니다.
패턴의 size를 입력받고 패턴을 적용시켜 합을 구하여. max값이 나오는 위치를 출력 해주세요.
주의 : 입력하실때 y좌표부터 입력받아주세요 ex) 2,3은 y=2, x=3
입력 예제
2 2
출력 결과
(2,3)
객체지향 문제
main()의 함수를 참고하여 Tower 클래스를 작성하라.
높이와 너비는 자유롭게 작성해라.
int main()
{
Tower myTower;
Tower seoulTower(100);
cout << "높이는 " << myTower.getHeight() << "미터" << endl;
cout << "높이는 " << seoulTower .getHeight() << "미터" << endl;
return 0;
}
JavaScript
복사
다음과 같은 Person 클래스가 있다.
Person 클래스와 main() 함수를 작성하여, 3개의 Person 객체를 가지는 배열을 선언하고, 다음과 같이 키보드에서 이름과 전화번호를 입력받아 출력하고 검색하는 프로그램을 완성하라
class Person
{
public:
Person();
string getName() { return name; }
string getTel() { return tel; }
void set(string name, string tel);
private:
string name;
string tel;
}
JavaScript
복사
