전체 글108 P11053. 가장 긴 증가하는 부분 수열 문제: https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 문제, 줄여서 LIS(Logest Increasing Subsequence)라고도 한다. 크게 완전탐색, DP, 이진탐색 방식으로 풀이할 수 있다. 유사한 문제가 여럿 있는데 이 문제는 DP(Dynamic Programming)방식으로도 풀리는 문제이다. 이번에는 위 3가지 방식으로 모두 풀이하겠다. 일단 LIS란 무엇일까? LIS는 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분 수열 중 가장 긴 수열을 말한다. 꼭 부분수열의 원소들이 배열에 이어져있지 않아도 된다. 완전 탐색 증가 부분수열은 다음 특징을 갖는다. 정수 i,j에 대해 i < j이면, S[i] < S[j]이다.(0 인접한.. 2023. 5. 4. [크래프톤 정글] 14일 - deque, Review 오늘 한 일☀️ - deque 공부 - 알고리즘 하 문제 위주 풀이 -> 완료 - 알고리즘 문제 오답 -> 진행 중 - 이진 탐색 공부(lower bound, upper bound, check 위주) -> 진행 중 deque deque는 앞, 뒤에서 데이터를 정리할 수 있는 양방향 자료형이다. +) 왜 양방향이 필요한가! 한쪽 방향으로만 출입구를 사용하면 맨 앞에 있는 원소를 제거할 때 n번의 이동이 필요하다. 평균적으로 n/2. 하지만 앞에서 뺀다면 1번만에 빠지기 때문에 상관없다. 자료구조 개념은 이전에 공부한 경험이 있으니, 각 언어에서 사용법을 알면 될 것 같다. 참고로 deque를 파이썬 공식 문서에서 찾아보면 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너 라고 나온다. 여기서.. 2023. 5. 4. [크래프톤 정글] 13일 - Stack 오늘 한 일🌴 - Stack 공부 - Algorithm 문제 풀이(2470, 11053, 1629, 10828, 10773, 9012, 17608, 2493) Stack 데이터를 임시 저장할 때 사용하는 자료구조이다. 데이터의 입력과 출력 순서는 후입선출(LIFO: Last In First Out) 방식이다. 고정 길이 Stack class FixedStack: """고정 길이 스택 클래스""" class Empty(Exception): """비어 있는 FixedStack에 팝 또는 피크할 때 내보낸다.""" pass class Full(Exception): """가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리""" pass def __init__(self, capacity): """스택 초.. 2023. 5. 3. [크래프톤 정글] 12일 - 탐색 오늘 한 일📝 - 이분 탐색 이론 공부 - Algorithm 문제 풀이(1920, 2805, 8983, 2630) 이분탐색 탐색은 데이터 집합에서 원하는 값을 가진 원소를 찾아내는 알고리즘을 말한다. 대표적인 탐색 방법은 다음과 같다. 배열 검색 연결 리스트 검색 이진 검색 트리 선형 검색(Linear search) 직선 모양(선형)으로 늘어선 배열에서 검색하여 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 순서대로 검색하는 알고리즘을 말한다. n의 복잡도를 갖는다. 검색 종료 조건 검색 실패: 검색할 값을 찾지 못하고 배열의 맨 끝을 지나는 경우(if i == len(a)) 검색 성공: 검색할 값과 같은 원소를 찾는 경우(if a[i] == key) 배열 원소의 개수가 n일 때, 조건을 판단하는 횟.. 2023. 5. 3. [크래프톤 정글] 11일 - 첫 시험 1주차 알고리즘 시험 더하기 사이클: https://www.acmicpc.net/problem/1110 1,2,3 더하기 - 재귀: https://www.acmicpc.net/problem/9095 부분수열의 합 - Brute force: https://www.acmicpc.net/problem/1182 더하기 사이클 문제 풀이 단계를 차분하게 정리하면 풀 수 있는 문제이다. 무조건 10의 자리로 만들어야한다고 생각해서 복잡하게 단계를 구상했는데 그렇지 않았다.(시험에서 뭔가 이상한 방향으로 가면 과감하게 나오는 것도 필요하다.😅) 이 문제에서 0을 앞에 넣어야한다는 생각에 str로 형변환하면서 풀이하려고 했는데 자릿수로 할 수 있는 문제였다. 이후에 두 방식대로 모두 풀이했다. 자릿수로 풀이한 경우 f.. 2023. 5. 3. Greedy 문제 풀이 - 잃어버린 괄호, 신입사원, 멀티탭 스케쥴링 Greedy 문제는 특별한 방식이 있기보다는 그리디 문제임을 확인하고, 문제를 최적화할 수 있는 우선 순위를 찾는 것이 필요하다고 생각한다. 최적화이기 때문에 모든 문제에 범용적으로 적용되는 것은 아니고, 문제마다 최적화할 수 있는 방안을 빨리 캐치하는 것이 필요하다. 이때 직관을 요구한다고 생각한다. 문제를 풀이하기 위한 아이디어를 간략하게 정리해보겠다. 1541. 잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 적당히 괄호를 쳐서 식의 최솟값을 구하는 것이다. 예를들어, 55-50+40.. 2023. 5. 3. P11047. 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 설명 K원을 만드는데 필요한 동전 개수의 최솟값을 구하기 위해 K원보다 작은 수 중 가장 인접한 수부터 하나씩 빼기 시작했다. 이진 탐색 본인은 인접한 수를 찾을 때, 이진 탐색을 사용했는데 값을 업데이트할 때마다 K원보다 작은 수 중 가장 인접한 수를 찾고 빼는 방식을 사용한다면, 시간 초과가 발생한다. 이를 해결하기 위한 방법은 .. 2023. 5. 3. DP(Dynamic Programming)이란? - 스티커, 동전, LCS, 행렬 곱셈 순서 동적 프로그래밍이란? 동적 프로그래밍은 큰 문제를 풀 때, 큰 문제의 일부인 작은 문제를 푸는 과정에서 발생하는 중복을 해결하는 방법이다. 이때 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 것을 최적 부분 구조(Optimal Substructure)를 가졌다고 표현한다. 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 다음의 정의를 갖는다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 즉, n은 n-1과 n-2 피보나치 수를 모두 갖고 있다. 만약 이 문제를 재귀호출로 푼다면 어떨까? fib(n) { if (n == 1 or n == 2) then return 1 else return (fib(n-1) + fib(n-2)) } 이렇게 푸는 방식은 매우 비효율.. 2023. 5. 3. WEEK01. 특별한 과제 벌써 정글에 온 지 5일이 되었다. 이곳에서는 목요일이 한 주의 끝이고, 금요일이 시작인데 어떻게 보면 이 글을 쓰는 시점인 오늘(어제)이 새로운 한 주의 시작이다. 오기 전까지 다른 사람들의 후기에서 이 과제를 여럿 봤는데 이제 내가 이 글을 작성할 시점이라는 게 신기하다. 1월부터 모집을 시작했으니 작성한 지 벌써 3개월이 지난 지원서를 다시 읽어보았다. 오랜만에 읽어보니 조금은 꾸며진 간절함이 어색하기도 하다. 과거의 나 내가 정글에 지원한 이유는 단 한 가지다. 스스로 당당할 만큼 개발 공부에 몰입하는 것!👩💻 사실 나는 1학년 때부터 개발 동아리에서 활동했지만, 개발보다 다른 것이 더 재미있었다. 서로 알고 있는 것을 적극적으로 공유하는 개발 문화는 좋아했지만, 개발은 진득하게 하지 않았다. .. 2023. 5. 3. 이전 1 ··· 9 10 11 12 다음
