쉽지않은 블로그

https://programmers.co.kr/learn/courses/30/lessons/81305 코딩테스트 연습 - 시험장 나누기 3 [12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1] [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]] 40 programmers.co.kr 문제 요약 시험장이 트리의 형태로 주어지고 각각 시험장에 몇 명에 인원들이 있는지 입력으로 주어진다 시험장을 k개의 그룹으로 묶은 후 k개의 그룹 중 가장 인원이 많은 그룹의 인원수의 최솟값을 구하라. 나의 풀이 이 문제를 처음 보자마자 이 문제가 생각났다. 사..

https://programmers.co.kr/learn/courses/30/lessons/81304 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 문제 요약 그래프 공간 속에서 일부 정점 중 함정이 있다 함정의 역할은 밟는 순간 해당 정점과 연결된 모든 간선을 뒤집힌다 모든 간선은 cost 가 다르다 시작 정점이 주어지고 도착 정점이 주어질 경우 최소비용을 계산하라 나의 풀이 이 문제는 꽤 오래 생각해야 풀 수 있었다. 이 문제는 언듯 보면 최단경로를 계산하는 여느 문제들과 다를 점이 없지만 함정 때문에 간선이 이동하면서 실시간으로 지도가 바뀐다. 갔던 곳을 다시 방문해도 된다(사실 다시 방문해야만 ..

https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 문제 요약 긴 길이의 배열이 있는 상황이다 배열의 특정 칸을 가리키는 커서라는 개념이 존재하고 커맨드 U, D, C, Z에 따라 커서를 이동하거나 , 배열의 특정 칸을 삭제, 복구하는 문제 문제 속 요구사항이 명확하다 나의 풀이 이 문제에서 가장 중요한 것은 입력 조건을 정확히 이해해야 한다. 그중에서도 "cmd..

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 문제 요약 5x5 책상이 존재하는 공간에 학생들은 2칸(상, 하, 좌, 우) 이내에 있을 ..

https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 문제 요약 숫자와 (0~9까지의 ) 영단어( ex | "zero" , "one"....)가 섞여있는 상태의 문자열로 주어질 경우 이를 숫자로 반환하여라 ex|. "03fiveseven8" => 03578 나의 풀이 C++ 보다는 문자열 처리에 편리한 javascript , python을 사용하고 replace와 같은 내장 함수를 사용했다. 길이가 50..

https://www.acmicpc.net/problem/13209 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사 www.acmicpc.net 나의 풀이 이 문제는 간단하게 말하면 트리구조의 자료구조에서 각 집 단안의 모든 노드 값의 합중 최댓값이 최소가 되게끔 집합을 묶었을 경우 집단내의 노드합이 최대값이 얼마인지를 묻는 문제이다. 이 문제는 10만개의 노드들을 어떻게 묶을지 선택을 해야 하는데 순차적으로 포함 여부를 모두 해보면 당연히 시간 초과가 날것이다 그리디나 DP 로 생각을 해보려고 했지만 하나를 선택함으로써 나머지가 ..

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 나의 풀이 사실 이문제는 이문제의 제작자인 데구리형님 에게 약간의 힌트를 예전에 들은적이 있어 그 기억을 더듬어보며 바로 문제를 풀수 있었다. 이 문제는 단방향인게 골때리는 점이다. 이 문제가 양방향이 였다면 면접장을 기준으로 다익스트라를 돌려보면 모든 마을의 최단거리를 저장하고 모든 마을의 최단거리중 가장 큰 값을 정답의 후보로 올려주면 되는문제였을것이다..

www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 나의 풀이 이 문제는 그리디 하게 풀 수 없다 어느 사원이 속하냐 안 속하냐는 다른 사원들의 값에도 효과를 미치기 때문에 방향을 고려하여 문제를 풀어야 된다 트리로 되어있는 문제이기때문에 맨 아래 리프 노드 푸터 루트 노드까지 쭉 뭔가 정보를 가지고 올려다 주면 위에서 판별할 수 있지 않을까 생각을 하였다 그리고 자료구조를 구성하자면 $dp[i][2]$ 를 로 생각을 해볼 수..