본문 바로가기

공부하자

Kotlin 시작하기...문법편 (1) JAVA 로 안드로이드 앱 개발을 해본 적도 없었으나, Kotlin으로 앱 개발을 !도전! 해본다 ('23. 1/15일 시작) 간단한 문법부터 정리해보자 (필자 스스로 기억하기 위해 작성) // 1. 함수(Function) - void 타입 return fun A() { } // A() : Unit 생략 가능 - int 타입 return fun A(a : Int, b : Int) : Int { return a+b } * 위와 기능 동일 fun A(a : Int, b : Int) = a+b // 2. 변수 (Variable) - val (불변) fun A(){ val tmp : Int = 3 tmp = 4 //(X, 변경불가) } - var (가변) fun A(){ var temp : Int = 3 tem.. 더보기
네트워크 플로우 네트워크 플로우의 기본 정의는 위키에 나와있듯, 'In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge.' 즉, 유향 그래프이고 가중그래프 G 가 각각의 노드를 연결한 에지들의 유량을 통해서 문제를 모델링하는 과정인 셈이다. 실제로, 네트워크 플로우 문제는 직접 봐서는 네트워크플로우로 풀어야 하는건가? 라고 알 수 있을 만큼 직관적이지 않다. (물론 내공이 쌓이면.. 더보기
이분탐색 'N개의 배열안에 특정 M이라는 숫자가 존재하는지 알아내라' 라는 문제를 처음 봤을 때,단순히 "배열 인덱스를 하나씩 증가하면서 탐색하라는 거 아닌가?" 라고 생각할 수 있다. 하지만, 백준 1920 번 문제 https://www.acmicpc.net/problem/1920 와 같이 찾고자 하는 수의 범위가 크고, 배열의 크기 또한 큰 경우 시간초과가 날 수 있다. 이 경우 쿼리가 M개, 배열이 최대 N개 이기 때문에 O(NM) 이 발생하여 시간초과. 즉 다른 방법을 찾아보아야 한다. 이때, 방법을 절반을 나누어가면서(이등분) 탐색하는 건..? 이라는 접근을 통해 풀이해볼 수 있으며, 방법은 다음과 같다. 1) 배열을 우선 오름차순으로 정렬한다. 2) 현재 배열의 중심(MIDDLE) 을 파악한다. 3) .. 더보기
2294 동전2 이 문제는 앞서 풀었던 동전1과 모든 경우의 수를 구하는지, 최소의 개수로 K를 이룰 수 있는지 의 조건만 바꾸어주면 쉽게 풀 수 있다. 단, 이 문제의 경우 이룰 수 없는 경우가 있다는 것을 전제로 하기 때문에 처음 배열 생성시 -1로 초기화 해 주어 최종적으로 이룰 수 없는 경우 -1로 출력해주는 것이 바람직하다. 기존 동전1 방식에서 수정해준 부분은, 해당 동전의 개수로 판단해야하기때문에 1) 기존에 dp[j] += dp[j-코인] 였던 점화식을 dp[j] = dp[j-코인] + 1 과 같이 개수를 늘려주는 것과 2) 현재 배열에 이미 값이 존재한다면, 기존의 값과 비교하여 MIN 값을 판단한다. 소스코드는 아래와 같다. (dp[0] = 0 을 해주어야 하는 이유는 초기 동전값을 넣어주기 위함이다... 더보기
2293 동전1 올림픽과 설연휴에 빠져 놀기만하고ㅠㅠ, 이제서야 업로드한다. 이번에는 쉬운 DP에 속하는 동전1문제를 풀어볼건데 우선 주어진 동전의 개수(N) 가 최대 100이고, 원하는 값(K) 가 10000 이므로 완전탐색으로 구했을 경우에 시간초과가 나지 않는다. 단, 여기서는 DP임을 알고 1. 점화식을 구해야 하는 문제인지 2. 점화식을 구하지 않고 풀 수 있는 문제인지 를 판단해야 한다. 필자의 주관적인 입장이므로 필자의 경우 점화식을 구하지 않고 푸는 문제의 경우 재귀식을 사용한다. (아직 알고리즘 초보이므로 단언할 수 없다!) 이 문제의 경우 아래 그림과 같이 300원의 원하는 값을 만들기 위해 주어진 동전이 100, 200이라면 100원을 3개 사용하는 방법과 100원+200원을 사용할 수 있는 총 2가.. 더보기
10431 줄세우기 어려운 문제를 푸려다가, 모르는 알고리즘에 부딫혀 한동안 쉬운 문제만 또 풀게되었다..ㅠㅠㅠ 이번에는 조금 어려운 문제 해설을 올리고 싶었으나, 우선은 ACM 기출문제 (이것도 정답률 높은 문제) 를 올린다. 줄세우기는 같은 이름의 다양한 문제가 많은데, 이번 문제의 경우 기본 규칙? 정도만 알면 쉽게 접근할 수 있는 문제이다. 우선 현재 자신의 위치보다 앞에 키가 큰 학생이 있다면 바꾸어주어야 하기 때문에 정렬알고리즘을 생각하면 비교적 짧은 코드에 구현 가능할 것이라 생각한다. #include int T,num[21],N; int main() { scanf("%d", &T); while(T--){ int sum = 0; scanf("%d", &N); for (int i = 0; i < 20; i++) .. 더보기
세그먼트 트리 (Segment Tree) 세그먼트 트리 Segment Tree 는 주어진 query 수행을 빠르게 하기 위한 이진트리 구조로, 트리를 만드는데 O(nlogn), (전체 메모리 사용량 O(nlogn)) 특정 query를 수행하는데 O(logn) 이 수행된다. 그러면 앞서 펜윅트리를 살펴보았는데, 세그먼트 트리와의 차이점은 무엇일까? 세그먼트 트리는 범위를 통해 나누어지기 때문에, 여러값을 동시에 업데이트할 수 있다. 세그먼트 트리의 경우 이진트리 구조로 아래와 같이 범위로 노드들이 쪼개져 깊이 내려가는 구조이다. 보통은 line sweeping 문제에 사용되고 이 경우 선분의 개수 n 만큼의 리프노드가 생성, 높이 logn 의 형태로 이진트리가 나타난다. 간단하게 그림으로 아래와 같이 나타남을 확인해볼 수 있다. 범위에 따른 SU.. 더보기
펜윅트리 (Fenwick Tree) 펜윅트리 Fenwick Tree 는 Binary Indexed Tree (BIT) 라고도 한다. 설명하기 위해, 대표적으로 사용되는 그림을 통해 이해해보도록 하자. 아래에 해당하는 배열은, 각 인덱스를 2진수로 나타내었을 때 마지막 1의 위치를 통해 현재배열 이전에 몇개의 배열을 포함할것인가를 파악할 수 있다. 예를 들어, 인덱스가 10인 위치에서 생각해보면, 10을 2진수로 나타내었을 때 1010(2) 즉 마지막 1의 위치가 2번째에 있기 때문에 현재 10의 위치에서 앞으로 1칸 총 2개의 배열을 포함하는 값이 위 그림에 나와있는 하늘색 10에 포함되게 된다. 12 까지의 SUM을 구한다고 한다면, 하늘색으로 칠해진 8과 12를 더하면 12까지의 SUM 을 구할 수 있다. 그렇다면, Segment Tr.. 더보기
RMQ RMQ = Range Minimum Query 보통 범위가 작게 나올 경우, Bruteforce 방식으로 O(n^2) (n은 배열의 길이) 으로 가능하지만, 배열의 범위가 큰 경우에 시간초과가 날 수 있다. 이러한 경우, 1) (전처리 O(n)) O(루트n)시간안에 쿼리를 수행 : 배열의 구간을 루트n으로 나누어 각각의 구간마다 최소값을 구한다. 2) 전처리과정에서 O(nlogn), O(1) 쿼리 수행 가능 : 이 경우 배열을 각 2의 승수 만큼의 인덱스 구간마다 정답을 모두 구해놓는 것으로 만일 RMQ(X,Y) (X~Y 인덱스 사이의 최소값) 를 구하기 위해서 RMQ(X,Z) 와 RMQ(P,Y) (P < Z 라는 조건) 를 구한 후 더 작은 최소값이 정답이 된다. 예를 하나 더 들자면 현재값에서 +1 .. 더보기
1002 터렛 정답률이 굉장히 낮음에도 불구하고, 고등학교 때 ' 두 원의 교점 구하기' 문제를 풀어봤던 사람이라면 풀 수 있는 문제이다. 참고로 문제를 보고, 바로 원을 떠올릴 수 있어야 하고 필자의 경우 고등학생 시절 풀었던 SSEN 을 참고하여 구현해보았다. 규칙을 아래와 같이 5개의 규칙으로 나누어질 수 있는데 1. 한 원 안에 다른 원이 포함되 있는 경우 => 이 경우 내접하는지, 내접한다면 두원사이의 반지름길이가 같은지에 따라 세부적으로 나누어질 수 있다. 2. 두 원이 포함관계는 성립하지 않지만, 2개의 교점이 있는 경우 3. 두 원이 포함관계는 성립하지 않지만, 1개의 교점이 있는 경우 4. 포함관계도 성립하지 않고, 교점 또한 없는 경우 어떻게보면 5가지로 나누어질 수 있으나, 그림을 통해 설명해보겠다.. 더보기

티스토리툴바