문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 문제의 조건을 고려하면서 어떻게 풀지 고민을 하면 위상정렬과 굉장히 유사하다는 것을 알 수 있다. 위상정렬에 정의는 순서가 있는 작업을 차례로 진행할 때, 순서를 결정하는 알고리즘이다. 문제에서 대놓고 문서를 풀 순서를 정하는 키워드가 있기도하다. 해당 문제에서 문제를 정하는 조건은 다음과 같다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은..
문제 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제 풀이 백준 문제를 자주 풀면 접해봤을 유형의 문제이다. 해당 문제의 유형은 LIS로 최장 증가 부분 수열의 길이를 구하는 문제이다. 왜냐하면 반도체의 선이 꼬이지 않게 가장 길게 연결하기 위해선 뒤에 등장하는 번호가 앞에 등장했던 번호들보다 커지면 안 되고, 이는 항상 앞에 등장했던 번호들보다 뒤에 등장하는 번호들이 작아짐이 보장되는 가장 긴 구간을 구해야 하기 때문..
문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 풀이 NXN의 배열을 일차원으로 압축시켜서 k번째 index의 수를 찾는 문제이다. 단순하게 NXN 배열을 만들어서 값을 i*j 값으로 넣어주기엔 N의 최댓값이 10^5승이므로 불가능하다. 따라서 실제 배열을 만들어주지 않고, 우리는 k번째 index의 수를 찾아야 한다. 우선 사용할 수 있는 정보는 배열의 원소들이 i*j의 형태로 계산된다는점과 A의 행렬..
문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 문제 풀이 출발지부터 도착지점까지 옮길 수 있는 중량의 최댓값을 구하는 문제이다. 해당 문제를 풀 수 있는 방법은 여러가지가 있다. 프림과 크루스칼을 통해서 start -> end까지의 최소 비용을 계산하는 방법도 있고, 이분탐색을 통해서 중량을 설정하고, 옮길 수 있는지에 대한 여부를 통해 mid 값을 조절하는 방법이 있다. 나는 ..
문제 https://www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 문제 풀이 문제를 보고 감이 안 잡혀서 알고리즘 분류를 보고 풀 수 있었던 문제였다. 비트마스킹이 왜 필요한가에 대해서 생각을 하다가, 저번에 풀었던 외판원 순회 문제가 떠올랐다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의..
프로젝트에서 Network 연결 상태에 따라 API 동작 및 화면을 갱신해야 했습니다. 여러 가지 방법이 있지만, 저는 공식문서에 나와있는 ConnectivityManager를 통해서 해결했습니다. 네트워크 상태 읽기 | Connectivity | Android Developers 이 페이지는 Cloud Translation API를 통해 번역되었습니다. 네트워크 상태 읽기 컬렉션을 사용해 정리하기 내 환경설정을 기준으로 콘텐츠를 저장하고 분류하세요. Android에서는 앱이 연결의 동적 변 developer.android.com 설명하기 전 네트워크 사용을 위해선 안드로이드 매니페스트에 다음 권한을 포함해야 합니다. 해당 권한은 음악, 갤러리 접근과 달리 일반권한이기 때문에 런타임에 요청할 필요가 없습..
문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 풀이 문제를 읽고 누적합을 구해서 소형차를 배정하는 문제인 것 같았다. 문제에서 주어진 테스트케이스에 대해서 먼저 누적합에 대한 그림을 그려보았다. 처음으로 접근한 방법은 정해진 구간까지의 최대 누적합을 구하는 방법으로 접근했다. 예를 들어 50까지 접근했을때의 최댓값은 40과 50을 태운 90이다. 다음으로 10까지 접근했을때의 최댓값은 40과 50을 태운 90 vs (35+40..
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 이전의 선택한 색에 따라 다음 선택이 영향이 받는 문제였고, 배낭 문제와 굉장히 유사하게 느껴졌다. 배낭 문제와 같이 물건을 담으면서, 해당 물건을 담을 경우와 담지 않을 경우를 나눠서 계산하는 것처럼 해당 문제도 색깔을 선택할 경우와 선택하지 않을 경우를 나눠서 계산하는 문제였다. 우선 그림을 그려가면서 가장 먼저 발견한 조건은 k가 n의 절반보다 크다면 경우의 수는 0이라는 점이다. 이는 문제에서도 ..
Contract 1.3.60 버전부터 사용되었으며, 컴파일러가 이해할 수 있게 명시적으로 자신의 동작을 설명할 수 있게 한다. 컴파일러가 이해할 수 있게 라는 말이 조금은 헷갈릴 여지가 있다고 생각한다. 코드를 통해 살펴보자 회원가입을 구현하려고 할 때의 시나리오를 생각해 보자. @JvmInline value class Password(val password: String) @JvmInline value class Id(val id: String) fun validate(id: Id?, password: Password?): Boolean { return id != null && password != null } fun signUp(id:Id?, password: Password?){ if(validat..
