Outgoing Introvert

△백트래킹, 재귀, 수학 - Silver 2 백준 6603 로또문제독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다..

△다이나믹 프로그래밍, 최대부분배열 - Silver 2백준 1921 연속합문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 예외 케이스를 잘 생각해야 하는 문제 // 76112KB 28mslet n = Int(readLine(..

○슬라이딩 윈도우 - Silver 2 백준 12891 DNA 비밀번호 문제평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 ..

○누적합, 슬라이딩 윈도우 - Silver 3 백준 21921 블로그 문제블로그 시작한 지 n일x일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는가?출력x일 동안 가장 많이 들어온 방문자 수 출력. 최대 방문자 수 0명이라면 SAD 출력0이 아니라면 기간이 몇 개 있는지 출력 내 답안1. 누적합 구하기2. 윈도우 오른쪽 index를 하나씩 늘려나가며 2-1. 합이 더 크면 최대합 갱신, count 초기화 2-2. 합이 같으면 count += 1// 84696KB 88mslet nx = readLine()!.split(separator: " ").map { Int($0)! }let n = nx[0], x = nx[1]let visits = readLine()!.split(separator: ..

×투 포인터 - Silver 2 백준 14246 K보다 큰 구간 문제n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j] (i≤j)의 합이 k보다 큰 모든 쌍 (i, j)의 개수를 출력하시오. 첫 번째 시도 - 실패더보기1. 누적합 구하기2. 누적합 배열의 구간 합이 k 보다 큰 구간 찾기 -> 누적합 배열의 구간 합을 구하는 방식이 틀렸다. sum = arr[end] 해주면 항상 0~end 구간의 합을 가지게 되므로.. [start, end] 구간의 합을 계산해야 한다..!* sum 이 k보다 크면 result += (n - end) 해준 건 잘했음. let n = Int(readLine()!)!let input = readLine()!.split(separator: " ").compact..

○투 포인터, 누적 합 - Silver 4 백준 2003 수들의 합 2 문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. // 70012KB 8mslet input = readLine()!.split(separator: " ").compactMap { Int($0) }let n = input[..

○정렬 - Silver 4 (30분) 백준 1764 듣보잡문제김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.입력첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.출력듣보잡의 수와 그 명단을 사전순으로 출력한다. 첫번째 시도 - 시간초과당연히 시간초과 뜰 걸 알았지만..

△다이나믹 프로그래밍 - Silver 3 (50분) 백준 1463 1로 만들기문제1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 첫 번째 시도 엥 이게 왜 실버 3이지? 아주 순수하게 3의 배수이면 3으로 나누고, 2의 배수이면 2로 나누고 둘 다 아니면 -1 을 순서대로 해주었더니10에서 3이 아닌 4가 출력이 되어버린다.. 풉 이렇게 쉬울 줄 알았니?  두 번째 시도그렇다면 거꾸로 해보자 1에서 부터 시작해 n을 넘지 않을 때까지 3을 곱해주거나, 2를 곱해주거나, +1을 해주거나이렇게 하면 어떻게 되는거지..

○수학 - Bronze 1 (20분) 백준 28702 FizzBuzzi = 1,2,3 ...- i가 3의 배수 && 5의 배수이면 FizzBuzz- 3의 배수면 Fizz- 5의 배수면 Buzz- 아니면 그냥 i 그대로 출력연속으로 출력된 세 개의 문자열 다음에 올 문자열을 출력하세요. 연속 세 개면 그 중에 하나만 숫자라도 다음에 올 문자열을 구할 수 있다. 입력 값 받아오면서 숫자가 들어오면 바로 결과값을 구해주도록 해주었다. index가 0이면 num + 3, 1이면 +2, 2이면 +1 => 결과값 숫자는 num + (3 - i)15의 배수면 FizzBuzz, 3의 배수면 Fizz, 5의 배수면 Buzz 아니면 결과값 그대로 출력var result = 0for i in 0..

○수학, 정렬 - Silver 3 (40분) 백준 2108 통계학문제1. 산술평균 : N개의 수들의 합을 N으로 나눈 값2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.출력첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.둘째 줄에는 중앙값을 출력한다.셋째 줄에는 최빈값을 ..