Red Salmon

소스 : https://github.com/stemp12/study/blob/master/Datastructure/postfix.cpp

이건 내가 지금으로부터 3년전 즉 대학교 2학년때 작성한 것인데 최근에 다시봐서 적는다.

사칙연산이 중위연산으로 들어올때 후위연산으로 구하는 것인데, 계산기의 기본 원리라고 보면 된다.

입력이 들어오면 스택을 활용해서 구하면 된다. 다음과 같은 규칙을 따른다.

1. infix 입력

2. 입력된 문자열은 정수가 아니므로 정수로 분리. 2자리 이상의 수가 들어올 수 있으므로 그 부분역시 처리.

   이때 완성된 숫자는 num이라는 스택에 삽입.

3. ( 는 무조건 삽입, )는 (나올 때까지 방출.

4. 모든 사칙연산은 자기보다 낮은 우선순위를 만날 때까지 방출 후 자기 삽입.

   이유는 연산에 깊숙이 쌓이면 우선순위가 낮다는 것.

5. 피연산자는 그냥 출력.

6. 마지막에는 스택에 쌓여 있는 것 전부 출력.

위와 같은 규칙을 따라 계산하면 된다.  뭐 어디서도 쓸모는 없겠으나..(솔직히 짜는데 시간이 오래걸려서 회사 면접문제에는 안나올 것 같다. 은근 손봐야할게 많다.)

그렇다고 안할수도 없는것이다. 자료구조는 개발자에게 기본소양이라고 생각한다.

출처 : https://www.acmicpc.net/problem/1287

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/%5BWA%5D1287.cpp

솔직히 이문제는 좀 너무했다.

먼저 사칙연산을 하려면 후외연산을 활용하는게 좋다. 이게 기본 자료구조이다. 

열심히 코딩을 했는데 자꾸 오답이나와서 생각해보니 입력의 최대가 1000자이다. 

즉, 9999999999999999999999999+1이 될 수도 있다.

int를 벗어나게 되니 당연히 빅인테져를 사용해야 하는데 자바가 아닌이상 C와 C++은 이마저도 구현해야한다.

그런데 또 사칙연산 전부가 들어간다. 즉 더하기 빼기 곱하기 나누기 전부 빅인테져 기반으로 구현해야 한다.

후위연산자체도 코딩하기 길고 짜증나는데 또 여기서 저런것 마저 요구하고 있다..그래서 나는 포기했다.

그럴만한 가치가 느껴지지 않았다.

물론 큰 시험이라면 당장 구현해야겠지만 그런 큰 시험이 아니므로 그냥 재껴두련다...

출처 : https://www.acmicpc.net/problem/1613

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1613.cpp

정말 쉬운 문제인데 참 오래 해맸다. 내가 왜 해맸는지도 모르겠다. 

플루이드 알고리즘을 사용할때 입력에서 1부터했으므로 당연히 1부터 검색을 해야하는데

습관적으로 0부터해서 계속 틀렸다 ㅠㅠ

이런 실수가 없어야 하는데 참 아쉽다.

출처 : https://www.acmicpc.net/problem/1298

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1298.cpp

이 문제는 그냥 이분매칭 알고리즘을 적용하면 풀리는 문제이다.

볼것도 없다. 최대 매칭을 구하라고하니 당연한 것이다. 알고리즘 역시 많이 썼던 그대로 하면된다.

그런데 항상 생각하는데, 쓰면 다 알고 보면 다 아는데 처음부터시작하면 오랜만에 하다보니 잘 기억이 나지 않고, 알고리즘이 쉽게 써지지 않는다. 더 많은 노력이 필요하다고 생각된다.