본문 바로가기

Problem Solving/SWEA147

[SWEA] 1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기 문제 4 종류의 괄호문자들 '()', '[]', '{}', '' 로 이루어진 문자열이 주어진다. 이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다. 예를 들어 아래와 같은 문자열은 유효하다고 판단할 수 있다. 아래와 같은 문자열은 유효하지 않은 문자열이다. 붉은색으로 표시된 괄호의 짝을 찾을 수 없기 때문이다. 아래 문자열은 열고 닫는 괄호의 개수는 유효하나 짝이 맞지 않는 괄호가 사용 되었기 때문에 유효하지 않다. 풀이방법 스택을 이용해 해결한다. 1) '{' , '[' , '', ')' 닫는 기호가 나올 경우 스택에 담겨진 top의 기호와 쌍을 이루는지 확인한다. 3) 2의 조건을 만족하면 pop으로 스택의 top을 삭제한다. 4) 모든 입력을 다 받아들인 후 스택이 비었다면.. 2020. 3. 5.
[SWEA] 7829. 보물왕 태혁 문제 보물 왕 태혁은 세상의 모든 보물을 숨겨놓은 창고를 만들었다. 그리고 잠금 장치에 비밀번호 숫자 N 을 등록하려고 한다. 하지만 숫자를 까먹으면 자기 자신도 보물을 찾을 수 없다는 사실을 깨달았다. 그렇다고 숫자 그대로를 적으면 위험하다. 숫자를 까먹지 않기 위해 특별한 방법으로 종이에 적어 놓았다. 그 특별한 방법이란, 숫자 N 의 약수를 적어놓는 것이다. 숫자의 모든 약수를 따로 보관하여 숨길 계획이다. 단, 1과N 은 적지 않았다. 10년 뒤, 보물을 찾으러 온 태혁은 암호를 입력해야 했는데 역시나 까먹어버렸다. 다행히 약수들이 적혀있는 종이를 가지고 있다. 종이에 써져 있는 약수들을 보고 원래 숫자를 만들어 내자. 풀이방법 DFS(깊이 우선 탐색)을 이용해 n개의 숫자 중 중복을 허용한 두개.. 2020. 3. 4.
[SWEA] 1227. [S/W 문제해결 기본] 7일차 - 미로2 문제 아래 그림과 같은 미로가 있다. 100*100 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다. 가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다. 주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라. 아래의 예시에서는 도달 가능하다. 아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다. 위의 예시는 공간상의 이유로 100x100이 아닌 16x16으로 주어졌음에 유의한다. 풀이방법 DFS(깊이 우선 탐색)을 이용해 문제 해결. 2의 값이 저장된 노드를 중심으로 상, 하.. 2020. 3. 4.
[SWEA] 1226. [S/W 문제해결 기본] 7일차 - 미로1 문제 아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다. 가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다. 주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라. 아래의 예시에서는 도달 가능하다. 아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다. 풀이방법 DFS(깊이 우선 탐색)을 이용해 문제 해결. 2의 값이 저장된 노드를 중심으로 상, 하, 좌, 우 갈 수 있는 노드를 탐색하며 모든 경로를 찾는다. 모든 경로를 찾았을 때, 3.. 2020. 3. 4.
[SWEA] 1219. [S/W 문제해결 기본] 4일차 - 길찾기 문제 그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다. 길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다. 다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라. - A와 B는 숫자 0과 99으로 고정된다. - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다. - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다. - 단 화살표 방향을 거슬러 돌아갈 수는 없다. 풀이방법 DFS(깊이 우선 탐색)을 이용해 문제 해결. 입력에 따라 각 노드와 간선을 나타.. 2020. 3. 4.
[SWEA] 1224. [S/W 문제해결 기본] 6일차 - 계산기3 문제 문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오. 예를 들어 “3+(4+5)*6+7” 라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다. "345+6*+7+" 변환된 식을 계산하면 64를 얻을 수 있다. 문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다. 이 때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다. 피연산자인 숫자는 0 ~ 9의 정수만 주어진다. 풀이방법 문제에서는 2가지를 요구하고 있다. 주어진 계산식을 후위표기식으로 바꾸는 것과 후위표기식으로 바꾼 식을 계산하는 것이다. [1. 주어진 계산식을 후위표기식으로 바꾸는 것] 후위 표기식으로 바꾸기 위해서는 스택을 이용한다. 주.. 2020. 3. 4.
[SWEA] 1223. [S/W 문제해결 기본] 6일차 - 계산기2 문제 문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오. 예를 들어 “3+4+5*6+7” 라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다. "34+56*+7+" 변환된 식을 계산하면 44를 얻을 수 있다. 문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 피연산자인 숫자는 0 ~ 9의 정수만 주어진다. 풀이방법 문제에서는 2가지를 요구하고 있다. 주어진 계산식을 후위표기식으로 바꾸는 것과 후위표기식으로 바꾼 식을 계산하는 것이다. [1. 주어진 계산식을 후위표기식으로 바꾸는 것] 후위 표기식으로 바꾸기 위해서는 스택을 이용한다. 주어진 계산식을 한 글자씩 읽어들일 때, 숫자일 경우 그대로 출력하고, '+' 또는 '*' 기호일 경우.. 2020. 3. 4.
[SWEA] 1222. [S/W 문제해결 기본] 6일차 - 계산기1 문제 문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오. 예를 들어 “3+4+5+6+7” 라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다. "34+5+6+7+" 변환된 식을 계산하면 25를 얻을 수 있다. 문자열 계산식을 구성하는 연산자는 + 하나뿐이며 피연산자인 숫자는 0 ~ 9의 정수만 주어진다. 풀이방법 문제에서는 2가지를 요구하고 있다. 주어진 계산식을 후위표기식으로 바꾸는 것과 후위표기식으로 바꾼 식을 계산하는 것이다. [1. 주어진 계산식을 후위표기식으로 바꾸는 것] 후위 표기식으로 바꾸기 위해서는 스택을 이용한다. 주어진 계산식을 한 글자씩 읽어들일 때, 숫자일 경우 그대로 출력하고, '+'기호일 경우 스택에 담거나 출력한.. 2020. 3. 4.
[SWEA] 7584. 자가 복제 문자열 문제 문자열 P는 스스로를 계속 복제해서 매우 긴 문자열이 되었다. 복제하는 방법은 다음과 같다. P0 = “0” Pi+1 = Pi + “0” + f(g(Pi)) 여기서, f(A) 함수는 문자열 A의 모든 문자를 반전시킨다. 예를 들어서, f(“10110”) = “01001”이다. g(A)함수는 문자열 A를 좌우 반전 시킨다. 예를 들어서, g(“10110”) = “01101” 이다. 위와 같은 복제 방법을 무한히 반복한 문자열 P의 K번째 문자가 무엇인지 구하여라. 풀이방법 주어진 시간은 2초, 입력이 최대 10^18이므로 반복문, 재귀를 사용할 생각을 일찍이 버린다. 주어진 문제를 해결할 수 있는 규칙을 찾는다. P1 = “001” P2­ = “0010011” P3 = “001001100011011”.. 2020. 3. 4.
[SWEA] 6190. 정곤이의 단조 증가하는 수 문제 정곤이는 자신이 엄청난 수학자임을 증명하기 위해, 어떤 규칙 만족하는 수를 찾아보기로 했다. 그 규칙은 단조 증가하는 수인데, 각 숫자의 자릿수가 단순하게 증가하는 수를 말한다. 어떤 k자리 수 X = d1d2…dk 가 d1 ≤ d2 ≤ … ≤ dk 를 만족하면 단조 증가하는 수이다. 예를 들어 111566, 233359는 단조 증가하는 수이고, 12343, 999888은 단조 증가하는 수가 아니다. 양의 정수 N 개 A1, …, AN이 주어진다. 1 ≤ i < j ≤ N 인 두 i, j에 대해, Ai x Aj값이 단조 증가하는 수인 것들을 구하고 그 중의 최댓값을 출력하는 프로그램을 작성하라. 풀이방법 완전탐색으로 해결 n개의 숫자가 입력으로 주어졌을 때, 각 숫자의 곱이 단조 숫자인 값을 모두 .. 2020. 3. 4.
[SWEA] 3750. Digit sum 문제 자연수 n에 대해 함수 f(n)은 n의 각 자릿수를 더한 값이다. 예를 들어 n = 588432라면, f(n) = 5 + 8 + 8 + 4 + 3 + 2 = 30인 것이다. 어떤 자연수 n이 주어질 때, n이 한 자리수가 될 때까지 n에 f(n)을 대입하는 것을 반복하면, 최종적으로 n이 어떤 값이 되는지 구하는 프로그램을 작성하라. 예를 들어 n = 588432라면 f(n) = 30이므로 n = 30이 되고, 이 때 f(n) = 3으로 최종적으로 n = 3이 되는 것이다. 풀이방법 1) 숫자를 문자열로 입력받고 각 자리수를 더해서 새로운 문자열로 만든다. 2) 문자열의 길이가 1이 될 때까지 1)의 과정을 반복한다. 3) 문자열의 길이가 1일 때 값을 출력한다. 소스코드 package samsun.. 2020. 3. 4.
[SWEA] 7853. 오타 문제 방송사에서 생방송 자막 송출을 담당하고 있는 재경이는 한글 타자가 무려 1000에 육박한다. 누구보다 빠른 한글 타자를 보유하고 있지만 치명적인 단점이 있다. 영어 타자의 오타가 극심하게 발생한다. 재경이는 어떤 단어를 쓸 때에 오타를 특정한 방법으로 발생시킨다. 치고자 하는 단어와 길이는 동일한 단어를 쓰지만, i번째 문자에다가 원래 단어의 (i-1) 번째, i 번째, (i+1) 번째 문자 중 무엇이든 쳐버린다. 특히 제일 첫 문자는 첫 문자와 그 다음 문자 중 하나를 쓸 수 있고, 마지막 문자는 마지막과 그 앞의 문자를 쓸 수 있다. 예를 들어서, apa 라는 단어에서 재경이가 낼 수 있는 오타는 aaa, aap, apa, app, paa, pap, ppa, ppp 중 하나를 칠 수 있는 것이다.. 2020. 2. 29.

티스토리툴바