분류 전체보기(222)
-
P#19 Minimum Sum Problem
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding DP[state] = minimum sum of using columns of state index : 0 1 2 3 4 5 states : 1 1 0 1 1 0 this state implies that column 0,1,3,4 are used Use dfs to backtrack all possibile situations. def solve(row:int=0, state:int=0, weight:int=0) ->int: global dp,n,k if state in dp and weight >=..
2020.08.23 -
Problem #18 Sliding Window
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#18: Sliding Window Problem Description Idea This problem is finding a maximum vale of all rnage of a fixed length. This problem can be ..
2020.08.23 -
유용한 PS Blogs & Articles
전설이다 https://koosaga.com/242?category=554431 동적 계획법을 최적화하는 9가지 방법 (1/4) 동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때 koosaga.com 코포 게시글이 많다. https://gumgood.tistory.com/169 Segment Tree (+ Lazy Propagation) 코드 최적화 원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속..
2020.08.22 -
고알 연습#3
8월 21일 2시간, 5문제 A,C,E -> 그리디 B,D -> 분할정복 실력도 문제고 끈기도 문제다. 매일 한다고 생각하니 진지함이 없어졌다. 전화 오면 받고, 메일 알림 오면 답장하고, 카톡 오면 카톡한다. B는 더 고민했으면 맞출 수 있는 문제였다. A는 #2의 그 문젠데 고민해도 모르겠더라 이로써 업솔빙해야 하는 문제는 3개가 되었다. 금광, 직선 찾기, 멀티탭 스케줄링. C -> 알파벳이 사용되는 수를 합치고, 수가 큰 순서대로 정렬 E -> positive, nonpositive 나눠서 생각. 단, 1은 곱하지 말고 더해줘야 함.
2020.08.21 -
P#17 Longest Path of a file system
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#16 Longest Path of a file system Problem Description Idea DP. 1. split the filesystem with '\n'. 2. count of '\t' implies the level 3. ..
2020.08.21 -
P#16 The last N elements
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#16: The last N elements Problem Description Idea My first approach is to use a List. record orders to a list. inserting elements to the..
2020.08.21 -
고알 연습#2
8월 20일 2시간 5문제 문제를 풀 때 랭크를 가렸고, 난이도/전략과 무관하도록 셔플했다. 총 점수 : 2솔 내 처음 분석은 이랬다. A: 비트마스킹 DP, B: TreeDP (분할정복 느낌), C:그리디, D: 랜덤 알고리즘, E:그리디/완탐 A,E,B에 대하여 대략적인 풀이를 생각하고 E,A,C,B 순으로 구현에 들어갔다. 개선할 부분 : E->그리디적으로 풀 때는 '확실해야 한다'. 이런 문제를 그리디적으로 풀 때 특징이 if문으로 코드가 난잡해진다는 것이다. 그렇기에 더 꼼꼼해야 한다. KOI, 학교 수행평가는 상관 없다. 그러나 코포/앳코더 같이 페널티 큰 대회들은 이런게 치명적이므로 신경 쓰자. 전체적으로 느렸다. 여유와 쳐짐을 구분하자. A-> 좋았다. dp 테이블 정의도 깔끔했고 구현도 ..
2020.08.20 -
과반수 원소 알고리즘
Majority Element / Majority Vote Algorithm 주어진 리스트에서 과반수를 차지하는 원소의 존재성 판정과, 존재 시 과반수 원소를 구하는 알고리즘. A[] = { 1, 3, 1, 1, 2} 리스트 A에서 과반수 원소는 1이다. 정렬하면 슥삭 풀리는 문제이지만 O(N) 시간복잡도에 가능한 알고리즘이 존재한다. O(N) Solution 내가 소개할 것 : Pair 매칭 알고리즘. *기존 길이 $n$ 리스트 A로부터 길이 $[n/2]$ 리스트 B를 만든다. N이 짝수일 때 : 앞에서부터 차례대로 2개씩 묶는다. 각각의 pair (x,y)에 대해 x==y면 하나만 남기고, x!=y면 둘 다 제거한다. A[]={1,3,1,1,2,1} 을 예시로 들자면 (1,3) => (), (1,1)..
2020.08.20 -
P#15 Random Element Selection
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem #15 : Random Element Selection The problem is that there are too many elements. So we have to pick an element without storing them. If ..
2020.08.19 -
고급 알고리즘 연습#1
0819 수요일 2시간 3분, 5문제 학교 시험 범위에 맞추어 (완탐,그리디,분할정복,DP,기댓값) Set을 잡았다. 앞으로도 고알 연습은 이렇게 돌릴 것이고, 특정 알고리즘이 약하다는 판단이 나오면 알고리즘 종류를 제한할 수 있다. 연습을 돌리기 전 Tourist의 글을 읽었다. - Tourist는 현 코드잼 챔피언으로 최근 수 년 간 자리를 유지했다. 글은 경진 프로그래밍 대회에서의 그의 전략을 담았다. 내가 깨닫고, 이번 Set에서 실천한 것. : 모든 문제를 먼저 푼다. 한 문제를 푼다는 것은 다음 단계들로 이루어진다. Read - Solve - Implement - (Debug) 여기서 Tourist의 전략은 먼저 모든 문제들을 읽고, 핵심 아이디어를 생각해 놓은 다음 Implement로 들어가..
2020.08.19 -
P#14 Calculate Pi by Monte Carlo Method
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#14 Calculate Phi by Monte Carlo Method Problem Description Idea Implementation Methods needed to learn. -> random function Result Simpl..
2020.08.18 -
P#13 K-distinct Substring
All problems are from https://www.dailycodingproblem.com/ My Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem# 13: K-distinct Substring Problem Description Idea Time Complexity : O(n) Let's Use Two Pointers. Starting from s=0, e=0, we will seque..
2020.08.17 -
P#12 : Staircase
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#12: Climbing Staircase Problem Description Idea We are cimbing a staircase. Well Known DP Problem. Find out tips with watching the impleme..
2020.08.16 -
P#11 String Auto Complete System (문자열 자동완성기능 구현)
All problems are from https://www.dailycodingproblem.com/ 전문가의 말을 믿기보다는 내가 전문가가 될 것. - 존 리 Be an Expert whether than believing an Expert. - John Lee Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#11 : String Auto Complete System (문자열 자동완성 시스템 ..
2020.08.16 -
Problem#10 : Time Lapse
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#10 : Time Lapse Problem Description Idea use while loops to delay it. Implementation
2020.08.16 -
Problem#9 : Non-Adjacent Sum
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem #9: Non-Adjacent Sum Problem Description Idea Simple DP Problem. We will set two different DP Table. DP1 (i) : we seek 1st ~ ith elements...
2020.08.16 -
Problem#8 :Unival Subtrees
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#8 :Unival Subtrees Problem Description Solution Time Complexity : O(N) Space Complexity : O(N) SVG File! You can click the image and Magni..
2020.08.16 -
Problem#7 : Decoding Possibility
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem#7 : Decoding Possibility Problem Description Idea Dynamic Programming. DP(i) : number of decodings possible from str[0:i] DP(i) = DP(i-1) ..
2020.08.15 -
Problem #6 XOR Linked List
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Daily Coding Problem #6 XOR Linked List An interesting Problem Let's Implement this with C++ 1. Note XOR Operations X⊕X = 0 X⊕0 = X X⊕Y = Y⊕X (X⊕Y)⊕Z = X⊕(Y⊕Z) What we have to decoy is the following equation: A⊕(A⊕C) = (A⊕A)⊕C = 0⊕C = C Now we can Traverse the Linked List if we save th..
2020.08.15 -
Problem #5 Implementing Pair in Python
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily Coding Problem #5 Implementing Pair in Python Basic Implementation. One thing Interesting is the fact that A function can return another Function and get..
2020.08.15 -
Problem #4 : First missing positive integer
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com Daily coding Problem #4 After Solving this Problem, I searched this problem in google. Saw various solutions, found out my solution is unique. Many solutions u..
2020.08.15 -
#3 Parse & ReverseParse a Binary Tree
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com #3 An opportunity to practice Python! Solution Generally, inorder Traversal can't recover the origianl Tree since there are more than one possible trees. Howev..
2020.08.15 -
Convex Hull과 Sorting의 관계
정렬 문제를 Convex Hull 문제로 환원하는 방법을 소개합니다. Convex Hull 문제를 정렬 문제로 환원할 수 있다는 것은 널리 알려져 있는 사실이다. Graham Scan알고리즘은 점들을 각도 순으로 정렬한 뒤 한 번의 스캔을 통해 Convex Hull을 구하는 알고리즘이기 때문이다. 곧, 다항 시간 내에 Convex Hull 문제를 점들을 정렬하는 문제로 환원할 수 있다. 여기서는 정렬 후에 이루어지는 스캔 (O(N))이 변환 시간이 된다. 다음과 같이 나타낸다. 여기까지는 Convex Hull과 다항식 시간 변환의 개념을 안다면 누구나 알 수 있는 사실이다. 한 발 더 나아가보자. 정렬 문제를 Convex Hull을 구하는 문제로 변환할 수 있을까? 즉, Convex Hull을 구하는 알..
2020.08.15 -
백준 2437 저울
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 문제 만들 수 없는 무게의 최솟값은 무엇인가? 초기 접근 : DP DP[i][j] : 1~i까지의 추를 이용해 무게 j를 만들 수 있는가? 최후에 DP[n][x]를 관찰해 x가 false 인 첫번째 x를 출력하려고 했다. 막힌 것은 추의 무게의 범위가 1~1000000, 추의 개수의 범위가 1~1000이므로 DP[] 는 1e9개의 비트를 저장해야 한다. 메모리 초과 + DT를 채우는 것 자체가 만만치 않다..
2020.08.14 -
#1 2SUM #2 No Division Multiplying
All problems are from https://www.dailycodingproblem.com/ Solution Codes : https://github.com/Kusin/DailyCoding Kusin/DailyCoding DailyCodingProblem. Contribute to Kusin/DailyCoding development by creating an account on GitHub. github.com #1 Approach 1 : Sort and Bianry search O(N log N) sort arr for k in arr -> find (Goal-k) in arr by binary sort Approach 2 : Use Hash, O(N) for k in arr -> hash..
2020.08.07 -
긴 대장정이었다.
쉬운 DP 문제인줄 알고 시작했던 것이 실은 수학과 최적화 문제였다. 이 문제를 풀면서 강한 멘탈과 '아이디어' 구체화의 중요성을 다시 한 번 깨달았다. 덕분에 깊게 몰입해서 빡센 구현을 할 수 있었다. 문제를 만드시고, 감을 잡지 못할 때 아이디어를 주신 최성준 선배님께 감사한다. https://code.sasa.hs.kr/problem.php?id=1525 SASA OJ 첫 번째 줄에 정수 M, N, K, p의 값이 입력으로 주어진다. 이때, M은 1 이상 1000000 이하의 정수이고, N은 1 이상 1000 이하의 정수이다. K는 0 이상 10 이하의 정수이고, p는 10000000 이상 1000000009 이하의 소 code.sasa.hs.kr Code SASA 1525: [어려움] 이동하는 경..
2020.07.24 -
Counting Sort할 때 누적합 배열 사용 이유
및 많은 교재에서 계수 정렬 - Counting Sort를 cnt 누적합 배열을 이용해 구현한다. 이를 배울 때 나는 이것이 무용하다고 생각했다. 누적합 없이도 그 개수만큼 세서 큐에 넣어주면 되기 때문이다. 그러나 오늘 pair형 data를 counting sort 하는 것에 대해 공부하고 나서 누적합 배열의 유용함을 알게 되었다. 그 유용함은 바로 index를 cnt 배열을 통해 정해준다는 것이다. 그러므로 그 데이터 자체가 아니더라도 부가적인 정보를 stablesort할 수 있다는 장점이 있다. 부가적인 정보의 예로는 입력 순서 등이 있다. 자세한 구현은 링크에 있으니 꼭 정독하고 counting sort를 마스터하자. https://blog.naver.com/jqkt15/222031601969 [..
2020.07.22 -
[백준] 퇴사
https://www.acmicpc.net/problem/14501 #include #define IOS ios::sync_with_stdio(false);cin.tie(0); typedef long long ll; const int INF = 1e9; const ll LINF = 1e17; int n,t[16],p[16]; int DT[16]; int main(){ IOS; cin>>n; for(int i=1;i>t[i]>>p[i]; for(int i=n;i>=1;i--){ if(i+t[i]-1
2020.07.20 -
KOI 2019 2차 대회 2번 '괄호' 풀이
※복습 : 문제 : 괄호 문제 링크 사용 알고리즘 : 다이나믹 프로그래밍 풀이: 2개의 괄호문자열을 대소 비교하는 방법에 주목하자. 길이가 짧으면 작다. 길이가 같다면 (,),{,},[,] 순으로 작으므로 10진법 수 비교하듯이 하면 된다. 즉, DP 테이블 자체를 문자열로 할 수 있다는 뜻이다. dt[N] : val( str ) = N 인 문자열 str 중 dmap(str) 값이 가장 작은 str 이때 dmap은 단순히 문자열의 괄호 문자를 숫자로 치환한 것을 의미한다. 아래 map을 참고하자. 이제 문제의 규칙을 이용하여 적당히 DP를 돌려주면 된다. 테스트케이스가 여러개 들어올 수 있으므로 미리 dt를 채우면 된다. 이 문제의 경우 반복문이 간단하다. 코드 더보기 1 2 3 4 5 6 7 8 9 1..
2020.07.11 -
각종 알고리즘
Disjoint Set #include #define SIZE 110 class Disjoint_Set{ private: int root[SIZE],rank[SIZE],cnt[SIZE]; public: void Make_Set(int x){ root[x]=x; rank[x]=0; cnt[x]=1; } int Find_Set(int x){ if(x==root[x]) return x; return Find_Set(root[x]); } //Union by Rank void Union(int a,int b){ a=Find_Set(a); b=Find_Set(b); if(a==b) return; int t=cnt[a]+cnt[b]; if(rank[a]>rank[b]){ root[b]=a,cnt[a]+=cnt[b];..
2020.07.08