문제 이해 단계 https://www.acmicpc.net/problem/1043 사람 수 N과 파티의 수 M이 주어진다. 그다음줄에는 진실을 아는 사람의 번호가 주어지는데, 지민이는 모든 파티를 참석하면서 거짓말을 쳐야 한다. 하지만 진실을 아는 사람이 있는 파티에서는 무조건 진실을 말해야 한다. 진실을 들은 사람이 거짓말을 듣거나, 거짓말을 들은 사람이 진실을 들으면 이는 실패한 것이다. 해당 조건에서 지민이가 거짓말을 칠 수 있는 파티의 최대 수를 구하는 문제 문제 접근 단계 문제의 제한조건부터 살펴보자. 사람의 수 N과 파티의 수 M이 모두 50까지 가능하다. 상당히 작은 숫자라서, 완전 탐색이나 원하는 대로 풀이가 가능할 것 같다. 문제의 특징 이 문제의 특징적인 점은, 옳고 그름을 판단하기 위..
암묵적 스레딩 암묵적 스레딩(implicit Threading) 스레딩의 생성과 관리 책임을 앱 개발자로부터 컴파일러와 실행시간 라이브러리에게 넘기는 것 앱 설계의 어려움을 극복하고 병행 및 병렬 앱 설계를 도와주는 방법 응용 프로그램 개발자가 병렬로 실행할 수 있는 스레드가 아닌 작업을 식별해야 함 작업은 일반적인 함수로 작성 런타임 라이브러리는 다대다 모델을 사용하여 별도의 스레드에 매핑 암묵적 스레딩 장점 개발자는 병렬 작업만 식별하면 된다. 라이브러리는 스레드 생성 및 관리에 대한 특정 세부사항을 결정 스레드 풀 다중 스레드 서버는 아직 여러 문제를 지님 스레드를 생성하는데 소요되는 시간 생성된 스레드가 단기 작업(곧 폐기될 스레드)이라면 더 문제가 됨 모든 요청마다 새 스레드를 만든다면, 동시 ..
Thread Thread 생성 using System; using System.Threading; // 추가해줘야 사용 가능 namespace ServerCore { public class Program { // 사용할 함수(쓰레드) static void MainThread() { Console.WriteLine("Create Thread"); } static void Main(string[] args) { //Thread 이름 = new Thread(함수 이름); Thread thread = new Thread(MainThread); thread.Start(); } } } using System.Threading을 추가해 줘야 사용이 가능하다. thread.Start()를 해야 만들어둔 thread가 ..
문제 이해 단계 https://www.acmicpc.net/problem/1238 N개의 마을에 연결된 M개의 단방향 도로가 존재한다. 각 도로에는 오고 가는 시간(비용)이 존재한다. N개의 마을 중 특정 마을 X로 왕복해야 하는데, 어느 마을에서 출발하는 것이 가장 시간이 오래 걸리는가? 그때의 소요 시간을 구하는 출력하는 문제 문제 접근 단계 문제 유형 유추 N개의 마을에 연결된 M개의 단방향 도로라는 말을 읽자마자 바로 그래프 탐색이 떠올랐다. 마을을 정점으로 치환하고, 단방향 도로를 단방향 간선으로 본다. 그리고 걸리는 시간을 각 간선의 가중치로 보면 완벽한 그래프 탐색 문제이다. 로직 어쨌든 이 학생들은 무조건 최단 거리로 오고 간다고 했다. 그래프 탐색에서 최단거리라고 하면 생각나는 것이 크루..
문제 이해 단계 https://www.acmicpc.net/problem/13905 섬 위에 N개의 집과 M개의 다리가 존재한다. 그리고 각 다리에는 무게 제한 K가 걸려있다. 입력으로 출발지와 목적지가 주어지는데, 혜빈이는 최대한 많은 금빼빼로를 들고 목적지까지 도착해야 한다. 각 다리에서 무게제한까지만 빼빼로를 들 수 있을 때 최대 몇 개까지 빼빼로를 옮길 수 있는가? 문제 접근 단계 제한사항부터 살펴보자. 존재하는 집의 수(N)는 100,000개, 다리의 수(M)는 300,000이다. 최대 10^5 * 10^5 = 10^10이므로, 완전탐색으로 하면 시간초과가 뜬다. 따라서 하나하나 비교하는 것은 안되고, 다른 방법이 필요하다. 그래프 탐색 결국엔 집과 집을 연결하는 것이 다리고, 그 다리에는 무게..
문제 이해 단계 https://www.acmicpc.net/problem/21941 소문자 문장 S가 주어지고, 문자열 리스트들이 주어진다. 각 문자열 리스트들은 각자 점수를 가지고 있다. 문장 S에서 모든 문자들을 지워야 하는데 아래 2가지 연산만 할 수 있다. 1. 문자열 리스트에 존재한다면 해당 부분을 지우고, 그 문자열만큼의 점수를 얻는다. 2. 문자 하나를 지우고 1점을 얻는다. 해당 연산을 통해 모든 문자를 지울 때, 얻을 수 있는 최댓값을 구하는 문제 문제 접근 단계 범위 파악 문제 조건부터 살펴보자. 문장 S는 최대 1000개까지, 문자열 리스트는 100개, 그리고 점수는 개당 10,000점까지 가능하다. 만약 문장의 길이가 1000이고, 문자열이 하나로 구성된, 개당 10,000점짜리가 ..
문제 이해 단계 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net NxN 크기의 맵에 M개의 바이러스를 놓으려고 한다. 바이러스는 맵에 ' 2 '라고 표시되어 있는 곳에 밖에 놓지 못한다. 바이러스는 1초당 상하좌우로 인접한 모든 빈칸(1이라고 적힌 칸을 제외)한 칸으로 퍼진다. M개의 바이러스를 배치하여 최소한의 시간으로 모든 맵에 바이러스를 퍼뜨릴 때, 이 최소 시간은? 만약 모든 맵에 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다. 문제 접근 단계 문..
문제 이해 단계 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net N명이 학생이 있고 그 학생들 사이에 M개의 친구 관계가 존재한다. 그리고 각각의 학생마다 친구비가 존재하는데, 친구 관계인 친구였다면 그중 하나에게만 지불하면 된다. 해당 조건으로 K원을 가지고 있을 때, N명 학생과 모두 친구를 맺을 수 있는 최소 비용을 구하시오. 만약 구할 수 없으면 "Oh no"를 출력한다..