본문 바로가기

PS 문제 풀이/SWEA75

[SWEA] 3950 괄호 출처: [SWEA] SW 문제해결 심화 - 증명의 중요성 Input 2 2 )( 10 )))))((((( Output #1 2 1 1 0 0 #2 2 0 4 5 9 ※ 첫번째 Test Case와 같이 적용한 연산 순서가 다르더라도 동일한 결과를 가지고 있는 경우가 있는데, 이 경우 어떤 순서로 해도 상관 없습니다. 누적 합 이용하여 문제를 해결할 수 있습니다. ※ 문자열의 길이가 홀수라면 괄호가 유효하지 않습니다. ① 『 ( 』 과 『 ) 』 을 각각 1과 -1로 계산하여 누적합을 구합니다. ) ( ( ( ) ( → -1 1 1 1 -1 → 누적합: -1 0 1 2 1 ② 누적 합 중 음수이면서 제일 작은 값의 위치 pos를 구합니다. 존재하지 않는다면 ④단계로 넘어갑니다. (존재한다면 전체 구간의 최솟.. 2021. 3. 1.

[SWEA] 4039 두 번 이상 등장하는 문자열 출처: [SWEA] SW 문제해결 심화 - 문자열 알고리즘 Input 3 11 sabcabcfabc 18 trutrutiktiktappop 6 abcdef Output #1 3 #2 4 #3 0 한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에 가장 긴 문자열의 길이를 출력하는 문제입니다. 구현 Suffix Array를 이용하여 LCP Array를 구합니다. ① 접미사 배열 (Suffix Array) ② LCP (Longest Common Prefix) LCP Array 중 최댓값을 구합니다. import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOEx.. 2021. 3. 1.

[SWEA] 4040 문자열의 거듭제곱 출처: [SWEA] SW 문제해결 심화 - 문자열 알고리즘 Input 3 abcd aaaa ababab Output #1 1 #2 4 #3 3 ▶ (abcd)1 / (a)4 / (ab)3 주어진 문자열에서 최대한 짧은 부분 문자열을 거듭 이용해서 전체 문자열을 만들어야 합니다. ex) "abababab"는 "ab"를 4번 반복하면 만들 수 있습니다. KMP알고리즘에서 실패 함수 테이블의 맨 마지막 값을 구합니다. ※ [BOJ] 4354 문자열 제곱 [BOJ] 백준 4354 문자열 제곱 출처: https://www.acmicpc.net/problem/4354 Input abcd aaaa ababab . Output 1 4 3 ▶ (abcd)1 / (a)4 / (ab)3 주어진 문자열에서 최대한 짧은 부분 .. 2021. 3. 1.

[SWEA] 1218 괄호 짝짓기 출처: [SWEA] 1218 괄호 짝짓기 Input 182 (({ 2021. 3. 1.

[SWEA] 3996 Poker 출처: [SWEA] SW 문제해결 심화 - Counting & Probability Input 1 S 1 S 10 D 11 H 10 C 2 H 2 S 11 Output #1 2 Pair Poker 카드 7장 중에서 5장을 선택합니다. 해당 문제에서 카드의 족보는 다음과 같습니다. (번호가 높으수록 높은 등급) (0) Top : 가장 낮은 족보 (1) 1 Pair : 같은 숫자가 한 쌍 존재 (2) 2 Pair : 각기 같은 숫자가 두 쌍 존재 (3) Triple : 세 개의 같은 숫자가 존재 (4) Straight : 숫자 5개가 연속 존재 (5) Flush : 같은 무늬 5장이 존재 (6) Full House : Triple과 Pair가 함께 존재 (7) 4 Card : 네 개의 같은 숫자가 존재 (8.. 2021. 3. 1.

[SWEA] 4041 Convex 출처: [SWEA] SW 문제해결 심화 - 계산기하학 Input 1 8 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 Output #1 5 2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질(CONVEX HULL)라고 합니다. - Test Case 개수 T - 점의 개수 N (3 ≤ N ≤ 100,000) - (N 줄에 거쳐) 점의 좌표 (x, y) (-100,000 ≤ x, y ≤ 100,000) ← 모든 점의 좌표는 다르다는 것을 보장하며 일직선을 이루는 경우는 X ▶ 블록 껍질(Convex Hull)을 이루는 점의 개수 출력 ※ 블록 껍질의 변에 점이 여러 개 있는 경우에는 가장 .. 2021. 3. 1.

[SWEA] 3951 CRT 출처: [SWEA] SW 문제해결 심화 - 이산수학 Input 1 2 1 3 2 5 Output #1 7 A ≡ bi mod(Ni) 관계에서 bi 와Ni 주어졌을 때, A를 만족하는 가장 작은 음이 아닌 정수 값을 찾으시오. A는 A mod Ni = bi 가 되는 모든 값입니다. ex) bi=2, Ni=3 이라면 A는 2, 5, 8, 11, 14 … 3k+2(k는 자연수)가 될 수 있다. - Test Case 개수 T / 식의 개수 M / (M줄에 거쳐) bi 와 Ni 가 주어집니다. ▶ Chinese Remainder Theorem을 구현하는 문제입니다. - 1 mod(3): 4 7 10 13 16 ... - 2 mod(5): 2 7 12 17 22 ... [예시 1] x = 5 (mod 6) / x .. 2021. 3. 1.

[SWEA] 3993 Pole 출처: [SWEA] SW 문제해결 심화 - Counting & Probability Input 4 4 1 2 4 1 1 5 2 4 20 2 1 Output #1 2 #2 0 #3 4 #4 6402373705728000 Test Case 개수 / (N, L, R)이 주어집니다. - 1~N까지의 높이를 가지는 막대가 일직선상에 존재합니다. (같은 높이 존재 X) - 왼쪽에서 보여지는 막대 개수 L과 오른쪽에서 보여지는 막대 개수 R이라고 했을 때, 가능한 막대 순서의 경우의 수를 구하시오. (1 ≤ N ≤ 20) ex) N=5, L=3, R=2일 때, 가능한 막대의 배치 중 하나는 {1 3 5 2 4} 입니다. ※ [BOJ] 1328 고층빌딩 [BOJ] 백준 1328 고층빌딩 출처: https://www.a.. 2021. 3. 1.

[SWEA] 3998 Inversion Counting 출처: [SWEA] SW 문제해결 심화 - Counting & Probability Input 1 5 4 1 3 2 5 Output #1 4 (4, 1), (4, 3), (4, 2), (3, 2) 이렇게 총 4개입니다. 『Inversion』 상태인 i A[j] 경우를 찾는 것은 병합 정렬 이용합니다. ※ [BOJ] 10090 Counting Inversions [BOJ] 백준 10090 Counting Inversions 출처: https://www.acmicpc.net/problem/10090 Input 7 4 2 7 1 5 6 3 Output 10 ▷ (4,2) (4,1) (4,3) (2,1) (7,1) (7,5) (7,6) (7,3) (5,3) (6,3) 총 10개 완전탐색.. 2021. 3. 1.

[SWEA] 3813 그래도 수명이 절반이 되어서는.... 출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다.. 2021. 3. 1.

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바