Outgoing Introvert

○ (투포인터 ×) Two Pointers, Sorting | Medium 922. Sort Array By Parity II 문제 Given an array of integers nums, half of the integers in nums are odd, and the other half are even. Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even. Return any answer array that satisfies this condition. Constraints - 2

개발을 하거나 코딩테스트 문제를 풀 때, 특정 코드가 실행되는 시간을 구하고 싶을 때가 있다. 아래의 함수들을 이용해 코드의 수행시간을 측정할 수 있다. 1. CFTimeInterval public func progressTime(_ closure: () -> ()) -> TimeInterval { let start = CFAbsoluteTimeGetCurrent() closure() let duration = CFAbsoluteTimeGetCurrent() - start return duration } progressTime { //실행 시간 측정할 코드 } 2. Date public func measureTime(_ closure: () -> ()) -> TimeInterval { let startD..

○ (dp ×) Dynamic Programming, Memoization, Sorting | Medium LeetCode 1387. Sort Integers by The Power Value Constraints: - 1

○ Stack, HashTable | Easy 496. Next Greater Element I 문제 The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0

○ Hash Table, 조합 | Easy 2506. Count Pairs Of Similar Strings 문제 해결이 어렵진 않은데, 조합 구현 공식은 컨닝함.. ㅎㅎ 영어가 문제인가 문제 설명이 문제인가.. 처음에 읽어보고 뭐라는건지 모르겠어서 포기할 뻔 했쟈나 이해하고 나면 간단함. 1. words 안의 각 문자열들을 Set으로 중복 제거하고, sort로 정렬하고 다시 문자열로 만들어준다. 2. 위의 변환 과정을 거친 문자열을 딕셔너리의 키 값으로 넣어 주고, 같은 문자열일 경우 값을 1씩 더해준다. 3. 딕셔너리에 저장된 중복 문자열로 pair 가 만들어질 수 있는 경우의 수는 nCr 이기 때문에, 조합 공식을 사용해 (n * (n -1)) / 2 로 구해준다. import Foundation ..

○ Hash Table | Easy LeetCode 2399. Check Distances Between Same Letters 소문자 알파벳의 아스키 값을 사용하는 것이 관건인 문제. 문제 이해하고 나면 어렵진 않다. 근데 문제 설명을 너무 어렵게 해놓음.. ㅡㅡ 내가 이해력이 딸리는건가? ㅎ 0-indexed string 은 무슨말이지? i번째 문자 저게 대체 뭔말인고 ? ㅋㅋㅋㅋ 그런거 다 무시하고 그냥 같은 문자 두개씩 주는데, 같은 문자 두개의 인덱스 차이를 구하면 되는 문제이다. 그 차이가 distance 배열의 알파벳 문자 인덱스와 일치하는지 확인해주면 됨. 1. 문자가 딕셔너리에 없으면 해당 문자의 인덱스를 값으로 추가해주고, 이미 있으면 현재 인덱스와 기존 인덱스의 차를 구해서 같은 문자..

△ 그리디 Silver1 백준 1931번 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주..

○ 그리디 Silver4 백준 11047번 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 그리디 유형의 대표 문제 동전 가능한 범위 내에서 무조건 가치가 큰 동전부터 더해나가면 되는 문제. 처음에 결과값..

그리디 Greedy 알고리즘이란? 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않고, 오직 현재 시점에서 가장 좋은 선택을 하는 알고리즘 ex) 대표적인 문제 : 백준 11047 동전 0 미래를 고려하지 않고 현재 내릴 수 있는 최선의 선택에만 집중하기 때문에 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지는 않는다. 항상 최적의 해를 찾을거라는 보장은 없기 때문에 근사 알고리즘이라고도 한다. 코테에서 그리디 알고리즘 사용 가능한 조건? 코딩테스트에서는 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야 한다. (보통 코테에서 그리디 문제는 이렇게 얻은 해가 최적의 해가 되는 상황으로 풀리도록 출제가 된다고 함) - 현재의 선택이 미래의 선택에 영향을 주지 않을 때 - 부분의 최적 ..

누적 합 Prefix Sum 배열에서 구간 합을 구해야 하는 문제에서 중첩 for 문을 사용해 값을 계속 더해주면 O(n^2) 시간 만큼 걸리지만 누적 합을 사용하면 계속 더해줄 필요 없이 마이너스 연산 만으로 해결 가능하다. O(1) 동적 계획법 문제들에서 DP로 연산 결과를 저장할 때에도 누적 합 방식이 많이 사용되는 듯 하다. * prefixsum 만들 때 index 0 말고 1부터 담아야 만들기 쉬움 psum 1, ~2, ~3, ~4 … suffix sum 은 뒤에서 부터 더하는 것. 알고리즘 대회 같은데서 가끔 나오긴 하는데 코테에서는 잘 안나옴. 구간쿼리 구할 때 배열의 요소가 정적일 경우 psum 동적일 경우 펜윅트리(?) 1차원 배열일 때 누적 합 구하는 건 간단하지만 2차원 배열은 좀,,..