유자의 코딩모험

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제풀이 오큰수 (Nearest Greater Element) Next Greater Element - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company inte..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 문자열로 이루어진 계산식이 주어질 때, 계산식을 후위 표기식으로 바꾸어 계산하는 문제다. "3+(4+5)*6+7"라는 문자열을 후위 표기식으로 바꾸는 과정은 어떻게 될까? 입력 받은 계산식에서 토큰을 읽는다 토큰이 피연산자, 즉 숫자면 토큰을 출력한다 토큰이 연산자(괄호 포함)일 경우 스택이 비었거나 top보다 우선순위가 높으면 스택에 push 우선순위가 높지 않으면 연산자의 우선순위가 토큰의 우선순위보다 작을때까지 스택에서 pop한 후 토큰의 연산자를 push한다 토큰이 오른쪽 괄호 ')'일 경우 스택 top에 왼쪽 괄호 '('가 올 때까지 pop 연산..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 0 ~ 9로 이루어진 번호 문자열에서 같은 번호로 붙어있는 쌍들을 소거하고 남은 번호로 비밀번호를 만드는 문제다. 예를 들어 아래의 번호 열을 철수의 방법으로 소거하고 알아낸 비밀번호다. 번호 쌍이 소거되고 소거된 번호 쌍의 좌우 번호가 같은 번호이면 또 소거할 수 있다. 번호 문자열을 검사할 때 스택이 비어있지 않고 스택의 top과 번호가 같다면 pop해준다. 스택이 비어있거나 스택의 top과 번호가 같지 않은 경우에는 스택에 번호를 넣어준다. 소거할 수 있는 번호 쌍을 모두 소거했다면 스택에서 번호를 꺼내준다. 이때 순서가 거꾸로이므로 reverse(..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 그림과 같이 도식화한 지도에서 A도시에서 B도시로 가는 길이 존재하는지 조사하려고 한다. 길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다. A과 B는 숫자 0과 99로 고정된다. 2차원 벡터로 그래프를 만든 다음 DFS를 수행해주었다. 0부터 출발해서 이동할 수 있는 모든 도시를 방문했을 때 visited[99]가 true이면 A에서 B로 가는 길이 존재한다는 뜻이다. C++ 코드

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 4 종류의 괄호문자들 '()', '[]', '{}', ''로 이루어진 문자열이 주어질 때, 괄호들의 짝이 모두 맞는지 판별하는 문제다. 아래와 같은 문자열은 짝이 잘 이루어져 있으므로 유효하다고 판단할 수 있다. 아래와 같은 문자열은 붉은색으로 표시된 괄호의 짝을 찾을 수 없기 때문에 유효하지 않은 문자열이다. 아래 문자열은 열고 닫는 괄호의 개수는 유효하나 짝이 맞지 않는 괄호가 사용되었기 때문에 유효하지 않다. char형의 스택에 여는 괄호 문자들 '(', '[', '{', ''일 경우에는 스택의 top이 짝인지 확인하고 짝이 아니라면 검사를 종료한다..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 N의 M 거듭제곱 값을 구하는 프로그램을 재귀호출을 이용하여 구현하는 문제다. M이 0일 때는 1, 그 이외의 경우에는 n * power(n, m - 1)을 리턴해주면 거듭제곱을 쉽게 구할 수 있다. 하지만 이 방법은 시간 복잡도가 O(N)이라서 지수가 커지면 문제가 발생할 수 있다. 이때 분할정복을 이용하면 O(logN)의 시간 복잡도로 거듭 제곱을 구할 수 있다. 2의 8제곱을 예로 들어보자. 2의 8제곱은 2를 8번 곱하여 구할 수도 있지만 거듭 제곱을 3번만 해서 해결할 수도 있다. 홀수번 거듭 제곱을 하는 경우에는 N을 한 번 곱하고 N의 (M-..