펭로그

참고자료 : https://www.swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV184uV6I70CFAZN 어느 회사 오프라인 코딩 테스트 문제로 문자열 계산기가 나왔었다.중위표기를 후위표기법로 바꿔서 풀면 풀린다는 개념은 알고 있었지만 당시엔 제대로 생각이 안나서 시간만 허비했었다....시험은 이미 끝났지만 그래도 다시 한번 풀어보기로 했다. 사칙연산을 할 때 연산 우선 순위는 다음과 같다. 1. 괄호를 먼저 계산하라.2. 곱셈 또는 나눗셈3. 덧셈 또는 뺄셈 하지만, 이는 사람이 쉽게 이해할 수 있는 형태의 논리이며 컴퓨터가 이해할 수 있는 논리로 바꾸면 다음과 같다. - Step1. 중위 표기법 수식을 후위 표기법 수식으로 변..

문제링크 : https://noj.am/5639 이진 트리를 구성하고 있는 각 노드는 다음과 같이 표현한다.V - 부모 노드L - 왼쪽 자식 노드R - 오른쪽 자식 노드 이진 트리의 순회 방식은 다음과 같다.전위 순회 : V-L-R중위 순회 : L-V-R후위 순회 : L-R-V 문제에서 주어진 다음 조건을 보면 힌트를 유추할 수 있다. 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 입력으로 전위순회를 시행했을 때의 결과가 주어진다고 했기 때문에 위의 원리를 그대로 적용해보면 각 노드별 서브트리를 구할 수..

문제링크 : https://noj.am/9935 요즘 알고리즘 테스트 문제들이 파싱 문제들이 하도 많이 나와서 연습해볼겸 별 의미는 없지만 string stream을 사용하여 풀어보았다.string stream을 통하여 입력된 문자열이 폭발 문자열의 '마지막 문자'에 해당할 경우 이전에 입력되었던 문자열이 폭발 문자열과 일치하는지 체크하는 방법으로 풀이했다. 본 풀이법은 스택을 사용한 풀이법이라 할 수 있다. 예제에서는 "C4"가 폭발 문자열이다.아래의 조건에서 '4'를 찾았다면 문자열 탐색이 실행된다.1if (s == bomb.back())cs 먼저 idx 변수를 폭발 문자열 크기만큼 뺀 인덱스로 초기화 시켜준다.폭발 문자열의 맨 앞인 'C'에 해당하는 값이다.123int idx = result.siz..

문제링크 : https://www.acmicpc.net/problem/9012 1. 열린 괄호의 갯수 == 닫힌 괄호의 갯수 가 성립해야한다.2. ( 가 나올때마다 카운트를 증가시키고 ) 이 나올때마다 카운트를 감소시켜 최종 카운트가 0이 되어야 한다.3. 닫힌 괄호가 먼저 나오면 안된다. ())(() 라던지 ))()(( 의 상황이 나오면 안된다는 뜻 (20~21번째 줄 조건시 break) 심화문제로 BOJ 10799번 쇠막대기 문제가 있다. 123456789101112131415161718192021222324252627// BOJ 9012 괄호#include using namespace std; int main() { // freopen("../input.txt", "r", stdin); int T;..

문제링크 : https://www.acmicpc.net/problem/10799 ( 은 쇠막대기의 시작점이고 ) 은 쇠막대기의 끝나는 부분이고 ( ) 은 레이저를 나타낸다.두 괄호 사이(쇠막대기)에는 반드시 ( ) 이 올 수밖에 없다. 1. 열린 괄호의 갯수는 닫힌 괄호의 갯수와 동일해야 한다.2. 열린 괄호가 증가하다가 감소하는 시점 ( ) 은 반드시 레이저이다.3. 레이저 ( )를 제외하고 레이저의 좌측 부분에 열린 괄호가 몇개인지를 세면 레이저를 기준으로 좌측의 잘린 쇠막대기의 판이 몇개인지 알 수 있다. 열린 괄호를 읽을 때 마다 카운트를 세면 될 것이다.4. 레이저 ( ) 우측 편부터 닫힌 괄호 ) 가 오면 쇠막대기 카운트를 하나씩 감소시킨다. 여기서 찾을 수 있는 규칙은 ( 의 경우 반드시 다..