SJ_Koding

예전에 KT AIVLE SCHOOL수료식날 팀원들끼리 자격증 이야기를 하다가 "지금 신청기간이에요!" 라는 말에 정보처리기사, AdSP 자격증 신청을 했었고, 잊고있다가.. 3일전에 알게되었다. 정보처리기사(필기)는 3일 공부로 합격하였고(추후 포스팅 예정) AdSP는 2일 벼락치기로 합격했다. 여기서 말하는 2일은 독서실에 오전 10시 부터 밤 11시까지. 하루 종일 투자한 2일이다. 사용 교재2024 이지패스 ADsP 데이터분석 준전문가 이 교재를 사용한 이유는 이론 내용도 내용이지만, 무엇보다 기출문제 제공이 컸다. ADsP도 기출은행식이라는 말을 들었었기 때문이다. (그렇다고 너무 기출은행은 아니었었다. 2024년 첫 시험이었던 40회는 주관식이 사라지고 신유형이 많이 나온 느낌이었다.)일단 무작..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐를 사용하는 대표적인 문제인 것 같다. 문제 요약: 여러 장으로 구성된 덱들을 하나로 합칠 때, 최소 비교 횟수로 합칠 수 있는 방법 ex) 10장, 20장, 40장으로 구성된 덱에서 10장짜리와 20장짜리를 합치는데 30번의 비교가 들고 합쳐진 30장과 40장을 합칠때는 70번의 비교가 소요되어 총 100번의 비교가 수행. 만약 10장과 40장을 먼저 합치고 20장과 합친다면 (10+40) + (50 + 20) == 120이 되어 최소..

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 유명한 보석 문제이다. 스터디에서 진행했던 문제이고 그리디 알고리즘을 공부할 수 있는 좋은 문제인 것 같아, 정리차원에서 포스팅한다. 문제 요약: 최대 용량이 다양한 가방들이 주어지고 가방에는 하나의 보석만 담을 수 있다. 보석은 무게와 값어치가 각각 주어지고, 최대 30만개를 훔칠 수 있다. 보석의 무게가 가방의 최대 용량보다 크면 가방에 담을 수 없다. 최대로 훔칠 수 있는 보석의 값어치 총합을 구..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Longest Common Subsequence, 최장 공통 부분 수열 문제는 두 수열이 주어지면, 공통되는 부분수열 중 최고길이를 가지는 수열을 찾는 문제이다. 해당 문제는 골드 V이지만, 한 번이라도 경험해보지 않으면 생각해내기 정말 어려운 문제인 것 같다. 최장 증가하는 부분수열을 구했던 문제와 동일한 난이도였지만, 어떻게 풀어내야할 지 감 조차도 안왔다. (내가 멍청한거 일수도..) 결국엔 이번 포스팅은 내가 ..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 가장 긴 증가하는 부분수열(11053)문제와 이어집니다. 11053문제는 최대 길이를 출력하는거라면 14002문제는 최대 길이와 함께 그 수열을 출력하는 문제입니다. 해당 문제를 해결하기 위해 아래의 포스팅은 꼭 참고해야합니다. 방법은 이미 아시는 분이라면 넘어가도 좋습니다. 2024.02.27 - [Algorithm/DP(Dynamic Programming)] - 백준 ..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP를 입문하는 문제로 피보나치수열과 부분 수열을 구하는 문제가 대표적인 것 같다. 멘토링을 하면서 DP에 조금 더 관심이 생겼는데, 정말 어려운 개념이어서 이해하는데 시간이 걸렸다. 이해를 정립시키기 위해 해당 문제를 블로그에 다시 정리하겠다. 문제요약 문제는 간단하다. 수열이 주어지면 가장 긴 부분 수열을 찾는 문제. (수열 크기 최대 1000) ex1) [1, 100, 2, 300..

소수와 결합된 투포인터문제이다. 연속된 수를 찾으므로 두 개의 포인터는 0에서 시작한다고 일반적으로 판단해도 될 것같다. 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 요약: N이 주어졌을 때, 연속된 소수로 이루어진 합의 경우의 수를 찾아라! 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 20: 7 + 13 은 안됨! 연속된 소수가 아니므로. = 0가지 솔루션: 1. 에라토스테네스의 체로 소수 배열을 만든다. 범위는 최대 400만으로 주어졌다. 일반적인 소수판별(O(N^2))로 구할 수 없다. 2. 두 개의 포인터(..

기업 코딩테스트의 마지막 문제에서 투포인터 문제가 나왔었는데, 종료조건을 건드리다가 시간을 넘겨버렸다. 투포인터의 개념을 이론적으로 알고는 있었지만 실제 투포인터 문제를 풀어본 적은 거의 없다. 이 참에 공부해보자. 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제요약 주어진 리스트에서 두 원소의 합이 0과 가장 가까운 원소를 찾는것이다. 원소의 범위는 -10억 ~ 10억 이며, 원소의 개수는 최대 10만개 이므로 모든 경우를 탐색하는 O(N^2)으로 풀어낼 수 없다. 이..