본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 4949 균형잡힌 세상 (Swift) 문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 풀이 Stack 자료구조를 사용해서 풀이할 수 있습니다. 먼저 문자열을 하나씩 살펴보면서 "[", "]", "(", ")" 가 아니라면, 살펴보지 않았습니다. 문자열이 괄호이고 Stack의 Top이 "[" 이고, 현재 문자열이 "]"라면 "[]"으로 짝이 맞게 되므로 Stack의 삭제연산을 해주었습니다. 마찬가지도 소괄호도 같은 역할을 해주었습니다. 둘다 아니라면 스택에..
[BOJ] 백준 9012 괄호 (Swift) 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 이 문제는 Stack를 사용하는 Well-Known 문제입니다. Stack이 비어있다면, 어떤 괄호이든지 상관없이 Stack에 삽입해주었습니다. Stack이 비어있지 않고, Stack의 top이 "(" 이고, 현재 문자열이 ")"라면 "()"로 올바른 괄호가 되기 때문에 Stack의 마지막 요소 "("를 삭제 해주었습니다. Stack이 비어있지 않고, 들어..
[BOJ] 백준 10773 제로 (Swift) 문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 정수가 "0"일 경우 가장 최신에 쓴 수를 지운다는 것을 보고, Stack 자료구조를 떠올릴 수 있습니다. 총 k번의 입력을 받으면서 정수가 "0"일 경우는 removeLast 메서드를 사용해 가장 최신에 삽입된 요소를 삭제시켜주고, "0"이 아니라면 삽입해줍니다. k번의 입력이 끝난 후, 배열의 요소의 합을 출력해주면 되는 문제입니다. 정수가 "0"일..
[BOJ] 백준 10828 스택 (Swift) 문제 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 스택 자료구조를 사용해서 풀 수 있는 문제입니다. 스택 자료구조를 모른다면 이 글을 한 번 읽어보시면 도움이 될 것입니다. https://dev-mandos.tistory.com/184 [자료구조] Stack에 대해 알아보고 구현해보기 (Swift) Stack이란? Stack 자료구조는 후입선출(Last In First Out)LIFO 의 특성을 갖는 자료구조 입니다...
[BOJ] 백준 1037 약수 (Swift) 문제 https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 풀이 1과 N을 제외하고 약수들이 주어졌을 때, N을 구하는문제입니다. N = 가장 작은 약수 * 가장 큰 약수 이므로, 이것을 출력해주면 끝입니다. 소스코드 후기 약수의 성질에 대해 생각해본다면 쉽게 풀 수 있는 문제입니다.
[BOJ] 백준 1010 다리 놓기 (Swift) 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 문제를 잘 살펴보면 조합의 수를 구하는 문제라는 것을 이해할 수 있습니다. 즉, $_mC_n$을 구하는 문제입니다. $mCn = \frac{m!}{n!(m-n)!$ 을 구해주면 되겠죠? 하지만 입력이 최대 30이므로, $30! = 2.6525285981×10^{32}$이므로 Int 자료형의 범위를 넘어갑니다. 조합의 성질을 이용해서 구해주어야 합니다. $nC_0 = 1, _nC_n = ..
[BOJ] 백준 11050 이항 계수 1 (Swift) 문제 https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 이항계수란 뭘까요? $(x + y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5$ 입니다. 이항계수는 다항식의 거듭제곱을 정리하였을 때, $x^{n-k}y^{k}$의 계수를 뜻합니다 n이 5, k가 2라면? $10x^3y^2$ 이므로 10이겠죠?? 또한, 이항계수는 $\frac{n!}{k!(n-k)!}$으로 구할 수 있습니다. 이 수식을 이용하면 답을 구할 수 있습니다. 소스코드 후기 이항 계수가 뭔지 몰라서.. ..
[BOJ] 백준 15439 Vera and Outfits (Swift) 문제 https://www.acmicpc.net/problem/15439 15439번: Vera and Outfits Vera owns N tops and N pants. The i-th top and i-th pants have colour i, for 1 ≤ i ≤ N, where all N colours are different from each other. An outfit consists of one top and one pants. Vera likes outfits where the top and pants are not the same colour. www.acmicpc.net 풀이 문제를 해석해보면 상의, 하의를 다른 색으로 입는 조합의 경우를 구하는 문제입니다. 예를 들어 N이 3이라면,..
반응형

티스토리툴바