[Java] Boj 11723: 집합
·
PS/Solve
문제https://www.acmicpc.net/problem/11723 풀이 집합과 관련된 클래스 3의 문제 중 하나이다. 입력되는 연산들에 대응하는 집합 관련 연산을 수행하면 된다. 집합에 수 추가하기, 집합에서 수 제거하기, 집합에 해당 숫자 있는지 확인하기, 집합에 수가 있는지 확인하고 있다면 삭제 - 없다면 추가하기, 집합을 다른 집합으로 바꾸기, 집합을 공집합으로 바꾸는 연산을 수행해야 하는데 차근차근 해보자. 먼저 집합은 수의 존재 유무를 확인하기 위해 HashSet을 이용해 구현하였다. Hashset 자료구조의 특성 상 저장하는 데이터가 중복 저장되지 않으므로 사용하였다. add x, remove x 연산은 그냥 각각 해시 셋에 x를 추가하고 x를 삭제해주면 된다. check x 연산은 해..
[Java] Boj 10026: 적록색약
·
PS/Solve
문제https://www.acmicpc.net/problem/10026 풀이 R, G, B로 이루어진 N*N 크기의 배열이 주어지고, 같은 색으로 이루어진 구역의 색상이 몇 개인지 알아내는 문제이다. 이렇게만 보면 잘 와닿지 않으니 문제의 입력을 하나 가져오겠다.RRRBBGGBBBBBBRRBBRRRRRRRR 위 경우에서 R, G, B로 이루어진 구역을 찾을 때, 상하좌우로 인접한 문자가 같으면 같은 구역이다. 그래프 탐색을 활용하여 문제를 해결할 수 있다. Character 타입을 저장할 배열 arr와 방문 여부를 확인할 boolean 타입 visit 배열을 사용해 배열 탐색을 하면 된다. 탐색 기준을 arr 배열 현재 칸의 문자와 다음에 탐색할 칸의 문자와 비교하여 두 문자가 똑같다면 그 칸에서 이어서..
[Java] Boj 1541: 잃어버린 괄호
·
PS/Solve
문제https://www.acmicpc.net/problem/1541 풀이 본래 양수, +, -, 괄호를 가지고 만든 수식에서 괄호를 몽땅 지웠을 때, 다시 괄호를 적절히 삽입해 이 식의 계산 결과 값을 가장 작게 만드는 문제이다. 입력으로 괄호를 지운 수식이 주어지고, 출력으로는 괄호를 삽입한 수식의 가장 작은 결과 값을 출력하면 된다. 문제에서 주목할 점은 수행하는 연산이 +, - 두 가지뿐이라는 것이다. 그렇다면 이 경우에서 결과를 가장 작게 만드는 방법은 무엇일까? - 연산이 있을 때, - 연산 뒤의 값을 연속된 덧셈 연산들끼리 몽땅 묶어서 빼는 값을 크게 만들어주면 된다. 즉, - 연산이 한번 등장하였을 때, 뒤에 등장하는 +를 모두 -로만 바꿔주면 수식의 결과 값을 최소로 할 수 있다. 아래..
[형식언어] 결정적 유한 오토마타
·
CS/형식언어
유한 오토마타(FA) 이전 포스팅에서 정규 문법이 주어지면 이 문법이 생성하는 언어를 알 수 있다고 하였다. 즉, 정규 문법을 정규 표현식으로 치환하여 정규 문법이 생성하는 언어를 알 수 있다. 이제는 형식언어론의 꽃, 유한 오토마타를 알아보자. 일반적으로 언어에 대한 인식기(recognizer)는 입력으로 스트링을 받아서 이 스트링이 그 언어의 문장이면 "Yes", 아니라면 "No"를 답한다. 이러한 인식기 중 가장 간단한 형태는 Finite Automata라 불리는 유한 오토마타이며, 유한 오토마타는 어휘 분석기 구현에 사용된다. 문법은 nonterminal 심벌, terminal 심벌, 시작 심벌, 생성 규칙으로 총 4개의 요소로 구성되는 반면 유한 오토마타(FA)는 5개의 요소로 정의된다. ..
[Java] Boj 9375: 패션왕 신해빈
·
PS/Solve
문제https://www.acmicpc.net/problem/9375 풀이 옷과 옷의 종류를 입력받고 같은 종류의 옷은 하나만 입을 수 있을 때, 입을 수 있는 옷의 조합 종류를 출력하는 문제이다. 문제를 보고 든 생각은 입력받은 옷들이 종류별로 몇 가지 있는지만 알면 바로 풀 수 있는 문제로 보였다. 옷이 종류별로 몇 가지 있는지 판정은 해시 맵을 이용하면 된다. 똑같은 옷이 입력으로 들어오지 않으니 단순히 한 종류의 옷이 몇 개 있는지만 알면 된다. 한 종류의 옷이 몇 개 있는지는 해시 맵을 이용해 구현 가능하니, 이제는 의상 조합 수를 따져보자. 상의 3개, 하의 4개, 모자 3개가 있을 때 조합 가능한 옷의 경우의 수는 (3 + 1) * (4 + 1) * (3 + 1) = 80가지가 될 것이다..
[형식언어] 정규 표현
·
CS/형식언어
정규 표현 정규 표현(regular expression)은 정규 언어를 표현하기 위한 한 방법으로, 정규 언어에 속해 있는 스트링의 모양을 직접 기술하는 형태를 가진다. 정규 표현의 기본 소자는 Φ, ε, 그리고 terminal 심벌이다. Φ는 공집합을, ε은 집합 { ε }, a ∈ VT는 집합 { a }를 나타내는 정규 표현이다. 만일 e1과 e2가 정규 언어 L1, L2를 나타내는 정규 표현이라면, (e1) + (e2)는 L1∪L2를, (e1) ∙ (e2) L1 ∙ L2를, (e1)* L1* = { ε } ∪ L11 ∪ L12 ∪ ... ∪ L1n ∪ ...인 , 즉 closure를 의미한다. 여기서 union 연산에 해당하는 + 연산은 교환법칙이 성립하며, 접속 연산인 concatenation..
[Java] Boj 2108: 통계학
·
PS/Solve
문제https://www.acmicpc.net/problem/2108 풀이 한창 PS를 시작할때 쉬워보여 도전했다가 한 부분에서 두드려맞고 포기했던 문제인데, 프린터 큐 문제와 함께 클래스 2에 남아있길래 한번 도전해보았다. 문제는 입력받는 값들에 대해 산술평균, 중앙값, 최빈값, 범위를 출력하는 것으로, 최빈값이 여러개 있다면 두 번째로 작은 최빈값을 출력해야 하는 조건이 있다. 산술평균은 반올림한 값을 출력해야 하므로 Math 라이브러리의 round를 이용하여 해결하였고, 중앙값과 범위는 사실 어려운 부분이 하나도 없다. 제일 까다로운 부분은 최빈값을 구하는 부분인데, 최빈값이 하나라면 그 값만 출력하면 되지만 최빈값이 여러개라면 두 번째로 작은 값을 출력해야 하는 것이 조금 까다롭게 다가왔다. ..
[Java] Boj 1966: 프린터 큐
·
PS/Solve
문제https://www.acmicpc.net/problem/1966 풀이 큐를 프린터처럼 사용하는 문제이다. 큐에 중요도를 집어넣고 큐의 앞에서부터 중요도가 가장 높은 문서부터 뽑아내는데, 이때 큐 내부에 맨 앞 문서의 중요도보다 높은 중요도의 문서가 큐에 존재한다면 이 문서를 큐의 맨 뒤로 이동시켜야 한다. 이와 같은 과정을 거치며 제시하는 문서 번호가 몇 번째에 출력되는지 알아보는 문제이다. 일단 문제의 흐름은 문서의 번호와 중요도를 큐에다 저장해야 하므로 문서 번호와 중요도를 저장할 클래스를 하나 만들고, 이를 큐에다가 일단 몽땅 넣어주었다. 그리고 문제를 해결하려 하는데 큐의 맨 앞에서 뽑은 중요도보다 다른 문서의 중요도보다 작은지, 같은지 검사를 어떻게 해야할까..? 하는 생각이 들었다. 문..