문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 배열 A 1 2 3 1 1 2 3 2 2 4 6 3 3 6 9 배열 B 1 2 2 3 3 4 6 6 9 풀이 알고리즘 : 이분 탐색 k번째 수를 찾는 이분 탐색을 수행 - start = 1, end = k : k번째 수는 k보다 작거나 같음 - mid가 몇 번째 수인지 아는 방법 : mid보다 작거나 같은 숫자를 구하기 -> i * j mid // i but mid // i 가 N보다 클 경우가 있으므로 min(mid // i, N) Python 코..

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 풀이 대표적인 다이다믹 프로그래밍 문제. DP 문제는 처음이라 못 풀고 풀이를 보면서 코드를 짰는데 나중에 자세하게 이 부분을 쓰고자 한다. ========================== Python 코드 import sys input = sys.stdin.readline string1 = input().rstrip() string2 = input().rstrip() array = [[0]*(len(string2)+1) for _ in range(len(st..

문제 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 풀이 알고리즘 : 스택 - 배열 prices, 이전 떨어지지 않은 주식 stack을 생성한다. - 배열 prices를 순환하는 반복문 - stack에 있는 prices + 1 - stack을 순환하면서 현재 주식과 비교 후 가격이 떨어졌으면 stack에서 뺀다. - 현재 주식을 stack에 더한다. Python 코드 def solution(prices): answer = [0]*len(prices) stack = [] popList = [] for idx, cnt_price in enumerate(prices) : if stac..

문제 링크 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 트럭 갯수 : n, 다리의 길이 : w, 다리의 최대 하중 : L - w대의 트럭만 동시에 올라갈 수 있다. - 단위 시간에 하나의 단위 길이만큼 이동한다고 가정 - 다리 위에 올라가있는 트럭의 무게 합 deque 사용- nList에서 트럭을 뺄 때와 빼지 않을 때를 고려한다. 반복문 사용 - 공통적으로 시간+1, bridge에서 하나..

링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 문제 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라. 알고리즘 투 포인터 풀이 방법 입력받은 인형 리스트 안에서 라이언이 있는 인덱스만을 뽑은 후 슬라이딩 윈도우 이용 코드 import sys input = sys.stdin...

시간 복잡도와 Big-O 표기법 정리와 더불어 코테 준비로 사용하는 python 언어에서 자료형별 시간복잡도를 정리하였다. 1. 점근 표기법(Asymptotic notation) 점근 표기법 : 알고리즘의 성능과 효율성을 표기해주는 표기법 여기서 말하는 효율성은 실행시간이 적으냐(=시간복잡도), 메모리를 덜 차지하는지(=공간복잡도)에 걸려있다. 결국 시간복잡도와 공간복잡도를 나타내는 표기법인 셈. 시간복잡도(Time Complexity) : 입력된 N의 크기에 따라 실행되는 조작의 수 공간복잡도(Space Complexity) : 알고리즘이 실행될 때 사용하는 메모리의 양 점근 표기법에는 대표적으로 대문자 O 표기법, 소문자 o 표기법, 대문자 오메가(Ω) 표기법, 소문제 오메가 표기법(ω), 대문자 세..