코드업 KOI 문제 (DP) 문제집 올솔브

고등학교 때 처음 보고, 굉장히 오랫동안 풀고 싶어했던 문제들입니다. https://www.acmicpc.net/problem/2625 2625번: DNA유사도 모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로만 표현된다. 한 DNA 서열에서 두 문자의 거리 는 두 문자 사이에 있는 문자들의 개수이다. DNA 서열의 부분서열은 DNA 서열에서 몇 개의 문자를 제 거 www.acmicpc.net 이 가혹한 문자열 문제에 가로막혀 오랫동안 생각하지 않고 있다가, 북마크를 보고 다시 떠올려 오늘 해결했습니다. 더보기 기본적으로 최장길이는 O(N^2K^2) dp를 통하여 LCS/편집거리와 비슷하게, 쉽게 구할 수 있다. 한 단계 발전시켜 한 방향으로 덱이나 누적합 등을 사용하면 O(N^2K)에 구할..

2022.12.05

DCP 124

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# 124: 격자판 DP Problem Description Idea DP(i,j) : (1,1)부터 (i,j)까지 오는 동안 먹을 수 있는 동전 가치 합의 최댓값 DP(i,j) = max(DP(i,j-1),DP(i-1,j)) + arr[i][..

2020.12.07

KOI 고등부 1,2번 문제집 완료

www.acmicpc.net/workbook/view/4576 다각형의 확장까지 풀면서 결국 문제집을 완료했다. 시험기간에는 역시 코딩이 잘된다.

2020.10.24

Problem #79

벌써 79번 문제다 주어진 수열의 한 원소를 수정해 단조 증가로 만들 수 있느냐가 문제 non decreasing 수열의 정의를 살펴보면 쉽다 정의 : 모든 n에 대해 a(n) a(x+1) or a(x-1) > a(x) and a(x) < a(x+1) a(1)

2020.10.22

[도전 28일차] 기하 구현 끝판왕, 달팽이

백준 6990 달팽이 2020/04/09 - [Problem Solving/KOI 고등부] - (※재도전 시급) [도전 11일차] 백준 6990 달팽이 4월 9일에 포기했던 문제를 6개월만에 다시 잡다. 6개월 전 시청한 IOI Korea님의 풀이와 나의 오랜 thinking이 합쳐져 구현에 온전히 집중할 수 있었다. 문제 : 백준 6990 달팽이 문제 링크 문제 요약 : L * L 크기의 좌표 평면에 N 마리 달팽이가 있다. 달팽이들의 시작 위치는 정해져 있고 일직선으로 움직인다. 달팽이들은 1초에 1의 속도로 움직인다. 달팽이는 다른 달팽이가 움직인 흔적이나 벽에 부딪혔을 때 멈춘다. 달팽이들의 시작 위치와 초기 방향이 주어졌을 때 모든 달팽이들이 멈추는데까지 걸리는 시간은 얼마일까? 모든 달팽이들은..

2020.10.10

정보과학올림피아드 1차 문제 형식 제안

2019년부터 달라진 점은 C++ 코드 해석 평가를 그만두고 비버챌린지 형식 문제들이 출제된다는 점이다. 이산 수학, 조합 문제들은 계속 만나볼 수 있다. 기출문제들을 풀면서 생각한 것인데 정보올림피아드 문제들도 프로젝트 오일러 http://projecteuler.net/와 같이 컴퓨터를 써서 풀 수 있는 문제들로 구성하면 좋겠다. 이산 수학은 기초적인 수학 능력이 맞다. 이산 수학 문제는 오로지 수학 능력을 체크하는 반면 오일러 프로젝트의 문제들은 정보과학적 사고 능력과 수학 능력을 모두 가지고 있어야 해결하기 때문에 정보과학 올림피아드에 더 적합하다고 생각한다. 결론 -> 기존 수학 문제 난이도 up + 문제 풀 때 (구름)IDE 사용 가능하도록 변경 복잡한 컴퓨터를 이용하여 효과적으로 가능하다는 것..

2020.09.09

Pause / 일시 중지

Since I want to master Calculus, I decided to pause solving Daily Coding Problems for a while. Postings will be continued from Problem #20 at 2020.9.26. Cya, readers and DCP. Daily Coding Problem 푸는 것을 잠깐 멈춥니다. 2020.9.26, Problem #20부터 다시 시작합니다. UPD) 2020.10.26, Problem #20부터 다시 시작합니다.

2020.08.26

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

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

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

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

#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

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

한국정보올림피아드(KOI) 공부 시작하기

서론 안녕하세요! 비키라입니다. 저는 2020/03/29부터 KOI 전국본선 고등부 1,2번 문제들을 본격적으로 풀었습니다. (도전 내용) 도전을 시작할 때 채점이 가능한 1,2번 문제들을 전부 풀자는 목표를 세웠고, 먼저 백준 온라인저지에 있는 모든 KOI 고등 1,2번 문제를 문제집에 정리하였습니다. 2019년 최신 문제부터 1997년 문제까지 차례대로 나열되어 있으며 편한 순서대로 풀면 됩니다. 오래된 문제들은 대부분 인터넷에서 풀이를 찾을 수 없었는데 이 경우 오랜 시간 풀이를 찾아 헤멨고, 그러다가 KOI 공식 풀이를 찾아, 이를 참고하여 공부했습니다. 한국정보올림피아드 전국본선 문제들을 공부하시는 분들을 위해 고등부 1,2번 문제의 풀이를 정리합니다. 구성은 아래와 같습니다. 1. 날짜 2. ..

2020.05.01

[도전 30일차] 다각형의 확장 (도전중)

보호되어 있는 글입니다.

2020.04.30

[도전 29일차] 헬기 착륙장 - KOI 고등부 풀이

※복습 : 문제 : 백준 2626 헬기 착륙장 문제 링크 사용 알고리즘 : 기하 - 최소 외접원 풀이 : 이 문제는 '주어진 모든 점을 포함하는 최소 외접원 찾기'로 요약 가능하다. (ho94949님의 글, 최소 외접원 찾기에 정말 자세한 내용이 있다.) 외접원의 중심을 찾는 과정은 거리 함수 $$z={\sqrt (x^2+y^2)}$$가 볼록함수라는 것으로부터 출발한다. 위 그래프의 꼭짓점을 우리가 원하는 외접원의 중심 (Ax,Ay) 라고 하자. 임의의 점을 하나 잡고, (Ax,Ay)에 가깝게 가는 과정을 반복할 수 있다면 어떨까? 최종적으로는 Ax,Ay에 도착할 수 있을 것이다. 그렇다면 (Ax,Ay)에 가까운지는 어떻게 판단할까? (Ax,Ay)는 가장 거리가 먼 점과의 거리가 최소인 점이므로, 현재 ..

2020.04.29

[도전 27일차] 검은점과 하얀점 연결 풀이

※복습 : 문제 : 백준 2647 검은점과 하얀점 연결 문제 링크 사용 알고리즘 : Dynamic Programming 풀이: A[i] : i번째 점의 색깔 ( 0이면 하양, 1이면 검정 ) 1. X[i][j] => i번점부터 j번점까지 검은 점의 개수 X[i][j]*2 == (j-i+1) 이면 i,j 가 연결이 가능하다. X[i][j] = X[i][j-1] + A[j]로 구하기 그 다음 X[i][j]의 정의를 바꾸기 2. X[i][j] = i번점부터 j번까지 살펴보았을 때 i번점과 j번점의 개수가 같은가? X[i][j] = ( X[i][j]*2 == (j-i+1) ) 로 갱신. DP[i][j] : i번점부터 j번점까지 보았을 때 최소 연결 거리 H[i][j] : i번점부터 j번점까지 보았을 때 최소 연..

2020.04.27

[도전 26일차] 초고속철도 - KOI 고등부 풀이

※복습 : 문제 : 백준 2543 초고속철도 문제 링크 사용 알고리즘 : Dynamic Programming 참고 : KOI 공식 풀이 풀이: 기본적으로 DT 자체는 떠올리기 쉽다. DT[i] : 1~i번째 철도까지 보았을 때의 경우의 수 문제는 이 번째라는 것을 어떻게 정할 것인가이다. 이는 철도를 정렬하는 것으로 해결할 수 있다. 철도의 앞 구간을 a, 뒤 구간을 b라 하자. a를 기준으로 정렬한다면 살짝 불편해지는데 a가 작고 , b가 큰 구간이 존재해서 처음부터 끝까지 DT를 채우는데 영향을 줄 수 있기 때문이다. b를 기준으로 정렬하면 이 점이 해결된다. 지금 보고 있는 철도 앞에 있는 철도가 나를 포함하지 못하기 때문에 편하다. 이제 정렬이 끝났으니 DT 간 관계식을 생각해야 한다. i번째 철..

2020.04.26