본문 바로가기

분류 전체보기

 (432)
[알고리즘] 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence) 가장 긴 증가하는 부분 수열이란3 9 2 10 2 11 19라는 수열이 있을 때 부분 수열은 3 9 2, 10 2 19, 9 2 10 등 많은 수열이 있지만 그 중에서도 3 9 10 11 19를 뽑으면 오름차순을 유지하면서 가장 긴 부분 수열을 뽑을 수 있다. LIS알고리즘이란 이 수열의 길이를 빠르게 찾아내는 방법을 말한다.그렇다면 이 수열을 어떻게 구할 수 있을까?1. 브루트포스 완전탐색모든 수열을 다 구해보면 된다. 그렇다면 1 2 3 4 라는 수열이 있다면 각 자리의 수를 사용하거나 혹은 사용하지 않는 경우의 수를 샐 수 있으므로 시간 복잡도는 O(2^N) 으로 너무 긴 시간이 걸린다.2. 동적계획법 (Dynamic Programming)각 자릿수가 자신을 포함했을 때의 최장 길이 부분 수열의 길..
[백준 1082번] 방 번호 (C++) https://www.acmicpc.net/problem/1082 방 번호는 무한으로 살 수 있으므로 N = 10이고 최대 값은 50이다. 이 때 모든 경우의 수를 다 해보는 것은 약 10^10으로 10억이상으로 엄청난시간이 걸린다. 중요한 추론은 숫자를 가장 길게 만들어야한다는 것이다. 그리고 91111 보다는 92000이 크고 100000이 더 크다. 즉 가장 비용이 적은 것들을 사용해서 먼저 가장 긴 방번호를 만들어둔 후 각 자리수마다 하나씩 비교하며 더 큰 값을 사용할 수 있을지 검사한다. 이 방법은 N^3 의 시간밖에 소요되지 않는다.  그리고 각 번호의 개수를 배열에 저장해두고 큰 값부터 다음 값이 가능한지 확인한다. 왜 큰 값부터 해야하냐면 만약 작은것부터 시행했을 때는 다음과 같은 문제가 ..
[백준 1033번] 칵테일 (C++) https://www.acmicpc.net/problem/1033 1:3, 4:7 등 여러 비율이 주어지고 결국 이어지는 길목을 똑같이 이어줘야하는 문제이다.   만약 1번 : 2번 = 4 : 72번 : 3번 = 3 : 10 이라하면 1번 : 2번 : 3번이 성립하는데 비율이 다르기 때문에 이것을 통일해줘야한다.2번이 처리해야하는 비율은 3과 7이다. 그렇다면 21로 비율을 맞출 수 있다. 21로 맞추면 1번에는 x3을 해줘야하고 10에는 x7을 해줘야한다. 그렇다면  12 : 21 : 70 이고 이것이 정답이다. 만약  2번:4번 = 5 : 3 이라면 2번은 3,5,7을 갖고있고 이것을 통일해야한다. 문제는 가장 적은 비율을 요구한다. 그러므로 최소공배수를 구해야한다는 것을 알 수 있다.  또한 문제가..
코드포스 DIV 3 첫 참가 후기 최근 무언가 도전적이고 성취감을 얻고 싶다는 생각에 코드포스가 떠올라 무지성으로 홈페이지에 들어가봤다. 코드포스는 세계에서 가장 큰 경쟁적 프로그래밍 사이트로 백준이 슈팅, 드리블 연습장이라면 코드포스는 진짜 시합이라고 볼 수 있겠다. (solved 랭크는 사실 의미가 없다. 성실함의 지표는 될 수 있어도 실력의 지표로는 사용하기 어렵다. 문제집 1000권을 풀었다고 공부를 잘한다고 할 수 없고 점수가 중요한 것처럼) 난 플래5로 전체적인 백준 인구수로 볼 때 중상위권으로 문제는 많이 풀어봤다고 생각이 들어 마침 DIV3 컨테스트가 열리길래 바로 신청하고 두근거리는 마음으로 (야근하고 피곤한 마음으로) 참가했다. 결과는... 7문제 중 3솔로 1만등(...)을 해버렸다. 평소 내 단점이 일단되면 ..
[Spring Batch] 5.0 버전에서 달라진 점과 기본 예제 진행하던 프로젝트에서 공용충전기의 대한 정보 업데이트를 위해 주기적으로 공용충전기의 대한 정보를 다시 받아와야하는 작업을 진행하기 위해 스프링배치를 공부하게 되었다.Spring Batch스프링 배치는 로깅, 추적, 트랜젝션 관리, 작업처리 통계, 반복 작업 자동화 등 많은 기능을 제공하는 스프링 기능을 제공한다.스프링배치는 Job과 Step을 관리하는 기능을 제공하며 실제로 실행하는 것은 스케줄러이다.Srping Batch 5.0 에서 달라진 것들Spring Batch 5.0 Migration Guide많은 초보 개발자들이 ChatGPT와 블로그 예제를 보면서 코드를 작성할 것이다.현재 많은 스프링배치 포스팅들은 이전 버전을 사용하고 있어서 지금은 사용하지 못하는 것이 많다.@EnableBatchProc..
[백준 2138번] 전구와 스위치(C++) https://www.acmicpc.net/problem/2138 여러가지 상황을 시도하고 규칙성을 찾아내는 것이 관건인 문제이다. 관건은 서로 영향을 줄 수 있는 스위치들이 엮여있기 때문에 모든 경우의 수를 해보는 것이 가장 간단하지만 시간초과가 날 것이다. 먼저 서로 영향을 끼치는 관계를 그림으로 나타내보자  무엇을 의미하는지 잘 모르겠다..그러나 일반적으로 어떤 방식을 사용하던 스위치는 결국 켜거나 놔두게 될 것이다. 한번 1번 스위치를 켰다고 가정하자. 그렇다면 1,2번 전구가 켜졌을 것이다.   그리고 이제 2번 스위치를 켤지 말지 결정해보자. 어라? 여기서 1번을 향하고 있는 스위치가 단 한개이다..!즉 1번은 이제 내 마음대로 조절할수가 있게 되었다.  만약 목표로하는 타겟의 1번이 켜져있다..
[백준 2250번] 트리의 높이와 너비 (C++) https://www.acmicpc.net/problem/2250   문제는 이해했을 것이고 어떻게 풀어야할까  먼저 이 문제는 root가 정해져있지 않다. 부모가 없으면 그게 루트이고 들어오는 순서들도 루트부터 레벨순으로 들어오지 않음을 유의하자. 이 문제는 한번 N번 노드가 자리를 잡게 한 후 계속 갱신시켜가면 O(2^N) 이상의 시간이 걸린다. 예를 들어 처음에 root를 1번에 자리시킨다고 하자. 그리고 2번, 3번이 들어올 때 마다 자리를 옮긴다면 마지막 18, 19가 들어올 때도 최적의 자리를 위해 모든 노드를 갱신해야할 뿐더러 그것이 최적의 자리인지도 확실하지 않다. 문제의 조건을 보면 각 노드의 컬럼 사이는 비어있지 않다. 그러므로 문제를 최적의 자리를 찾는다에서 반드시 비워둬야할 자리가 ..
[백준 15824번] 얘 봄에는 캡사이신이 맛있단다 https://www.acmicpc.net/problem/15824 처음에는 DP로 생각했으나 O(N^2) 에서 시간을 더 줄이는 것이 불가능했다. 이 문제는 모든 조합을 구하는 것은 O(2^N - 1) 로 불가능하다. 가장 중요한 추론은 어떠한 조합이든 결국 최댓값과 최솟값만 알면 스코빌지수를 알 수 있는 것이다. 1, 2, 3, 4 가 있을 때1 ,2, 41, 3, 41, 4 스코빌지수는 모두 3이다.  두번째 떠올려야할 아이디어는 위처럼 꼭 모든 조합을 해봐야알 필요는 없다. 사실 이것을 생각해내기가 가장 어려운 것 같다. 당연히 조합을 먼저 구하려고 하는 것이 일반적이기 때문이다. 1, 2, 3이 있다고 하자.3은 최댓값으로 (1, 3), (2, 3), (1, 2, 3) 으로 총 3번의 최댓값이 ..

티스토리툴바