wonseok.log wonseok.log

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제는 이분탐색을 활용한 Parametric Search 알고리즘을 사용해야 합니다. 1부터 최대 길이를 양쪽으로 하여 절반씩 길이일 경우에 원하는 랜선의 갯수가 되는지 확인하여 s와 e를 조정합니다. #include #include #include using namespace std; int main(){ int n,k; cin>>n>>k; int arr[10000]; for(int i=0;i>arr[i]; } long long s = 1; long long e = 1; for(int i=1;i

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 처음 생각했을 때 정렬 후 map을 통해 중복제거하고 값을 key로 0부터 하나씩 담기는 count를 value로 하여 추가한 풀이를 작성하였습니다. 이렇게 하면 map은 insert의 시간복잡도는 O(logN), 이후 정렬에 대한 시간복잡도 O(NlogN)이 걸려 전체 수에 대해서 탐색할 때의 시간복잡도는 O(N2logN)입니다. 다음 풀이는 무조건 시간초과가 나타나게 되는데 map이 아닌 unordered_map을 사용하면 이진 검색 트리가 아닌 해쉬 테이블로 구현이 되어 O(1)만에 통과할 수 있습니다. #include #include #include #include using namespace std; int main(){ int arr[1..

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 다음 문제는 이분탐색으로도 해결할 수 있습니다. 해당 수열을 정렬 후 처음 인덱스부터 끝까지 탐색을 하되 해당 인덱스의 값보다 M이 큰 값을 이분탐색을 하여 삽입할 인덱스를 찾을 수 있습니다. 즉, 정렬을 무너뜨리지 않고 해당 값을 추가할 인덱스(lower_bound)를 반환합니다. 하지만, 투 포인터 라는 알고리즘을 사용해서 풀이를 하려고 합니다. 이 문제에서 투 포인터를 사용하면 정렬할 때 O(NlogN)과 수를 고르는 방법 O(N)으로 시간복잡도는 O(NlogN)이 됩니다. #include #include #include using namespace std; int main(){ int arr[100000]; int n,m; cin>>n>>m..

이 문제는 C/C++로 풀이를 작성하였습니다. 문제 예시 풀이 부분합을 구하는 방법을 3중 for문을 이용해서 하나씩 덧셈을 하여 s를 넘었는지 확인하는 방법이 기본적으로 떠올릴 수 있습니다. 그리고 부분합 구하는 방법을 조금 배우신 분이라면 새로운 배열을 만들어 처음부터 해당 인덱스까지의 원소들의 합을 나타내는 배열을 만듭니다. 이후 2중 for문을 이용하여 sum(j) - sum(i)가 s가 넘었는지 확인하면 시간복잡도를 낮출 수 있습니다. 하지만 N의 크기는 10만이라 O(n2)이여도 시간초과가 발생하기 때문에 투 포인터 라는 알고리즘을 사용해서 풀어야 합니다. 투 포인터 를 사용하면 O(N)으로 해결할 수 있습니다. #include #include #include using namespace st..

Drawable Drawable은 Android Developer에서 정의한 바로는 "something that can be drawn" 를 위한 일반적인 추상클래스입니다. Drawable을 사용하여 사용자에게 보여지는 화면을 다양하게 꾸밀 수 있도록 합니다. 하지만, View와 달리 Drawable은 사용자와 상호작용하거나 이벤트 수신하는 API는 따로 존재하지 않습니다. Drawable과 Bitmap과의 차이를 정확하게 모르시는 분들도 있을 것 같은데, 위에서 정의한대로 Drawable은 그려지는 모든 것에 대한 추상클래스이고 Bitmap은 PNG, JPG, .gif 등과 같이 bit로 map 형태로 만들어 이미지를 표현하는 클래스라고 볼 수 있습니다. 즉, Drawable로 표현할 수 있는 하나의 ..

이 글은 "윤재성의 Google 공식 언어 Kotlin" 강의를 듣고 공부한 내용으로 작성하였습니다. Set Set은 수학에서 집합이라고 사용한 용어와 동일하게 데이터를 담는 컬렉션입니다. 데이터를 담는 순서가 관계가 없고 중복된 객체를 담지 않는다는 것이 특징입니다. 원하는 객체를 찾기 위해서는 순서가 정해지지 않았기 때문에 일일이 탐색해야 합니다. Set도 다른 컬렉션과 동일하게 불변형 set과 가변형 set이 존재합니다. immutable Set fun main(){ val set1 = setOf(1,3,5,3,1) println(set1) // [1,3,5] val set2 = setOf(2,4,5,5,4,2) println(set2) // [2,4,5] } setOf() 함수를 사용하여 불변형 ..

이 글은 "윤재성의 Google 공식 언어 Kotlin" 강의를 듣고 공부한 내용으로 작성하였습니다. Map Key와 Value의 값을 저장하기 위한 Collection 입니다. List와 동일하게 가변형 Map와 불변형 Map이 있습니다. immutable Map fun main(){ val map1 = mapOf("key1" to 1, "key2" to 2, "key3" to 3) val map2 = mapOf("key1" to '1', "key2" to '2', "key3" to '3') println(map1) // {key1=1, key2=2, key3=3} } Kotlin에서느 mapOf() 함수를 통해서 쉽게 map을 생성할 수 있습니다. map의 ..

이 글은 "윤재성의 Google 공식 언어 Kotlin" 강의를 듣고 공부한 내용으로 작성하였습니다. List Array와 동일하게 인덱스를 통해 원소에 접근이 가능한 선형 자료구조입니다. Array는 크기가 정해지면 변경할 수 없지만, List는 추가, 삭제가 가능합니다. Kotlin에서는 List를 생성할 때 특징이 있는데 불변형 리스트와 가변형 리스트가 있습니다. 불변형 리스트는 가변형 리스트에 비해 원소 접근하는 속도가 조금 더 빠르고 가변형 리스트는 새로운 원소를 추가할 때 추가 메모리 공간이 필요하기 때문에 메모리 효율측면에서도 떨어진다고 할 수 있습니다. 따라서 kotlin에서는 List를 사용할 때 변경해야할 경우에 불변형 리스트를 가변형 리스트로 변경 후 변경이 완료되면, 불변형 리스트로..