유자의 코딩모험

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번 행까지 모두 검사를 진행해주어야 하..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 주어지는 영어 문장에서 특정한 문자열의 개수를 찾는 문제다. string 라이브러리의 find 함수를 쓰면 간단하게 찾을 수 있다. size_t find(const string& str, size_T pos) const; str : 찾고자 하는 문자열 pos : 검색을 시작할 위치 문자열을 찾았다면, 해당 문자열의 시작 위치를 리턴하고, 그렇지 않을 경우 npos 리턴 string::npos란? size_type으로 정의된 특수값이다. string::npos란 -1 값을 가지는 상수로 find() 함수 수행 시에 찾는 문자열이 없을 때 반환된다. find..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 테이블 위에 자성체들이 있다. 푸른 자성체의 경우 N극에 이끌리는 성질을 가지고 있고, 붉은 자성체의 경우 S극에 이끌리는 성질이 있다. 테이블에서 일정 간격을 두고 강한 자기장을 걸었을 때, 시간이 흐른 뒤에 자성체들이 서로 충돌하여 테이블 위에 남아있는 교착 상태의 개수를 구하는 문제다. 화살표와는 상관없이 N극, S극 쌍을 찾는 문제로 그림에서는 7개이다. 처음에는 어렵게 생각해서 A, B와 같은 자성체들은 없애고 남은 자성체들을 모아서 카운트하려 했다. 하지만 그렇게 하니 정답이 잘 안나와서 다른 방법을 생각하게 되었다. N극, S극 쌍을 찾는 문..