SAYNOT'S HOME

오늘은 DFS를 사용해서 알고리즘 문제를 해결할 예정이다.

역시 차근차근 진행해보자.

*본인은 C++로 코딩할 예정이다.

1. 문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다.

항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때,

방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

출저 - 프로그래머스

2. 사고 - DFS(깊이 우선 탐색)

1. 동선이 여러개 일 경우 알파벳순이므로, sort함수를 통해 내림차순으로 정렬해둔다.

3. unordered_map을 사용해 key는 출발지, value(여러개 일 수 있으므로 vector)엔 목적지 데이터를 넣어둔다.

4. 첫 방문지인 INC을 스택에 push해둔다.

5. 이후 스택이 빌때까지 반복문을 돌아가게된다.

6. 스택의 top부분을 map의 key에 넣어 도착지를 찾아 스택에 push한다.

7. 이후 map에선 해당 도착지를 pop하여 탐색대상에서 제외시킨다.

8. 방문하고자 하는 곳이 없거나, 도착지가 존재하지 않으면 해당 key를 answer에 push한다.

9. 이후 스택에서 pop한다.

10. 스택이 비게되면 answer을 reverse함수를 통해 역순으로 배열시킨다.

11. 결과를 도출

3. 코딩

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<string> solution(vector<vector<string>> tickets) {
	vector<string> answer;
	sort(tickets.begin(), tickets.end(), greater<vector<string>>());
	unordered_map<string, vector<string>> route;
	for (unsigned int i = 0; i < tickets.size(); i++) {
		route[tickets[i][0]].push_back(tickets[i][1]);
	}
	stack<string> stk;
	stk.push("ICN");
	while (!stk.empty()) {
		string tp = stk.top();
		if (route.find(tp) == route.end() || route[tp].size() == 0) {
			answer.push_back(tp);
			stk.pop();
		}
		else {
			stk.push(route[tp].back());
			route[tp].pop_back();
		}
	}
	reverse(answer.begin(), answer.end());
	return answer;
}

int main(void) {
	vector<vector<string>> tickets;
	vector<string> v;
	v.push_back("ICN");
	v.push_back("SFO");
	tickets.push_back(v);
	v.clear();
	v.push_back("ICN");
	v.push_back("ATL");
	tickets.push_back(v);
	v.clear();
	v.push_back("SFO");
	v.push_back("ATL");
	tickets.push_back(v);
	v.clear();
	v.push_back("ATL");
	v.push_back("ICN");
	tickets.push_back(v);
	v.clear();
	v.push_back("ATL");
	v.push_back("SFO");
	tickets.push_back(v);
	v.clear();
	
	vector<string> res;
	res = solution(tickets);
	for (auto &i : res) {
		cout << i << " ";
	}
	return 0;
}

- 티켓 : [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]

- 과정1(내림차순 정렬) : [[SFO, ATL], [ICN, SFO], [ICN, ATL], [ATL,SFO], [ATL, ICN]]

- 과정2(unordered_map 대입)

SFO - ATL

ICN - SFO, ATL

ATL - SFO, ICN

- 과정3(while문)

stack - INC > ATL(else) > INC(else) > SFO(else) > ATL(else) > SFO(else) > pop*6번(if)

- 과정4(answer 역순으로 결과 도출)

answer - ICN > ATL > ICN > SFO > ATL > SFO

4. 알게된 것

백번 보는 것보다 한번 해보는게 낫다.

직접 문제만 볼땐 몰랐는데 코딩을 하며 하나씩 해결해나갈 수 있었다.

그리고 마지막엔 듣고 있는 수업의 강의를 보며 부족했던 코드를 하나씩 수정해나갔다.

BFS, DFS를 이용해야하는 문제가 많은데 계속해서 문제를 풀어봐야 적응이 되겠다는 생각이 들었다.

여행가고싶다.

오늘은 동적 계획법(일명 DP)을 사용해볼 예정이다.

'N으로 표현'이란 문제인데 문제만 보면 어려워 보인다.

차근차근 해결해나가자.

*본인은 C++로 코딩할 예정이다.

1. 문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)

12 = 55 / 5 + 5 / 5

12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때,

N과 사칙연산만 사용해서 표현 할 수 있는 방법 중

N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

출저 - 프로그래머스

2. 사고 - 동적 계획법(DP)

1. N을 사용한 횟수에 따라 만들 수 있는 수들이 생긴다(정해진다).

2. 직접 계산해보며 N에 따른 사용횟수를 일반화 해본다. > 3을 한번 사용하면 3, 두번 사용하면 33과 사칙연산 값인 6, 0, 9, 1을 산출 할 수 있다.

3. 일반화한 공식을 코딩으로 적용해본다.

4. 동적 계획법으로 탐색범위를 확실히 좁혀야 하는데에 집중하여야 한다.

3. 코딩

#include <iostream>
#include <unordered_set>
#define MAXN 8
using namespace std;

int solution(int N, int number) {
	int answer = -1, std = 0;
	unordered_set<int> us[MAXN];
	for (int i = 0; i < MAXN; i++) {
		std = 10 * std + 1;
		us[i].insert(std * N);
	}
	for (int i = 1; i < MAXN; i++) {
		for (int j = 0; j < i; j++) {
			for (auto& op1 : us[j]) {
				for (auto& op2 : us[i - j - 1]) {
					us[i].insert(op1 + op2);
					us[i].insert(op1 - op2);
					us[i].insert(op1 * op2);
					if (op2 != 0) {
						us[i].insert(op1 / op2);
					}
				}
			}
		}
		if (us[i].count(number) > 0) {
			answer = i + 1;
			break;
		}
	}
	return answer;
}

int main(void) {
	int N, number;
	N = 3;
	number = 12;
	cout << solution(N, number) << endl;

	return 0;
}

- N = 3, number = 12

- 과정1 : us[0] = 3, us[1] = 33, us[2] = 333, us[3] = 3333, us[4] = 33333, us[5] = 333333, us[6] = 3333333, us[7] = 33333333

- 과정2 : us[1] = {33, 6, 0, 9, 1}

- 과정3 : us[2] = {333, 4, 2, 3...12...}

- 과정4 : us[2] {...12...} 존재 확인, answer = i + 1

- answer = 3

- 3*3 + 3 = 12

- 결과 : 3

4. 알게된 것

다이나믹 프로그래밍이란?

문제의 답을 확인하기 위해서 확인하는 범위를 줄여가며 동적으로 결정해나가는 방식

동적 계획법을 사용하기 위해선 문제에 대한 충분한 이해를 필요로 한다.

문제를 잘 읽고 확인 범위를 줄여나가기 위한 설계를 철저히 진행해야 한다.

난이도도 다이나믹하다.

이번에 우선순위 힙을 사용하여 푸는 알고리즘 문제가 등장하였다.

오늘도 계속해서 달려보자.

*본인은 C++로 코딩할 예정이다.

1. 문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은

두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때,

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는

최소 횟수를 return 하도록 solution 함수를 작성해주세요.

출저 - 프로그래머스

2. 사고 - 우선순위 힙

1. 하나씩 비교해서 최솟값을 찾아, 계산해나가면 O(n^2) 이상의 복잡도를 가지게 된다. > 효율이 낮다.

2. 우선순위 힙을 선언한다. > greater 기준으로 정렬한다.

3. 힙의 가장 작은 수를 꺼내고, 그 다음 작은 수를 꺼내서 정해진 연산을 수행한다.

4. 결과 값을 다시 힙에 넣는다.

5. 가장 작은 수가 K를 넘어서면 카운트를 반환한다.
6. 길이가 1이거나, 힙이 비어있는 상황 등 다양한 예외 처리를 진행한다.

7. 힙을 이용하므로 시간복잡도는 O(NlogN)을 가지게 된다.

3. 코딩

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int min1 = 0, min2=0, newq=1;
    priority_queue<int, vector<int>, greater<int>> pq; //작은 순서대로 정렬하는 우선순위 큐
    for (auto&i : scoville) pq.push(i);
    if (pq.size() == 1) {
        if (pq.top() >= K) return answer;
        return -1;
    }
    while (!pq.empty() && pq.size() > 1 && newq > 0) {
    	//cout << q.top() << endl;
        min1 = pq.top(); //최소 값 저장
        pq.pop();
        min2 = pq.top(); //그 다음 최소 값 저장
        pq.pop();
        newq = min1 + (min2 * 2); //연산
        pq.push(newq); //결과 값 큐에 저장
        answer++; //카운트 증가
        if (pq.top() >= K) return answer; //최소 값이 K 이상이면 answer 반환
    }
    return -1; //나올수 없는 경우엔 -1 반환
}

int main(void) {
    vector<int> scoville;
    int K = 7;
    scoville.push_back(1);
    scoville.push_back(2);
    scoville.push_back(3);
    scoville.push_back(9);
    scoville.push_back(10);
    scoville.push_back(12);
    cout << solution(scoville, K) << endl;
    return 0;  
}

- scoville = [1, 2, 3, 9, 10, 12], K=7

- 과정1 : 1 + (2*2) = 5

> [3, 5, 9, 10, 12], answer : 1

- 과정2 : 3 + (5*2) = 13

> [9, 10, 12, 13], answer : 2, K보다 9가 크므로 answer 반환

- 결과 : 2

4. 알게된 것

heap은 유용하다!

위와 같이 heap을 이용해서 최대, 최솟값을 손쉽게 뽑아낼 수 있다.

이러한 점을 이용하여 복잡한 알고리즘을

좀 더 빠른 시간복잡도안에 결과를 도출할 수 있다.

heap과 priority heap을 이용해서 상황에 맞게 잘 구현해보자.

맵고 짜고 단거

이번에도 탐욕법(그리디)를 이용한 문제를 풀어보고자 한다.

*본인은 C++로 코딩할 예정이다.

1. 문제

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다.

이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.

number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중

가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

출저 - 프로그래머스

2. 사고 - 탐욕법

1. number의 배열을 순회하며 하나씩 이전 숫자와 비교한다.

2. 큰 숫자가 나타날 경우 그 숫자보다 작은 숫자들을 pop하고, 그 만큼 k를 감소시킨다.

3. k가 0이 되면 남은 숫자들을 자릿수에 맞춰서 반환한다.

4. k가 0이 되지않을때 역시 고려한다.

3. 코딩

#include <iostream>
#include <string>
using namespace std;

string solution(string number, int k) {
	string answer = "";
	int len;
	for (unsigned int i = 0; i < number.size(); i++) {
		len = answer.size();
		for (int j = 0; j < len; j++) {
			if (answer[j] < number[i]) {
				answer.pop_back();
				k--;
			}
			if (k == 0) {
				break;
			}
		}
		if (k == 0) {
			answer += number.substr(i, number.size());
			break;
		}
		answer += number[i];
		//cout << "answer : " << answer << ", k : " << k << endl;
	}
	answer = answer.substr(0, answer.size() - k);
	return answer;
}

int main(void) {
	string number = "4177252841";
	int k = 4;

	cout << solution(number, k) << endl;

	return 0;
}

- 수 : "4177252841"

- 뺄 갯수 : 4개

= 결과 : 775841

4. 알게된 것

string의 substr()함수!

아주 유용한 함수이다. 지정한 위치부터, 지정한 위치까지의 값을 뽑아낼 수 있는데, 유용하게 쓰인다.

파이썬의 슬라이싱과 비슷하다 보면 된다.

해당 함수를 이용해 k가 순환 중에 0이 안나오는 경우까지 고려하여 코딩해야한다.

이러한 과정을 거치면 문제를 해결 가능하다.

왜 초기화 코드에 vector가 있었던걸까?

오늘도 계속해서 알고리즘 문제를 풀어볼 예정이다.

*본인은 C++로 코딩할 예정이다.

1. 문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고,

이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때,

순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

출저 - 프로그래머스

2. 사고 - 정렬

1. 매번 가장 크게만들 수 있는 수를 고르면 O(n^2) 시간 복잡도를 가지게 될 것이다.

2. 우선 빈 문자열로 수를 초기화 한다.

3. numbers를 큰 수를 만들 수 있는 순서대로 정렬한다. > O(nlogn)

4. 하나하나씩 answer에 꺼내어 붙인다. > O(n)

5. 시간복잡도는 O(nlogn)을 가지게 된다.

6. 추가적으로 넘어오는 numbers에 0만 여러개 들어있는 경우의 수도 고려한다.

- 큰 수 정렬 기준

> 2와 34가 있다고 해보자. 234, 혹은 342가 될 수 있다. 이와 같이 하나씩 붙여보고 대소관계를 파악할 수 있다.

3. 코딩

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(int a, int b) {
	string str_fir;
	string str_sec;
	string s_a = to_string(a);
	string s_b = to_string(b);
	str_fir = s_a + s_b;
	str_sec = s_b + s_a;
	bool res = str_fir > str_sec;
	return res;
}

string solution(vector<int> numbers) {
	string answer = "";
	sort(numbers.begin(), numbers.end(), cmp);
	for (auto &num : numbers) {
		answer += to_string(num);
	}
	
	return answer[0] == '0' ? "0" : answer; //numbers에 0이 여러개면 000... 대비
}

int main(void) {
	vector<int> num;
	num.push_back(6);
	num.push_back(10);
	num.push_back(2);


	cout << solution(num) << endl;

	return 0;
}

- 수 : [6, 10, 2]

- 정렬된 수 : [6, 2, 10]

= 결과 : 6210

4. 알게된 것

예외의 상황을 항상 고려하자.

마지막 테스트케이스에서 삽질을 오래하였는데, 바로 numbers에 0이 여러개 들어온 상황이다.

이런 경우 원래 코드대로라면 000.. 이런식으로 반환할 것이다.

그렇기 때문에 answer의 첫번째 인덱스가 0이면 뒤에 뭐가 오든 0으로 치환시켜버리도록 코딩해야한다.

위와 같이 모든 경우의 수를 고려해야 완벽하게 코딩테스트에서 통과할 수 있을 것이다.

"야! C++도 sort 함수 있어!"

오늘도 알바를 마치고 어김없이 달린다.

알고리즘 공부해서 미래에 있을 코딩테스트를 뿌시자.

*본인은 C++로 코딩할 예정이다.

1. 문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다.

다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다.

체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost,

여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때,

체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

출저 - 프로그래머스

2. 사고 - 탐욕법

1. 학생의 수만큼 배열을 만들고, 가지고 있는 체육복 수를 지정한다.

2. 맨앞과 맨뒤에 배열을 추가하여 구현시 편리하게 만든다.

3. 모두 1로 지정하고, reserve 학생들은 +1, lost는 -1을 준다.

4. 순환하면서 체육복을 빌려줄 수 있을때(2일때), 작은번호가 0이면 체육복을 빌려주며 수를 수정한다.

5. 0이 아니면 뒷번호 역시 조사하여 조건에 맞으면 조정한다.

6. 알고리즘 복잡도는 for문이 3번 돌며 총 O(n)의 복잡도를 가지게 될 것이다.

3. 코딩

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
	int answer = 0;
	//vector<int> v;
	vector<int> v(n+2, 1);
	//for (int i = 0; i <= n+1; i++) {
	//	v.push_back(i);
	//	v[i] = 1;
	//}
	for (auto &j : lost)v[j]--;
	for (auto &k : reserve)v[k]++;
	for (int i = 1; i <= n; i++) {
		if (v[i]==2 && v[i-1]==0) {
			v[i - 1]++;
			v[i]--;
		}
		else if (v[i] == 2 && v[i + 1] == 0) {
			v[i + 1]++;
			v[i]--;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (v[i] >= 1) {
			answer++;
		}
	}
	return answer;
}

int main(void) {
	int num = 5;
	vector<int> lost;
	lost.push_back(2);
	lost.push_back(4);
	vector<int> reserve;
	reserve.push_back(3);

	cout << solution(num, lost, reserve) << endl;

	return 0;
}

- 학생수 : 5명(1번, 2번, 3번, 4번, 5번)

- 여분가져온 착한 친구 : 3번

- 잃어버린 친구 : 2번, 4번

= 수업을 들을 수 있는 학생수 : 4명

4. 알게된 것

시간복잡도만 보고 알고리즘의 좋고, 나쁨을 판단할 수 없다는 것을 알게되었다.

만약 학생수가 10,000,000명이라고 생각하고 여벌을 가져온 학생이 2명이라고 생각해보자.

여기서 위 알고리즘으로 구현하면 10,000,000개의 공간이 필요로 하며, O(n)이지만 여러번의 연산을 필요로한다.

이럴경우 다음과 같이 사고 해 볼 수 있다.

1. 여벌의 체육복을 가져온 학생들의 번호를 정렬한다. > O(nlogn)

2. 잃어버린 학생에 대해 빌려줄 수 있는 학생을 찾아서 처리한다(lost를 해쉬화) > O(1)

위의 알고리즘은 O(nlogn)이기 때문에 알고리즘만 보면 O(n)보다는 비효율적으로 보일 수 있으나,

학생수가 매우 많고, 여벌을 챙겨온 학생 수가 이에 비해 매우 적으면 오히려 아래와 같은 방식이

더 나은 알고리즘이 될 수 있다.

이와 같이 시간복잡도만 보고 모든 것을 판단할 수 없다는 것을 알게 되었다.

다음엔 체육복 가져간 도둑부터 잡는 걸로 하자.

방학 중에 알고리즘 공부를 통해 미래에 있을 코딩테스트에 대비하고자 한다.

그래서 프로그래머스에 있는 문제를 하나하나 풀어보며 포스팅 할 예정이다.

*본인은 C++로 코딩할 예정이다.

1. 문제

수많은 마라톤 선수들이 마라톤에 참여하였다.

단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와

완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,

완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성하라.

출저 - 프로그래머스

2. 사고 - 해시

1. 단순히 생각하고자 하면 이중 for문을 이용하여 쉽게 해결할 수 있을 것처럼 보인다.
2. 단, 시간복잡도가 O(n^2)가 되며 효율성 테스트에 통과하지 못할 것이다.

3. Hash Table을 이용하여 이를 해결할 수 있을 것이다. > unordered_map을 사용하였다.

4. participant 길이만큼 순회하며 Key에 선수이름을 저장하고, 이름이 등장한 횟수를 value로 하여 추가한다.

5. 중복이 되면 해당 Key의 value를 1 증가시킨다.

6. completion 길이만큼 순회하며 map에 존재하는 key에 value를 1 감소시킨다.

7. map을 순회하며 value가 0이 아닌 key를 반환한다.

8. for문을 3번 순회하지만 시간복잡도는 O(n)이다.

3. 코딩

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	vector<string>::iterator vecit;
	unordered_map<string, unsigned int> ht;
	unordered_map<string, unsigned int>::iterator htit;
	for (vecit = participant.begin(); vecit != participant.end(); vecit++) {
		auto htit = ht.insert(make_pair(*vecit,1)); //key(참가자), value(이름등장횟수) 생성
		if (htit.second == false) { //참가자가 중복이면
			ht[*vecit] += 1; //해당 참가자의 value 값 1 증가
		}
	}
    
	for (vecit = completion.begin(); vecit != completion.end(); vecit++) { //완주자 순회
		ht[*vecit] -= 1; //완주자 value 값 1 감소
	}
    
	for (htit = ht.begin(); htit != ht.end(); htit++) { //unordered map 순회
		if (htit->second != 0) { //0이 아니면
			answer = htit->first; //해당 key > answer 대입
		}
	}
	return answer; //반환
}

int main(void) {
	vector<string> parti;
	vector<string> comple;
	parti.push_back("leo"); //테스트 케이스
	parti.push_back("kiki");
	parti.push_back("eden");

	comple.push_back("eden");
	comple.push_back("kiki");

	string res = solution(parti, comple);

	cout << res << endl;

	return 0;
}

참가자 : leo, eden, kiki

완주자 : eden, kiki

완주하지 못한 사람 : leo

4. 알게된 것

다른 사람들의 풀이를 보다보니 C++11에 추가된 '범위 기반 for문'을 많이 사용하는 것을 알게되었다.

'범위 기반 for문'을 사용하여 vector와 unordered_map을 순회 시 긴 코드를 짧게 정렬 가능하다.

수정한 solution 함수로 포스팅을 마치겠다.

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	//vector<sring>::iterator vecit;
	unordered_map<string, unsigned int> ht;
	//unordered_map<string, unsigned int>::iterator htit;
	for (auto vecit : participant) {
		auto htit = ht.insert(make_pair(vecit,1));
		if (htit.second == false) {
			ht[vecit] += 1;
		}
	}
	for (auto vecit : completion) {
		ht[vecit] -= 1;
	}
	for (auto htit : ht) {
		if (htit.second != 0) {
			answer = htit.first;
		}
	}
	return answer;
}

앞으로 마라톤은 모두 완주하는 걸로하자.

2020 카카오 하계 인턴 코딩테스트에서 처참한 결과를 보며 느낀점이 많다.

아직 기초를 한참 더 쌓아야 가능할 것같다고 생각하였다.

이번 시간엔 파이썬과 스택 구조를 활용하여

수식의 후위 표기, 계산에 대해 공부해보도록 하자.

1. 수식의 후위 표기법

후위 표기법을 이야기하기 전에 수식의 여러가지 표기법에 대해 짚고 넘어가야한다.

수식엔 다양한 표기법이 존재한다.

• 전위(prefix) 표기법 : 연산자 먼저 표시, 피연산자를 나중에 표시
  • * + A B - C D
• 중위(infix) 표기법 : 피연산자 사이에 연산자를 표기(일반적으로 사용)
  • (A + B) * (C - D)
• 후위(postfix) 표기법 : 피연산자를 먼저 표시, 연산자를 나중에 표시
  • A B + C D - *

3개 예제는 모두 같은 공식이다. 중위 표기법을 일반적으로 우리가 사용하지만

프로그래밍으로 괄호가 포함된 중위 표기 연산 수식을 계산하긴 힘들다.

컴퓨터 프로그래밍시 괄호표기가 필요없는 후위 표기법을 이용하여

다양한 수식을 계산하는 것이 속도가 빠르다.

*계산기나 컴퓨터 내부에선 원래 스택을 활용해 중위표기법을 후위표기법으로 변환하여 연산한다.

2. 중위 표기법 -> 후위 표기법 변환

후위 표기법을 연산하기 위해선 일반적인 중위 표기법을 후위 표기법으로 변환할 필요가 있다.

변환 방법은 다음과 같다.

1. 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3. 괄호를 제거한다.
   
   

예제를 통해 살펴보자. 위 공식을 이용하여

• A * C + B(중위 표기법)를 후위 표기법으로 변환해보자.

1. 우선순위에 따라 괄호를 다시 표현하면 ((A * B) + C)
2. 각 연산자를 오른쪽 괄호 뒤로 이동시키면 ((A B) * C) +
3. 괄호제거하면 마무리, A B * C +
   
   
   

3. 후위 표기법 계산

이제는 후위 표기법을 계산해보자.

이제부터 스택 개념을 적용할 것이며 계산 방법은 다음과 같다.

*스택 : https://saynot.tistory.com/28

1. 처음부터 차례대로 읽으며 피연산자는 스택에 쌓는다.
2. 연산자를 만나면 스택에서 피연산자 2개를 꺼내 연산을 수행하고 다시 스택에 쌓는다.
3. 모두 읽을 때 까지 위 두 공식을 반복한다.

역시 예제를 통해 알아보자.

위 공식을 이용하여 13 5 + 3 -(후위 표현식) 수식을 계산해보자.

1. 13은 피연산자, 스택에 PUSH
2. 5는 피연산자, 스택에 PUSH
3. +는 연산자이므로 5 POP, 13 POP하여 연산 수행
4. 13 + 5 = 18, 결과값을 스택에 PUSH
5. 3은 피연산자, 스택에 PUSH
6. -는 연산자이므로 3 POP, 18 POP하여 연산 수행
7. 18 - 3 = 15, 계산 끝
8. 13 5 + 3 - = 15
   
   
   

4. 알고리즘 설계

중위 표현식 > 후위 표현식 변환 알고리즘

1. 연산자 우선순위 지정(이걸 바꾸는 코딩테스트 문제 존재)
2. 후위 표현식으로 만들어져 반환될 리스트 생성
3. 중위 표현식을 왼쪽부터 한 글짜씩 읽음
4. 피연산자면 리스트에 append
5. '('이면 스택에 PUSH, ')'이면 '('가 나올때까지 스택에서 POP, 리스트에 append
6. 연산자면 스택에서 이보다 높은 우선순위들 POP, 리스트에 append
7. 그리고 이 연산자를 스택에 PUSH
8. 스택에 남아있는 연산자는 모두 POP, 리스트에 append
   
   

후위 표현식 계산 알고리즘

1. 후위 표현식을 왼쪽부터 한 글짜씩 읽음
2. 피연산자면 스택에 PUSH
3. 연산자면 스택에서 POP해서 op1, 다시 POP해서 op2 지정
4. op2와 op1을 연산자로 계산하여, 결과값 스택에 PUSH
5. 수식의 끝이면 스택에서 POP하여 계산 결과 도출
   
   
   

4. 코딩 - Python

위 두가지를 이용하여 중위 표현식을 입력받으면 후위 표현식으로 변환하여

결과값을 도출하는 알고리즘을 구현해보았다.

*splitTokens함수와 Stack 클래스는 해당 주제에서 제외되는 부분이라 생략하였다.

def infixTopostfix(tokenList): #중위 표현식을 후위 표현식으로 변환
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []

    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)         
        elif token == ')':
            if token == ')':
                while opStack.peek() != '(':
                #print(opStack.peek())
                    postfixList.append(opStack.pop())
                opStack.pop()
        else:
            if opStack.isEmpty() == False:  
                if prec[opStack.peek()] >= prec[token] and token != '(':
                    postfixList.append(opStack.pop())
                    opStack.push(token)
                elif prec[opStack.peek()] >= prec[token] and token == '(':
                    opStack.push(token)
                else:
                    opStack.push(token)
            elif opStack.isEmpty() == True:
                opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList


def postfixEval(tokenList): #후위 표현식 계산
    opStack = ArrayStack()
    for token in tokenList:
        if type(token) is int:
            opStack.push(token)
        elif token == '*':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2*tmp1)
        elif token == '/':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2/tmp1)
        elif token == '+':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2+tmp1)
        elif token == '-':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2-tmp1)
    return opStack.pop()



def solution(expr):
    tokens = splitTokens(expr) #문자열을 토큰화 시키는 함수
    print("tokens : ", tokens)
    postfix = infixTopostfix(tokens) #중위 표현식 > 후위 표현식
    print("postfix : ", postfix)
    res = postfixEval(postfix) #후위 표현식 계산
    return res

def main():
    quest = '( 13 + 15 ) * ( 16 + 23 )'
    ans = solution(quest)
    print(quest, " = ",ans)

if __name__ == '__main__':
    main()

결과는 다음과 같다.

일반적으로 수식 순서는 * /가 + -에 비해 먼저이다. 하지만 이를 바꿔서 계산해야하는

코딩 테스트 문제가 존재한다. 이럴때 위 코드에서 사전을 수정하여 우선순위를 조절해 코드를 바꾸면 될것이다.