전체글397

• 

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

• 

  [백준/BOJ] 16197번: 두 동전 문제 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 해설 두 동전 중 하나만 보드에서 떨어트리기까지 최소 몇번을 움직여야 하는지 구해야하는 문제이다. bfs를 이용하여 문제를 해결할 수 있다. bfs를 수행할 때 방문여부를 체크하는데, 이 문제에서는 동전이 2개이며 각각의 (y, x)좌표를 갖고 있으므로 4차원 배열을 이용하여 방문여부배열을 선언해야 한다. 즉, 다음과 같이 선언된다. visited[row][col][row][col] 입력을.. PS(Problem Solving)/BOJ 2022. 9. 2.

• 

  [백준/BOJ] 1719번: 택배 문제 https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 해설 플로이드 와샬 알고리즘을 응용하여 문제를 해결할 수 있다. 플로이드 와샬을 진행하므로 자기 자신으로 향하는 노드는 0으로, 그 외에는 INF(임의로 지정)으로 초기화해준다. 이후 간선의 정보를 입력받아 어떠한 노드에서 어떠한 노드로 향할 때 얼마의 비용이 드는지를 저장해주고, a->b와 같이 한 번에 갈 수 있는 노드들은 경로를 저장해 줄 배열 path[a][b] = b와 같이 된.. PS(Problem Solving)/BOJ 2022. 9. 1.

• 

  [백준/BOJ] 1185번: 유럽여행 문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 해설 N-1개의 길만을 남겨야 한다. 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 위 3 문장은 문제에서 가장 핵심이 된다 생각한 것들이다. 우선 1, 2번을 보면 최소 신장 트리를 구해야 한다는 것을 알 수 있다. 이때, 문제에서는 각 나라에 .. PS(Problem Solving)/BOJ 2022. 8. 31.

• 

  [백준/BOJ] 1613번: 역사 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 해설 n개의 사건들의 전후 관계가 주어진다. 이를 통해 두 개의 사건의 전후 관계를 알아낼 수 있는지, 안다면 먼저 일어났는지, 후에 일어났는지를 알아내면 된다. 플로이드 와샬 알고리즘을 이용하면 모든 사건들의 전후 관계를 한번의 알고리즘 수행으로 알아낼 수 있다. 전후 관계를 표시할 배열들을 초기값(INF = 987654321이라 하자.)으로 선언해준다. 이때 같은 사건(i == j.. PS(Problem Solving)/BOJ 2022. 8. 30.

• 

  [백준/BOJ] 14938번: 서강그라운드 문제 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 해설 어떠한 지역에 떨어졌을 때, 수색 범위 안에서 가장 많은 아이템을 얻을 수 있는지를 구하는 문제이다. 우선 모든 지역에서의 범위를 구해야 하기 때문에 1번 지역에 떨어졌을 때 모든 지역까지의 거리를 구해야 하고, 2번 지역에 떨여졌을 때 모든 지역까지의 거리, 3번, 4번 . . . n번에 떨어졌을 때의 모든 지역까지의 거리를 구해야 한다. 모든 지역까지의 거리를 구하는 알고리즘으로 다익스트.. PS(Problem Solving)/BOJ 2022. 8. 29.

• 

  [백준/BOJ] 16928번: 뱀과 사다리 게임 문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 해설 총 100개의 칸으로 이루어진 보드판에서 주사위를 굴려 100번째 칸에 도달할 수 있는 최소 횟수를 구하는 문제이다. 문제의 조건으로 100번 칸을 넘어가면 이동할 수 없으므로, 딱 100번째 칸에 도달했을 때의 값을 구해야 한다. 우선 뱀과 사다리 각각 어떠한 칸에 놓여 어떠한 칸으로 입력되는지를 저장해놓기 위해 두 개의 Map을 선언하였.. PS(Problem Solving)/BOJ 2022. 8. 28.

• 

  [Android] PendingIntent란? PendingIntent PendingInten는 Pending과 Intent를 합쳐놓은 단어이다. Intent란 무엇인가? 컴포넌트 간의 작업 수행을 위한 정보를 전달하는 역할을 맡고 있다. 이제 Pending에 대해 알아보자. Pending을 직역해보자면 다음과 같다. "보류", "임박한"의 뜻을 가지고 있다. 이제 Pending과 Intent를 합친 PendingIntent에 대해 유추해볼 수 있다. PendingIntent는 Intent(정보 전달)을 바로 실행하는 것이 아닌, 특정 시점에 수행하도록 하는 역할을 하는 것이고, 기본 목적은 다른 애플리케이션의 권한을 허용하여 가지고 있는 Intent를 본인 앱의 프로세스에서 실행하는 것처럼 사용하게 하는 것이다. 예를 들어 Notification으.. Android 2022. 8. 26.

• 

  [백준/BOJ] 1660번: 말이 되고픈 원숭이 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 해설 출발점에서 도착점까지 움직일 때, 최소로 움직일 수 있는 값을 출력하는 문제로 BFS를 사용하여 문제를 풀 수 있었다. 원숭이는 상하좌우로 움직일 수 있고, k번 이하로 말처럼 움직일 수 있다고 한다. 나는 이를 말이 움직일 수 있는 좌표와 원숭이가 움직일 수 있는 좌표로 각각 저장해주었다. private val monkeyX = intArrayOf(1, -1, 0, 0.. PS(Problem Solving)/BOJ 2022. 8. 26.