Partially Committed

오늘은 보다 간단한 상황에 대해서 공부해보자. 바로 Subsequence 판단 문제인데, Subsequence 의 정의는 아래와 같다. In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. - wiki 배열이 주어졌다고 가정하면, 원소의 순서를 바꾸는 행위 없이 일부 원소만 delete 하여 origin array 로부터 subsequence 을 만들어낼 수 있다. 예를 들어 [1,5,7,9] 에 대해서 [1, 5]..

배열이 주어지고, 배열 내에서 특정 조건을 만족하는 원소 쌍을 검색하는 문제 상황을 해결하는 방법에 대하여 공부해보자. 가령, 이런 상황이다. 유한 길이의 1 - d array 가 주어졌을 때, 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍을 찾아라. 어떠한 조합으로도 targetNum 을 만들 수 없다면 empty vector 을 반환하라. 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍은 유일하다. 면접에서 이 문제를 물어봤다고 가정하고, 차근차근 논리를 전개해보자. 먼저, 역으로 물어봐야 할 것은 어느 정도의 시간과 메모리를 허용하는지, 당연한 소리겠지만 원소의 타입은 integer 인지 그리고 2개의 원소에 대해서 조건을 만족하면 되는지, 반환해야하는 vector 내의 원소..

Algorithm || DataStructure #01. 구간합 Date : 2022/09/09 틀린 내용이 있을 시, 지적해주시면 감사하겠습니다! 1. 배열과 리스트 배열의 특징 인덱스를 사용해서 원소에 O(1) 에 접근 가능 새로운 값 삽입 및 특정 위치의 값 삭제가 비효율적. (땡기거나 밀어줘야함) 선언할 때 한번 지정한 배열의 크기는 늘리거나 줄일 수 없다. 리스트의 특징 값에 접근하려면 O(N) 이 필요함. 데이터의 삽입 삭제가 O(1) 에 가능 가변 길이임 예제 : 숫자의 합 https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc..