백준 : 11053 가장 긴 증가하는 부분수열

문제 이해수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)을 구하는 프로그램을 작성하라. 여기서 가장 긴 증가하는 부분 수열이란, 어떤 수열에서 원래 순서를 유지하면서 앞보다 뒤가 점점 커지는 숫자들이며 그 중 가장 길게 고를 수 있는 경우를 출력하면 된다.문제 분석처음 이 문제를 접했을 때, 가장 먼저 고민한 것은 start와 end 값을 어떻게 정해야 할지였다. 이진 탐색의 구조를 떠올리긴 했지만, target 값은 매 반복마다 바뀌게 되고, 우리가 구하고자 하는 건 "원래 위치"가 아니라 LIS를 만들기 위한 위치이기 때문에 mid 값이 의미가 있는 건지 확신이 서지 않았다. 원래의 위치를 정확히 추적하려면 리스트를 정렬할 수 없고, 그렇다면 이진 탐색을 어떻게 시작할지 막막했다.초기 ..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 23.

[크래프톤정글] 정글에서의 생활

정글에 입소하기 전에 가장 걱정했던 부분 중 하나는 기숙사의 환경과 밥을 어떻게 해야하는지였다. 추후 정글을 지원하려는 분들을 위한 기록용으로 간단하게만 소개한다.기숙사 입소입소 당일에 짐이 너무 많아서 택시를 타고 왔다. 다행히 집이랑 그리 멀지 않기도 하고, 늦게 출발하니 막히는 시간에서 벗어나서 거의 하이패스로 도착할 수 있었고 택시비도 예상보다 훨씬 덜나왔다. (네이버 지도보다 약 1만원 정도 덜나와서 기분 좋았다) 그리고 기사님이 짐 많은 중생을 많이 도와주셔서 덕분에 잘 도착할 수 있었다.기숙사는 안내되는 바와 같이 2인 1실이다. 지금은 짐이 다 차있어서 그나마 입소하자 마자 찍어둔 사진으로나마 공유한다.참조로 기숙사에는 책상이 없다. 공부는 무조건 강의실에 와서 하거나 캠퍼스 곳곳에 놓여있..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 23.

백준 : 2470 두 용액

변수 설정N : 전체 용액의 수A : 주어진 용액의 특성값함수의 매개변수 : start, end이 문제에서는 target 설정이 불필요하다. A 리스트의 값을 더한 것의 절댓값 끼리의 비교이며, 0과의 거리가 가장 짧은 것을 구한다면, 절댓값이 가장 작은 수를 반환하면 되기 때문이다.문제 특성 상, 여러가지의 정답을 허용하기 때문에 어떤 값이라도 출력을 하고 그 값의 합이 0과 가장 가까운 값이라면 Pass를 준다.최종 코드def salt (start, end): best = float('inf') answer = (0, 0) while start 코드를 구성하며 어려운 점은, sum 값을 리스트에서 직접 받아와야 한다는 점과, 타겟 설정이 불필요하다라는 생각에 도달하기 까지 시간이 오래..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 22.

백준 : 2110 공유기 설치

백준 : 2110 공유기 설치백준의 2805 나무 자르기 문제와 동일하게 이진탐색을 이용하여 풀이하였고, 함수의 동작도 동일했다. 만약 나무자르기 문제 풀이를 완료했다면 동일한 로직으로 푸는데 크게 어려움이 없을것이라 예상된다.문제 이해이 문제는 문제의 요구사항을 이해하는게 관건이다. 문제 정의가 명확하지 않다면, 삽질을 할 가능성이 크다.N으로 주어진 집의 개수에 따라, C개의 공유기를 설치할 수 있는 최대 거리 중 각 공유기의 최소 거리를 구해야 한다. 요구 사항은 최소 거리를 리턴하는 것으로 정답은 하나만 있지만, 그 정답에 도달하는 방식은 여러개일 수 있다.즉 최소 거리는 동일하지만, 어떤 집에 설치할지는 다양할 수 있다. 주어진 집 간의 거리를 예시로 들어보자면,집의 좌표 : 1, 2, 8, 4..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 22.

백준 : 2805 나무 자르기

나무 자르기 문제는 이진탐색을 활용하여 나무를 자를 수 있는 최대 길이를 찾는 문제이다.변수 설정N : 나무의 수 , M : 가져갈 나무 길이의 총합h : 자를 나무의 길이height : 자르는 지점 (target)나무의 길이가 h보다 클때, h - height 의 값의 합이 7 (M) 이 될때 height의 최대값을 구해야 한다.최종 코드는 다음과 같다.import sysdef find_height(left, right, target): best = 0 while left mid : total += tree - mid if total >= target : best = mid left = mid + 1 ..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 21.

백준 : 9095 - 1, 2, 3 더하기

점화식으로 풀면 금방 푼다고 하는데, 점화식 자체를 이해하는데 한 시간이 걸렸다.. 손으로 다 써보니까 점화식이 무슨 말인지 이해가 간다.점화식의 풀이 과정을 다 써본 바로는 저렇게 나온다. dp(6) = dp(5) + dp(4) + dp(3) 을 정규식으로 바꾸면 다음과 같이 풀 수 있다. dp(n) = dp(n-1) + dp(n-2) + dp(n-3) 문제에서 n은 11이하의 양수라고 주어졌기에, 우선 리스트에 모든 가능한 dp값을 채워넣는 방식으로 접근했다. 그리고 a의 값에 따라, b 리스트에서 해당하는 인덱스의 값을 반환하도록 하였다. 만약, 값이 커진다면 재귀 함수를 이용한 풀이가 필요할 것으로 보인다.n = int(input())a = [int(input()) for __ in range (..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 3. 20.