전체글397

• 

  [백준/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.