전체 글397

• 

  [백준/BOJ] 1005번: ACM Craft 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해설 선행 순서가 정해져 있고, 이를 특정 건물을 짓기까지 얼마나 오랜 시간이 걸릴지 구해야 한다. 선행 순서가 있는 문제에서 전체적인 순서를 구할 때 위상 정렬을 사용한다. 문제의 예제 2번을 보며 풀이를 해보자. 우선 차수가 0인 1번 정점부터 시작을 한다. 위상 정렬을 진행하므로 1번 정점을 큐에 넣고, 이와 연결된 간선들을 모두 제거한다. 이제 차수가 0인 것은 2번과 3번이다... PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 2473번: 세 용액 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 해설 두 용액 문제를 응용하여 해결할 수 있는 문제이다. 두 포인터 알고리즘을 사용하는 문제인데, 두 포인터를 사용하면 두 개의 값만을 알 수 있다. 따라서 한개의 값을 더 정해야 하는데, 이는 고정적인 값을 하나 정한 후 두 포인터 알고리즘을 수행하는 것으로 해결하였다. 문제의 예시로 풀이를 해보자. {-2, 4, -99, -1, 98}이 있다. 이를 정렬하면 {-99.. PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 12015번: 가장 긴 증가하는 부분 수열 2 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해설 문제의 예시를 가지고 문제를 풀어보자. 10 20 10 30 20 50이 있다. 여기서 가장 긴 증가하는 부분 수열(LIS)은 {10, 20, 30, 50}이 된다. 이를 구하는 방법으론 dp를 사용하는 것이 가장 먼저 떠오를 것이다. 하지만 dp를 사용하게 되면 범위가 너무 커 시간 초과가 발생한다. 이를 이분 탐색을 통해 해결할 수 있다. 우선 makeLis라는 배열을 선언해놓겠다... PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 1766번: 문제집 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해설 문제들의 선행 순서를 입력으로 받고, 이를 이용하여 순서를 짜야한다. 또한 문제의 난이도는 1번 문제가 가장 쉽고 N번 문제가 가장 어려우며, 가능한 쉬운 문제부터 문제를 풀어야 한다. 이러한 유형의 문제는 위상 정렬을 이용하여 해결할 수 있다. 위상 정렬을 이용하나, 이 문제에서는 문제의 난이도까지 고려해야하고, 이는 문제의 번호가 낮을수록 쉽우므로 우선.. PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 9252번: LCS 2 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해설 문제의 예시를 보자. ACAYKP, CAPCAK 두 문장이 있다. 여기서 부분 수열이 되는 수열 중 가장 긴 것은 ACAK이다. 이를 찾아가는 과정을 보자. 우선 2차원 배열을 선언할 것이다. dp라는 이름을 가진 배열이라 하자. 각 인덱스의 값을 정할 때, str1[i] == str2[j]라면 부분 수열이 되는 값이 하나 늘은 것이므로 .. PS(Problem Solving)/BOJ 2022. 9. 12.

• 

  [Android] Notification 사용법 Notification Notification을 해석해보면 "알림"이다. 평소 핸드폰을 사용하다 보면 문자가 왔을 때, 부재중 전화가 와있을 때, 스크린샷을 찍었을 때 등 여러 경우에서 알림창이 뜨는 것을 확인할 수 있다. 이와 같은 기능을 구현하는 것이 Notification이다. Notification은 NotificationManager의 notify() 함수로 발생한다. notify() 함수에는 NotificationCompat.Builder가 만들어 주는 Notification 객체를 대입하며 이 객체에는 알림 정보가 저장된다. 또한 NotificationCompat.Builder를 만들 때 NotificationChannel 정보를 대입해줘야 한다. 즉, NotificationChannel로 .. Android 2022. 9. 11.

• 

  [컴퓨터 네트워크] 네트워크 엣지(Network Edge): 접속 네트워크(Access Network) 네트워크 엣지(Network Edge) 인터넷에서 호스트(Host) 또는 종단 장치가 연결되는 접속 네트워크(Access Network) 접속 네트워크 구분 Home Access Network: DSL(Digial Subscriber Line), Cable, FTTH(Fiber To The Home), Ethernet/WIFI Enterprise Access Network: Ethernet/WIFI Mobile Access Network: 3G, 4G/LTE, 5G DSL(Digital Subscriber Line) 네트워크 구성 DSL 종류와 채널 구성 ADSL: 케이블 길이가 길면서도 고속의 데이터 전송이 가능한 기술로 10Mbps 전후의 전송속도 제공(전화선 길이에 따라 달라짐) VDSL: 전화선의.. Computer Network 2022. 9. 11.

• 

  [백준/BOJ] 2623번: 음악프로그램 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 해설 보조 PD 3명이 담당한 가수들의 순서를 정한다. 이때 한 가수를 여러 보조 PD가 담당할 수 있다. 이렇듯 이미 순서가 정해져 있고, 선행 순서를 위배하지 않으면서 순서를 정하는 것은 위상 정렬(topological sort) 알고리즘을 사용하면 된다. 위상 정렬은 여러 가지 답이 나올 수 있으므로, 코드를 어떻게 짜냐에 따라 답이 달라질 수 있다. 코드 impor.. PS(Problem Solving)/BOJ 2022. 9. 10.

• 

  [알고리즘] 위상 정렬(Topological Sort) 위상 정렬(Topological Sort) 순서가 정해져 있는 작업을 어떠한 차례로 수행해야 하는지 결정해주는 알고리즘이다. 즉, 방향 그래프에 존재하는 정점들의 선행 순서를 위반하지 않고 모든 정점을 나열하는 것이다. 위상 정렬은 한 방향 그래프에서 여러 위상 정렬이 가능하다. 즉, 답이 여러가지일 수 있다는 것이다. 위 방향그래프에서 위상 정렬을 한 결과를 생각해보면 다음과 같다. 1 → 6 → 2 → 5 → 4 → 3 6 → 2 → 1 → 5 → 4 → 3 6 → 1 → 2 → 5 → 4 → 3 과정 진입 차수가 0인 정점을 큐에 저장한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 이후 진입 차수가 0인 정점을 큐에 저장한다. 큐가 빌 때까지 반복한다. 이때, 모든 원소를 방문하.. Algorithm 2022. 9. 10.

• 

  [백준/BOJ] 2467번: 용액 문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 해설 두 용액을 합쳐 0에 가장 가깝게 만들어야 한다. 모든 용액을 입력받은 후, 투 포인터 알고리즘을 통해 문제를 해결하면 된다. 다음과 같이 양 끝점을 변수로 하나씩 잡아 더해준다. 여기서는 -99 + 98이므로 -1이 된다. 값이 -이므로 왼쪽 포인터를 한 칸 옮겨 -2 + 98을 해본다. 이 값이 기존의 합보다 0에 가깝다면 과정을 계속 반복해주면 된다. 코드 import jav.. PS(Problem Solving)/BOJ 2022. 9. 9.

• 

  [백준/BOJ] 13904번: 과제 문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 해설 우선순위 큐를 이용한 그리디 알고리즘으로 문제를 풀었다. 문제의 예시를 보자. 다음과 같이 점수가 더 큰 문제부터 차례대로 정렬을 해놓았다. 우선 점수가 가장 큰 60점짜리 문제는 4일이 마감 기간이므로 4일에 문제를 풀도록 하자. 이제 다음으로 점수가 높은 50점짜리 문제를 보자. 이 문제 또한 2일째에 아직 아무 계획이 없으므로 2일째에 끝내도록 하자. 다음으로 40점짜리 문제이다. 이 문제의 마감기한은 4일이지만, 이미 4일.. PS(Problem Solving)/BOJ 2022. 9. 9.

• 

  [백준/BOJ] 5972번: 택배 배송 문제 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 해설 전형적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 통해 1번 헛간에서 시작하여 마지막 헛간에 도착했을 때의 최소 비용을 구해 출력하면 된다. 다익스트라 알고리즘을 잘 모른다면 이 글을 읽어보는 것을 추천한다. 코드 import java.util.* import kotlin.collections.ArrayList private lateinit var graph: Array private.. PS(Problem Solving)/BOJ 2022. 9. 7.

• 

  [백준/BOJ] 13424번: 비밀 모임 문제 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 해설 각 방 사이 비밀 통로를 이용하는 비용이 나와있다. 플로이드 와샬 알고리즘을 이용하여 각 방 사이를 오가는데 필요한 최소 거리를 구해놓은 후, 현재 친구들이 있는 방에서 각 방까지 가장 작은 비용으로 갈 수 있는 방을 찾으면 된다. 코드 import java.util.* import kotlin.collections.ArrayList import kotlin.math.min privat.. PS(Problem Solving)/BOJ 2022. 9. 7.

• 

  [백준/BOJ] 15644번: 구슬 탈출 3 문제 https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 이전 문제인 구슬 탈출 2문제랑의 차이점은 출력에 경로가 추가된 것밖에 없다. 앞부분은 구슬 탈출 2문제랑 같으므로 저 글을 확인하도록 하자. 이제 경로를 추가해야 한다. 데이터 클래스에 경로를 저장할 route라는 변수를 추가해주었다. 이제 움직인 방향에 따라 왼쪽이라면 "L", 오른쪽이라면 "R", 위라면 "U", 아래라면 "D"를 .. PS(Problem Solving)/BOJ 2022. 9. 6.

• 

  [백준/BOJ] 13459번: 구슬 탈출 문제 https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 이전에 구슬 탈출2 문제를 풀고 구슬 탈출1문제도 있을 것 같아 검색해보니 역시나 있었다. 구슬 탈출2 이 글을 보고 오는 것을 추천한다. 이 문제와 구슬 탈출2 문제는 출력에만 차이가 있고, 다를 것이 없다. 구슬 탈출2 문제에서는 빨간 구슬이 탈출하는데 최소 몇 번 움직여야 하는지를 출력하는 것이고, 이 문제는 탈출할 수 있다면 1, 없.. PS(Problem Solving)/BOJ 2022. 9. 5.

• 

  [백준/BOJ] 13460번: 구슬 탈출 2 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 빨간 구슬과 파란 구슬 두개가 있다. 이 중 10번 이하로 움직여서 빨간 구슬만이 구멍에 들어가게 해야한다. 만약 두 구슬 모두 구명에 빠지는 경우 -1을 출력하게 된다. 처음에는 빨간 구슬을 관리할 큐, 파란 구슬을 관리할 큐 이렇게 두개를 만들어 문제를 해결하려 했다. 하지만 한개의 큐로 모든 정보를 다 담고 하는 것이 더 나을 것 .. PS(Problem Solving)/BOJ 2022. 9. 5.

• 

  [백준/BOJ] 2638번: 치즈 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 해설 문제에서는 치즈의 외부 공기와 내부 공기로 나뉘어 있다. 외부 공기에 2면 이상이 닿아있다면, 그 부분은 녹는다. 내부 공기에 닿은 것은 무시하여도 된다는 것이다. 따라서 문제를 크게 나눠보면 다음과 같다. 외부 공기와 내부 공기를 구분한다. 현재 위치에 있는 치즈가 두 면 이상이 닿았는지 확인하고, 2면 이상 닿아있다면 그 치즈를 녹인다. 더 녹일 치즈가 있는지 확인한다... PS(Problem Solving)/BOJ 2022. 9. 4.

• 

  [백준/BOJ] 2660번: 회장뽑기 문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 해설 두 회원이 친구 사이라면 1, 친구의 친구 사이라면 2, 친구의 친구의 친구 사이라면 3 ... 과 같이 숫자가 증가한다. 예를 들어 1, 2, 3의 회원이 있을 때, 1번 회원과 2번 회원이 친구 사이이고, 2번 회원과 3번 회원이 친구 사이라면 1번 회원과 3번 회원은 친구의 친구 사이이므로 2의 값을 가지게 된다. 즉, 한 다리를 거쳐 알 수 있다는 것이므로 플로이드 와샬 알고리즘.. PS(Problem Solving)/BOJ 2022. 9. 3.

• 

  [컴퓨터 네트워크] 인터넷과 프로토콜 인터넷(Internet) Internet은 Inter-Connected Network of Networks의 약자이며, 네트워크들을 상호 연결한 네트워크이다. 인터넷을 구성하는 내부의 네트워크를 subnet이라고 한다. 이러한 subnet들을 상호 연결한 것이 인터넷이다. 즉, 인터넷도 한 개의 네트워크이다. 네트워크(Network) 다양한 유형의 호스트와 스위치들을 통신 링크로 연결한 분산 시스템 즉, 네트워크는 크게 호스트와 스위치로 구성되어 있다. 호스트(Host) 인터넷의 끝에 연결되는 종단 장치(End-System)이다. ex) PC, 서버, 스마트폰, Iot 센서 등등 (통신) 링크(Link) 통신 장치들 간에 정보 전달 단위인 패킷(packet)을 전달하는 유, 무선 매체(Media) ex).. Computer Network 2022. 9. 3.

• 

  [백준/BOJ] 1507번: 궁금한 민호 문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 해설 플로이드 와샬 알고리즘을 역으로 이용하여 문제를 해결할 수 있다. 플로이드 와샬 알고리즘을 생각해보자. 만약 1번 도로, 2번 도로, 3번 도로가 있을 때, 1 - 2, 2 -3번 간 도로가 있다면 1 - 3번 도로는 없어도 1 - 2 -3을 통해 갈 수 있다. 즉 map[1][3] == map[1][2] + map[2][3]이 되는 것이다. 따라서 이 문제에서는 m.. PS(Problem Solving)/BOJ 2022. 9. 3.