2022.10.26 오전 9시 ~ 11시 오늘 알고리즘 중간고사 시험봤음! 시험보다가 마스크로 오른쪽 눈을 찔러서 시험 내내 너무 힘들었다.. 나왔던 문제는 아래와 같다. unimodal을 binary search로 maximum value의 인덱스 찾기 Knapsack을 이용하여 maximum weight 구하기 Longest Palindromic Subsequence 구하기 Maximum Subarray를 divide-conquer로 구하기 시간 되면 이와 비슷한 백준 문제 풀고, leetcode도 하나씩 해결할 예정 :(

백준 1012번: 유기농 배추 Graph theory / DFS / BFS https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 문제 설명 유기농 배추는 해충으로부터 보호하기 위해 배추흰지렁이가 총 몇 마리가 필요한지 구하는 문제이다. 전형적인 그래프 이론 문제로, 이를 해결하기 위해 DFS 혹은 BFS를 사용하여 해결한다. 배열이 주어지는 그래프 이론의 문제를 처음 접하면 문제를 읽고 이해하기가 난감한 경우가 발생한다. 특히 배추흰지렁이의 이동 루틴이 헷..

백준 9252번: LCS 2 Dynamic Programming https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 이 문제는 LCS를 구하는 과정이 백준 9521번과 완전히 동일하다. (Input, Output 형식도 같다!) 따라서, LCS를 구하는 방법에 대해서는 이전 글을 참고하면 된다. https://lucple.tistory.com/31 만약 문자열 X와 Y가 다음과 같다고..

백준 9251번: LCS Dynamic Programming https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 LCS는 두개의 문자열이 주어졌을때, 공통적으로 가장 긴 subsequence를 찾는 문제이다. 이때, substring과 달리 subsequence는 문자열이 연속적이지 않아도 된다. 만약, 문자열 X와 Y가 다음과 같다고 하자. X = Y = 이때 생성될 수 있는 subse..

작년에 머신러닝을 혼자 공부하기에 앞서 파이썬을 먼저 시작했다. 이론만 공부하면 재미가 없어서.. Problem Solving을 함께 시작했고, C99와 함께했던 실버 점수대에서 천천히 올렸다. 마침 겨울방학 때 자료구조를 공부했기 때문에 큐, 스택 등을 배워서 점수 올리는데 유용하게 써먹었다. 원래 여름방학에 끝내려고 했으나, 개인적인 사정으로 많이 풀지 못했다. 그래서 2학기 개강하고 나서 겨우 플래티넘을 달았다. 문제를 풀다 보니 문자열 처리 제외하고 파이썬보다 C++이 유리한 것 같다. 파이썬으로 풀었는데 채점 느리게 되면 엄청 초조해진다.. 70~80%까지 천천히 오르다가 시간초과 (같은 메커니즘인데 C++로 돌리면 통과) 이제 점수는 종강 이후 올리고, 문제 풀 때는 복습 위주로 진행하기로 :)