유자의 코딩모험

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

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 해야 할 V개의 작업이 있는데 어떤 작업은 특정 작업이 끝나야 시작할 수 있다. 이를 선행 관계라 한다. 이런 작업의 선행 관계를 나타낸 그래프가 주어졌을 때, 한 사람이 한 번에 하나씩 일할 수 있는 작업 순서를 찾는 문제다. 위상 정렬을 사용하여 문제를 해결했다. 선행 관계를 입력받아서 그래프를 만들어주고 cnt 배열에 각 정점이 가지는 선행 정점의 수를 저장한다. 작업 순서를 찾기 위해 먼저 cnt[i]가 0인 정점들을 큐에 넣어준다. cnt[i] = 0은 선행 정점이 없으므로 바로 작업을 처리할 수 있다. 큐에서 정점을 하나씩 꺼내면서 정점을 출력..

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-..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 [SWEA 1215] 회문1 C++ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 "기러기" 또는 "level"과 같이 거꾸로 읽어도 앞에서부터 읽은 것과 같은 문장이 woojeenow.tistory.com 회문1에서는 8x8 평면 글자판에서 제시된 길이의 회문의 총 개수를 구했지만 회문2에서는 100x100 평면 글자판에서 가장 긴 회문의 길이를 구해야한다. 회문1에서와 달리 회문의 길이가 정해져있지 않으므로 길이가 2인 회문부터 길이가 100인 회..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 "기러기" 또는 "level"과 같이 거꾸로 읽어도 앞에서부터 읽은 것과 같은 문장이나 낱말을 회문(palindrome)이라 한다. 주어진 8x8 평면 글자판에서 가로, 세로를 모두 보아 제시된 길이를 가진 회문의 총 개수를 구하는 문제다. 제시된 길이만큼의 문자들이 회문인지 확인하기 위해서는 n - len 이하까지만 탐색해주면 된다. 이해하기 쉽도록 길이가 4인 회문을 찾는 예제를 그림으로 살펴보자. 보라색 박스는 회문 시작 위치, 노란색 박스는 회문 검사를 하는 문자열을 의미한다. 가로 검사를 할 때에는 0부터 7번 행까지 모두 검사를 진행해주어야 하..