CS (138) 썸네일형 리스트형 [백준] 1058. 친구 https://www.acmicpc.net/problem/10581. 플로이드워셜로 푸는 방법플로이드워셜은 N개의 노드에서 N개의 노드로 이동하는데 걸리는 최단 거리(비용)을 구할 수 있다. 즉, 각 노드에서 다른 N-1개의 노드로 몇 번의 이동으로 도달 가능한지 구한 후(=사람 a와 사람 b의 관계), 1번 또는 2번으로 이동이 가능하면 2-친구 관계이므로 카운트해주면 된다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new Inpu.. [프로그래머스] 등대 https://school.programmers.co.kr/learn/courses/30/lessons/133500?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr트리간선이 n-1개이고, 모든 등대가 서로 다른 등대로 이동 가능하다.즉, 사이클이 생길 수 없다. 따라서 트리로 바라볼 수 있고 dfs, bfs 같은 트리 순회 방법을 사용할 수 있다.그리디임의의 한 점을 루트 노드라고 생각하여, dfs를 진행한다고 가정하자. 가장 아래인 리프 노드는 불이 켜질 필요가 없다. 즉, dfs를 진행하며 가장 아래인 리프 노드까지 내려간 뒤, 리.. 다익스트라 알고리즘 - 우선순위 큐와 방문 처리에 대해 다익스트라 문제를 풀다가 공식처럼 우선순위 큐를 사용하고, 방문 처리를 하는 느낌이 들었다. "우선순위 큐를 꼭 사용해야 하는가?", "방문 처리를 꼭 해야 하는가?" 라는 궁금증이 들어서 이 글을 작성한다. https://www.acmicpc.net/problem/1753 이 문제를 예로 들자. 입력 값이 다음과 같고, 1번 노드에서 출발한다고 가정하자.5 611 2 21 3 32 3 42 4 53 4 14 5 2 간선을 리스트로 표현하면 다음과 같고, 1 ➡️ 2 ➡️ 3번 노드 순서로 방문했을 때의 모습은 다음과 같다. 이때 큐에는 (4, 7)과 (4, 4)가 담겨있다. (노드 4번까지 오는데 걸린 비용이 각각 7, 4)우선순위 큐를 사용하지 않을 경우(4, 7)을 먼저 poll한다. 그리고 cos.. TCP/IP 네트워크 스택 이해하기 TCP/IP의 중요한 성질Connection oriented먼저 두 개의 엔드포인트(local, remote) 사이에 연결을 맺은 후 데이터를 주고받는다. 이때 TCP 연결 식별자는 형태이다. Bidirectional byte stream양방향 데이터 통신을 하고, 바이트 스트림을 사용한다. 이 바이트 스트림은 여러 패킷으로 분할되어 전송되지만, 수신측의 TCP에서 이러한 패킷을 일련의 바이트 스트림으로 재조립하여 응용 계층에서 처리할 수 있게 한다. In-order delivery송신자가 보낸 순서대로 수신자가 데이터를 받는다. 이를 위해서는 데이터 순서가 필요한데 순서를 표시하기 위해 TCP 세그먼트 필드에 32비트의 sequence number 필드가 있다. Reliability through A.. 프로세스 동기화, 데드락(교착 상태) 공유 자원, 임계 영역(Critical Section), 경쟁 상태(Race Condition)공유 자원: 여러 스레드가 동시에 접근할 수 있는 자원을 공유 자원이라고 한다.임계 영역: 공유 자원 중 여러 스레드가 동시에 접근했을 때 문제가 생길 수 있는 부분을 임계 영역이라고 한다.경쟁 상태: 둘 이상의 스레드가 공유 자원에 동시 접근했을 때 실행 순서에 따라 결과 값이 달라지는 상황을 의미한다.따라서 경쟁 상태를 방지하고 데이터 일관성을 보장하기 위해 임계 영역에 하나의 스레드만 접근할 수 있도록 제어해야 한다.* Race Condition은 CPU 코어가 1개일 때도 발생할까?결론은 Race Condition은 CPU 코어가 1개일 때도 발생한다. CPU 코어가 1개인 경우에는 동시에 하나의 프로세.. [백준] 10713. 기차 여행 https://www.acmicpc.net/problem/10713 가격 비교 (min(a * k, c + b * k)) 각 철도를 이용하는 총 횟수를 알아내고, 그에 따라 해당 철도를 이용할 때 티켓을 구매하는 방법과 IC 카드를 구매하는 방법 중 가격이 더 작은 방법을 이용하면 된다.철도 이용 횟수 구하기 (누적합)각 철도를 이용하는 횟수를 구해야 하는데, 만약 도시 1번에서 3번으로 이동할 경우, 1번 철도와 2번 철도를 이용한다. 그런데 이런 식으로 카운트하면, 이동 횟수가 m번이고 매 이동마다 가장 먼 도시로 이동한다고 가정했을 때 O(m * n)의 시간 복잡도가 소요되어 시간초과가 날 수 있다.따라서 누적합을 이용해야 한다. 누적합 활용 방식은 다음과 같다.도시 1번에서 5번으로 이동한다고 .. [백준] 1941. 소문난 칠공주 https://www.acmicpc.net/problem/1941 처음에는 5 X 5 그래프의 각 노드를 시작으로 그래프 탐색을 해서 7명을 모으는 것을 생각했다. 그런데 같은 조합이 여러 번 나올 수 있다. (학생 1 -> 2 -> 3인 조합과 학생 3 -> 2 -> 1의 조합은 같기 때문) 그리고 이때 이미 나온 조합인지 일일이 검사하는 건 매우 비효율적이다. 따라서 25명의 학생 중 7명의 학생 조합을 찾고(백트래킹), 이 조합의 학생들이 모두 연속된 자리인지, 그리고 S 값이 더 많은지 확인(bfs)하면 된다. 그런데 7명의 학생 조합을 찾을 때 중복된 조합을 생성하면 안된다. (ex, 학생 1 + 2, 학생 2 + 1은 같음) 따라서 5 X 5 배열을 숫자 0 ~ 24로 취급한 후, dfs의 s.. [백준] 7570. 줄 세우기 https://www.acmicpc.net/problem/7570 처음에 떠올렸던 풀이는 시간 초과로 불가능했다. 따라서 다른 방법을 떠올려야 하는데, 구글링을 통해 dp로 O(N)의 시간으로 풀 수 있는 방법을 발견했다. (https://mygumi.tistory.com/276#recentEntries)우선 숫자를 제일 앞이나 뒤로 이동시키는 최솟값 = (n - 가장 긴 연속된 숫자의 오름차순 수열의 길이)이다.그리고 가장 긴 연속된 숫자의 오름차순 수열의 길이를 찾기 위해선 다음 점화식이 사용된다.dp[n] = dp[n - 1] + 1혼자 힘으로 떠올리기 힘들고 이렇게 적어도 와닿지 않지만, 예시를 통해 직접 적어가며 생각하면 이해는 된다..import java.io.BufferedReader;imp.. 이전 1 2 3 4 ··· 18 다음
