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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다..

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식. 일종의 트리 탐색 알고리즘DFS, BFS, 최선우선탐색 tip) 백트래킹 문제는 N이 작다 (10 언저리)재귀함수 사용할 때, 종료 시점 잊지 말기! 예제)백준 15649 N과 Mhttps://www.acmicpc.net/problem/15649 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출..

△다이나믹 프로그래밍, 최대부분배열 - 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(..

○Dynamic Programming - Easy LeetCode 746. Min Cost Climbing Stairs 문제You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.You can either start from the step with index 0, or the step with index 1.Return the minimum cost to reach the top of the floor.Constraints:• 2 • 0 내 답안시간 O(n), 공간복잡도 O(n)배열을 사용..

○슬라이딩 윈도우 - 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: ..

△Hash Table, Sliding Window - Medium LeetCode 3. Longest Substring Without Repeating Characters 문제Given a string s, find the length of the longest substring without duplicate characters.이게 슬라이딩 윈도우 문제라고..? 전혀 모르겠는딩.. 1차 시도 - 실패중복이 발생했을 경우에 대한 로직은 잘 구현했으나, 중복이 없을 경우에 처리하는 걸 빠뜨림..→ 마지막에 return 할 때 max(result, arr.count - start) 이렇게 다시 비교를 해줘야 한다. func lengthOfLongestSubstring(_ s: String) -> Int ..

×투 포인터 - 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[..

△Level 2 연습문제 (투 포인터) Programmers 연속된 부분 수열의 합 아아아주 오랜만에 다시 잡은 펜.. 머리가 다 굳은건가 하핳하 투 포인터를 사용해 시작점과 끝점을 오른쪽으로 이동하며 합이 k인 수열의 index를 구하는 문제sequence[end] 더해주기 전에 end 더해주기 전에 값이 있는 index인지 먼저 확인 해주기! func solution(_ sequence:[Int], _ k:Int) -> [Int] { var start: Int = 0 var end: Int = 0 var sum: Int = sequence.first ?? 0 var result: [Int] = [] while end (end - start) { ..