AppBar 클래스 개요 AppBar 클래스는 앱의 상단 바를 구성하는 역할을 한다. AppBar는 다음과 같은 모양이다. 맨 위쪽엔 leading, title, actions 위젯이 있다. leading widget은 맨 앞에 놓일 위젯, title은 위젯에 들어갈 문구를 결정한다. actions 자리에는 보통 간단한 아이콘으로 기능을 추가하는 데에 사용된다. 중간에는 자유롭게 늘려 사용할 수 있는 공간인 flexibleSpace, 아래에는 bottom 위젯을 추가할 수 있다. 보통 다음과 같이 사용된다. 위의 앱에서는 title에 AppBar Demo라고 출력되고, actions에 아이콘이 추가되어 간단한 기능을 하는 예시이다. actions 예로 AppBar에 돋보기 아이콘과 알림 아이콘을 추가해보..

Flutter란? Flutter는 Google에서 개발한 오픈소스 어플리케이션 프레임워크이다. Flutter는 안드로이드, iOS, 리눅스, 맥, 윈도우를 위한 크로스 플랫폼 어플리케이션을 개발하는 데 사용될 수 있다. 현재까지 최신 버전은 May 19, 2021에 릴리즈된 Flutter 2.2이다. 앞으로 소개할 입문 글들은 모두 flutter.dev에 기반하여 작성된다. widget widget이란? flutter에서 widget은 중심적인 구성요소로서, UI의 각 부분에 대한 immutable한 description이다. widget은 반복적으로 사용될 수 있어서, tree에 몇 번이라도 포함될 수 있다. widget은 기본적으로 immutable하기 때문에, state를 변경하고 싶다면 State..

BOJ 9466 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 ver..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net • 접근 보통 피보나치 문제를 접근할 때에는 divide and conquer 또는 DP로 접근한다. n이 매우 작은 경우(BOJ 2747 참조)에는 재귀로 풀어도 풀 수 있다. 시간복잡도가 O(2^N)이기 때문이다. 그보다 n이 조금 더 커진다면 DP로 풀 수 있다. 이 경우 time complexity가 O(N)이므로 N이 대략 2억 언저리인 경우까지도 해결이 가능하다. 이 문제는 다르다. n의 upper bound가 1e18이다. 이런 경우에는 O(N)으로 풀 수 없다. ..

• 개요 Bellman-Ford algorithm에 대해서 찾아보는데, 대부분 간단하게, 또 과정 위주로 설명되어 있고 왜 Bellman-Ford algorithm이 정당성을 가지는지, 또 왜 그러한 순서로 해도 문제가 발생하지 않는지에 대해 설명이 부족한 것 같아 직접 정리하기로 하였다. • Single Source Shortest Path problems(SSSP) SSSP는 그래프 이론에서 아주 중요하고 또 자주 출제되는 문제이다. non-negative weighted graph와 관련된 문제의 경우에 Dijkstra's algorithm이 풀이에 사용되는데, 이는 time complexity가 O(VlogE)이므로 일반적인 graph에서 다른 알고리즘보다 빠른 측면이 있기 때문이다. 그러나 Di..

• Topological sort의 필요 directed acyclic graph(dag)의 경우 가끔씩 순서에 따라 linear한 정렬이 필요한 경우가 있다. 예를 들어 다음과 같은 상황을 가정해 보자. 수강할 강의를 선택하려고 한다. 매 학기 하나의 강의만 선택할 수 있고, 어떤 강의는 선수과목이 존재하여 선수강의를 수강하지 않았을 경우 수강할 수 없다. 이 경우 수강할 강의를 선택하는 방법을 제시하라. 위와 같은 상황을 graph로 나타내면 다음과 같을 것이다. 맨 처음 선택할 수 있는 과목은 A와 G 뿐이다. A를 수강한 다음이라야 비로소 B를 수강할 수 있고, D를 수강하려면 B와 G를 수강하여야 한다. F 과목을 수강하기 위해서는 F를 제외한 그래프 안의 모든 강의를 수강하여야 한다. 이런 문..

• segment tree with lazy propagation algorithm의 필요성segment tree는 구간에 대한 query를 O(logN)에 수행할 수 있도록 한다. 한 index에 대한 update를 수행할 경우에 update의 time complexity는 역시 recursive call에 의해서 O(logN)에 수행된다. 만약 한 index가 아니라 구간 [L, R]에 대한 update를 수행할 경우 [L, R]에 속한 모든 index에 대하여 update를 해 주어야 하므로 O((R-L+1)logN), 일반적으로 쓰면 O(NlogN)의 긴 수행 시간이 필요하게 된다. 이를 해결하기 위해서는 일종의 optimization이 필요한데, 이것이 바로 lazy propagation이다. ..

• 문제 설명 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net KOI 2010 고등부 1번 문제이다. 푸는 방법은 두 가지가 있는데, two pointers로 푸는 방법과 binary search로 푸는 방법이 있다. two pointers로 풀면 time complexity는 O(N^2)으로 풀 수 있고, binary search로 풀면 O(N^2*logN)으로 풀 수 있다. 다만 two pointers로 풀기 위해서는 ..

2013년도 KOI 도대회 고등부 3번 문제이다. 간단한 segment tree 문제처럼 보였는데, TLE를 3번 받았다. 해법은 간단하다. 1행의 케이블의 번호를 1, 2, 3, 4, 5의 오름차순으로 정렬하고, 2행의 케이블의 번호를 이에 맞게 다시 부여해준다. 그러면 예제의 경우 2, 4, 1, 3, 5가 되는데, 교차는 한 기계에서 그 앞에 자신보다 큰 숫자가 있을 경우에 발생한다. 예제의 경우를 보자. 2의 경우 교차는 0이다. 4의 경우도 교차가 0이고, 1의 경우 앞에 2와 4가 있으므로 교차가 2번 발생하고, 3의 경우는 4로 인해서 한 번, 5는 발생하지 않는다. 따라서 교차횟수는 총 3회이다. 따라서 https://jordano-jackson.tistory.com/33에서 다루었던 BO..