LIS LIS; Longest Increasing Subsequence 최장 증가 부분 수열 original array의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열 LIS 길이 구하기 1. DP - O(N^2) length를 아래와 같이 정의할 때, DP를 활용하여 LIS의 길이를 구할 수 있다. length[i]: i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이 이때 length.size == array.size 이다. for (i in array.indices) { length[i] = 1 for (j in 0 until i) { if (array[j] < array[i]) length[i] = max(length[i..
1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 안녕하세요. 백준의 꼬인 전깃줄 문제입니다. 최장 증가 수열의 길이를 우아하게 돌려돌려 물어보는 문제에요. 이 문제를 풀 때만 해도 LIS의 길이 구하는 방법은 DP, 즉 O(N^2)인 방법만 알고 있었어서 10만...이라는 입력값을 보고 뭔가 이상하다고 생각했습니다. 곱셈이 헷갈려서 계산기로 10만*10만을 해 봤습니다. 그리고 못 푸는 문제다 싶어 호다닥 구글링으로 정답 풀이를 참고해서 풀었습니다. 근데 알고리즘을 알고 나니 제법 쉬운 문제였어..
안녕하세요. 지난번에 kotlin의 Equality에 대해 포스팅했었는데요. 아래 포스팅입니다. Kotlin의 Equality, == vs === Equality | Kotlin kotlinlang.org 공식문서에 따르면 kotlin에는 두 가지 타입의 Equality가 존재합니다. Structural equality와 Referential equality인데요. 간단히 말하자면 Structural equality는 값을 비교하는 것이고, Ref dev-sia.tistory.com Structural equality와 Referential equality, 동일성과 동등성에 대해 정리하면서 == 연산자와 === 연산자의 차이에 대해 알아보았습니다. 그리고 equals를 호출했을 때 동일성과 동등성을 비..
2932번: 표 회전 상근이는 N×N 표를 만들었다. 표에는 1부터 N2까지의 수가 행 우선 순서(row-major order)에 따라 쓰여져 있다. 표가 수행할 수 있는 연산은 아래와 같이 두 가지이다. 행을 회전시킨다 - 한 행을 골라 www.acmicpc.net 백준의 표 회전 문제입니다. 이 문제...분명 풀었을 때는 실버 3이었던 것 같은데 실버 2가 되었네요. 사실 반년 전에 푼 문제인데 아직도 풀이방법을 잊을 수 없는... 그런 매콤한 추억이 있는 문제랍니다. 제출 300, 정답 98, 맞힌 사람 73으로 정답 비율이 35%입니다. 그런데 백준에서 맞힌 사람 200명 안넘으면 티어를 믿으시면 안 됩니다. 보통 고수들이 새로운 문제 나왔다고 찍먹해보거나 아무것도 모르는 뉴비들이 랜덤뽑기로 풀게..
안녕하세요. 6월 회고입니다. 벌써 7월 중순이네요. 왜...? 면접스터디 CS스터디가 벌써 4회차를 앞두고 있습니다. 무슨 뜻이냐면 아무도 도망가지 못했다는 뜻이죠... 사실 신기하게도 저희 중 누군가가 인턴을 붙었습니다. 그래도 스터디는 해야지... 하반기 가보자고. 전환되면 놓아드리겠습니다. 출근러와 백수들아 4회차도 잘 부탁해! 이제 누구 하나 취뽀하는 날에는 진짜 소고기 먹으러 가지 않을까 싶어요. 5월달까지만 해도 삼겹살 먹을 것 같았는데... 6월의 수확 없습니다. 닥닥 끌어모아 보자면 일단 1일 1커밋을 꾸준하게 이어가고 있구요.(놀랍게도 내일모레 200일) 패캠에서 안드로이드 강의를 하나 사서 듣고 있는데 아직까지는 너무너무 만족입니다. 이거 다 듣고 앱 세개 만들어서 광고달고 용돈벌이를..
