문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 역 인접리스트를 활용한 데이크스트라 문제 첫번째 접근법 소프티어 8차를 보고난 후 1번문제와 비슷하다 판단하여 그리디하게 접근함… 각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함 두번째 접근법 제일 처음 떠올렸던 접근인데 각 면접장으로부터 다른 정점들까지의 최단경로를 구함으로써 한번..

문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acm..

Concept 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 아래와 같은 수열이 있을 때 오름차순으로 정렬된 부분 수열은 1,3,5 1,3,4 3,5 1,2,4 등과 같이 존재하며, 해당 수열에서 최장 증가 부분 수열은 3 Feature 이러한 LIS의 길이를 구하는 방법 중 단순한 접근법은 Brute-Force방법으로 수열의 총 길이가 K라고 가정할 때 1개 이상의 원소를 가지는 모든 부분수열의 경우의 수는 2^K개로 모든 부분 수열의 오름차순 정렬을 확인하는 것은 시간이 매우 오래 걸린다. LIS의 길이를 구하는 최적 방법에는 2가지가 있다. 다이나믹 프로그..

문제 https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 풀이 역시 구현+시뮬레이션 답게 장황한 문제의 지문에 조금 당황했지만.. 이해하고 나면 막상 수월하게 풀이가 가능했던 문제 해당 문제에서 핵심 로직 : 공격에 관한 상태배열 관리 입력의 방향은 Switch~case문으로 처리. 시작 좌표 큐에 추가. while문을 수행하면서 큐에서 꺼낸 좌표에 대해 로직 수행. 큐에서 꺼낸 좌표의 상태값이 0이라면(넘어져있는 경우) contin..