[recursion 예제3] 매개변수의 명시화

2020. 7. 15. 15:44· algorithm

 

순환적 알고리즘을 설계하기 위해선 2가지가 필요하다.

1. 적어도 하나의 base case(종료되는 case)가 있어야 한다.

2. 모든 case는 결국 base case로 수렴한다.

 

 

* 추가로, 

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔야한다!

 ->이번 포스팅은 명시적 매개변수로 표현하는 법에 대한 것이다.

 

 


"순차 탐색"을 통해  두 매개변수의 차이점과 recursion의 응용을 알아보자.

 

 

암시적 매개변수?

data[0]에서 data[n-1] 사이에서 target을 검색하는 코드이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int data[6] = { 1,2,3,4,5,6 };
	printf("%d", search(data,6,4));
}
int search(int* data, int n, int target) {
	for (int i = 0; i < n; i++)
		if (data[i] == target)
			return i;
	return -1;
}

결과:3

->하지만, 검색 구간의 시작 인덱스인 0은 보통 생략한다.즉, 암시적(implicit) 매개변수로 설정한 것이다.


 

명시적 매개변수?

data[begin]에서 data[end] 사이에서 target을 검색하는 코드이다.

 

순차탐색 ver.1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int data[6] = { 1,2,3,4,5,6 };
	printf("%d", search(data,0,5,4));
}
int search(int* data, int begin,int end, int target) {
	if (begin > end) //검색할 개수가 0개일 때
		return -1;
	else if (target == data[begin])
		return begin;
	else
		return search(data, begin + 1, end, target);
}

순차탐색 ver.2 (binary search와는 다름)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int data[6] = { 1,2,3,4,5,6 };
	printf("%d", search(data,0,5,4));
}
int search(int* data, int begin,int end, int target) {
	if (begin > end)
		return -1;
	else {
		int middle = (begin + end) / 2;
		if (data[middle] == target)
			return middle;
		int index = search(data, begin, middle - 1, target);
		if (index != -1)
			return index;
		else
			return search(data, middle + 1, end, target);
	}
}

 

결과:3

-> 즉, 검색구간의 시작점을 begin으로 설정해 명시적(explicit)으로 지정한다.

*자기자신을 호출할 때 혼동 방지를 위해서 시작부분을 명시하는 변수가 있어야 한다.

 


매개변수의 명시화를 이용해 다른 코드를 구현해보자.

최대값 찾기 ver.1

(begin <= end라고 가정하자.)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int findMax(int* data, int begin, int end);
int main(void) {
	int data[6] = { 11,102,0,2,14,33 };
	cout<<findMax(data, 0, 5)<<endl;
}
int findMax(int* data, int begin, int end) {
	if (begin == end)
		return data[begin];
	else
		return max(data[begin], findMax(data, begin + 1, end));
}

결과:102

최대값 찾기 아이디어

 

최대값 찾기 ver.2

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int findMax(int* data, int begin, int end);
int main(void) {
	int data[6] = { 11,102,0,2,14,33 };
	cout<<findMax(data, 0, 5)<<endl;
}
int findMax(int* data, int begin, int end) {
	if (begin == end)
		return data[begin];
	else {
		int middle = (begin + end) / 2;
		int max1 = findMax(data, begin, middle);
		int max2 = findMax(data, middle + 1, end);
		return max(max1, max2);
	}
}

결과:102

최대값 찾기 2  아이디어

 


나는 지금까지 반복문을 활용하면서 암시적 매개변수를 대부분 사용한 것 같다.

명시적 매개변수의 활용의 이점을 알았고, 앞으로를 위해서 명시적 변수를 쓰는 연습을 해둬야겠다.

반응형

'algorithm' 카테고리의 다른 글

[recursion 응용] n queens problem  (0) 2020.07.22
[recursion 응용] Counting Cells in a Blob  (0) 2020.07.19
[recursion 응용] 미로찾기  (0) 2020.07.16
[recursion 예제 2] 문자열, 2진수  (0) 2020.07.15
[recursion 예제 1] 피보나치, 최대공약수  (1) 2020.07.11
'algorithm' 카테고리의 다른 글
  • [recursion 응용] Counting Cells in a Blob
  • [recursion 응용] 미로찾기
  • [recursion 예제 2] 문자열, 2진수
  • [recursion 예제 1] 피보나치, 최대공약수
이티권
이티권
programming, design
이티권
ET WORLD
이티권
전체
오늘
어제
  • 분류 전체보기 (85)
    • Web (43)
      • Three.js (1)
      • javascript (6)
      • React (2)
    • algorithm (18)
      • BOJ (6)
    • Record (9)
      • 생각 (6)
      • 경험 (3)
    • Art (7)
    • Technology (8)
      • Data (2)
      • Info (5)

블로그 메뉴

  • WEB
  • RECORD
  • ALGORITHM
  • TECH
  • ART

공지사항

인기 글

태그

  • 순환
  • 뷰라우터
  • 뷰링크
  • 맥북소리녹화
  • ChatGPT
  • 기명함수 표현식
  • 컴포넌트 통신
  • vue.js
  • 깃허브하는법
  • C언어
  • 재귀함수
  • html tag
  • svgr
  • 퓨 이벤트
  • 포토샵
  • 알고리즘문제
  • 레포지터리만들기
  • 깃 CLI
  • 시니어프론트엔드개발자
  • js
  • 페이지 링크
  • 스프레드문법
  • 알고리즘
  • 컴퓨터공학힘든가요
  • 불확신
  • 나머지매개변수
  • CSS
  • HTML
  • 깃허브시작
  • 뷰 프롭스

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
이티권
[recursion 예제3] 매개변수의 명시화
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.