전체글397

• 

  [백준/BOJ] 2644번: 촌수계산 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해설 부모자식 관계가 성립하는지를 저장하기 위해 ArrayList라는 자료형을 가진 graph를 선언하였다. 부모자식을 양방향으로 모두 저장하였다면 dfs를 통해 찾고자 하는 두 사람의 관계가 나올 때까지 dfs 알고리즘을 수행하면 된다. 코드 private lateinit var visited: BooleanArray private val graph = ArrayList.. PS(Problem Solving)/BOJ 2022. 9. 20.

• 

  [컴퓨터 네트워크] 프로토콜 계층 구조 통신 프로토콜 정의 통신 장치들간에 교환될 메시지의 형식 정의(Syntax) 메시지 교환 순서 정의(Timing) 메시지를 교환할 때 수행해야할 행위를 정의(Semantics) 프로토콜 구조: 계층 구조 계층 구조의 예 웹 브라우저와 웹 서버 사이의 웹 페이지를 안전하고 효과적으로 전달하기 위해 여러 개의 프로토콜들이 사용되고, 이 프로토콜을 정의할 때 계층 구조가 사용되게 된다. 계층 구조의 장점 새로운 프로토콜 정의 용이 특정 통신 기능 또는 서비스 수정 용이 전체 시스템 이해 용이 계층 구조의 단점 최적 시스템 구현의 어려움(프로토콜 단위 사용, 계층 간 서비스 인터페이스 구현) 프로토콜 특정 통신 서비스를 위한 정보 교환 규칙 정의 유사한 통신 서비스를 위해 유사한 프로토콜 다수 정의 가능 물리 .. Computer Network 2022. 9. 18.

• 

  [백준/BOJ] 2583번: 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 해설 bfs를 이용하여 푸는 문제이다. 풀이 과정을 나눠보면 다음과 같다. 주어지는 좌표에 해당하는 영역을 미리 체크해놓는다. 모든 사각형의 체크가 끝났다면, 처음부터 반복문을 실행하며 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳을 찾는다. 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳에 도달했다면, bfs를 수행하여 영역의 총 크기가 얼마인지 구한.. PS(Problem Solving)/BOJ 2022. 9. 18.

• 

  [백준/BOJ] 1240번: 노드사이의 거리 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해설 n - 1개의 노드 사이의 거리가 주어지고, m개의 노드 사이의 거리를 구해야 한다. 크루스칼 알고리즘, dfs 등 여러 방법이 있을 수 있지만, 나는 문제를 보자마자 플로이드 와샬 알고리즘을 떠올렸다. n이 크지 않으므로 간단히 모든 노드 사이의 최소 거리를 구해놓고, 구하고자 하는 노드 사이의 거리를 출력하면 된다라고 생각했다. 또한 플로이드 와샬 알고리즘은 구현 방법도 쉽기 때문에 상당히 쉽게 풀은 문제였다. 코드 import.. PS(Problem Solving)/BOJ 2022. 9. 17.

• 

  [백준/BOJ] 1946번: 신입 사원 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 해설 문제에서 핵심 문장은 "어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다."이다. 즉, 두 성적이 모두 다른 지원자보다 떨어진다면, 그 사람은 면접에서 떨어지게 된다. 문제의 예시 중 첫 번째 테스트케이스를 보자. (3, 2), (1, 4), (4, 1), (2, 3), (5, 5).. PS(Problem Solving)/BOJ 2022. 9. 16.

• 

  [컴퓨터 네트워크] 네트워크 코어(Network Core) 코어 네트워크(Core Network) 정의 접속 네트워크(Access Network)들을 연결하기 위해 ISP들이 운영하는 광역 네트워크이다. 구성 라우터들을 고속의 링크로 연결 ※ 라우터: 고속의 링크들을 연결한 것 종단간(End to end) 경로 N개의 링크와 (N - 1)개의 라우터의 연결 라우터 구조 라우터가 하는 역할 2가지 1. 네트워크들을 링크를 통해 연결 - 연결 기능 2. 입력된 정보의 패킷(입력되는 정보의 단위)을 교환 - 교환 기능 패킹 스위칭(Packet Switching) 패킷(Packet) 전송 장치 간에 전달되는 정보 단위 공유 링크의 공정한 정송을 위한 긴 메시지를 작은 패킷 단위로 나누어서 전송 패킷 스위치(Packet Switch) 입력 링크와 출력 링크 간에 패킷 단.. Computer Network 2022. 9. 15.

• 

  [백준/BOJ] 13305번: 주유소 문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 해설 각 도시마다의 기름값이 나와있고, 기름 1L 당 1KM를 갈 수 있다. 우선 첫번째 도시에선 기름값이 얼마든지간에 기름을 넣어야 한다. 즉, 총 기름값을 저장할 변수를 total이라 했을 때, total의 초기값은 (첫 번째 도시의 기름값 + 첫 번째 도로의 길이)가 된다. 또한 맨 마지막 도시에선 더 갈 도로가 없으므로 기름값을 신경쓸 필요가 없다. 이는 반복문을 할 때.. PS(Problem Solving)/BOJ 2022. 9. 15.

• 

  [백준/BOJ] 20040번: 사이클 게임 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 해설 사이클을 구하는 문제이므로 union - find를 이용하여 문제를 풀었다. union-find는 사이클을 찾는 알고리즘으로 크루스칼 알고리즘을 구현하는데 쓰인다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고리즘(Kruscal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 그리디 알고리즘(Greedy.. PS(Problem Solving)/BOJ 2022. 9. 14.

• 

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