문제 링크 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 문제가 한 노드에서 모든 노드의 최단 거리를 구하는 문제로 BFS로 바로 방문을 검사하며 구현하였다. // init 1. 큐 선언 2. 방문 배열 선언 3. 그래프(multimap) 선언 4. 1번 노드로부터 최단 거리 배열 선언 // init(Graph) 파라미터로 주어진 edge를 순회하면서 multimap에 양방향으로 추가한다. // process(BFS) 1. 먼저 1번 노드와 연결된 노드들을 큐에 push 2. push 한 노드들은 모두 방문 처리를 한다. 3. push 한 노드들은 1번 노드로부터 최단 거..
문제 링크 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 풀이 주어진 조건을 잘 봐야겠다는 생각이 드는 문제였다. [조건] 1. 주어진 항공권 모두 사용 2. 가능한 경로가 다수 개일 경우, 알파벳 순서가 앞서는 경로 조건 1은 깊이(depth)를 이용하여 모두 방문했다는 것을 인지했다. 조건 2는 미리 도착지에 대해 내림차순하여 마지막으로 갱신되는 것이 알파벳 순서가 앞서는 것으로 처리했다. ++ 그리고 만약에 중간에 경로가 불가능해지는 것에 대해서 탈출 키워드 '#'을 사용하여 return 되는 것이 '#'이라면 자신을 호출했..
문제 링크 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 재귀 DFS로 풀었다. // check_1_diff() - 문자가 하나만 다를 경우, true // dfs() 0. 탈출조건 만약, target의 문자열로 바뀌었을 경우는 들어간 깊이?(count)로 return 시켰다. 그리고 만약, string형의 visit 변수의 '0'이 없다면 모두 방문했다는 소리다. 따라서, 변환할 수 있을 때의 (최대 깊이+1 = 51)로 리턴시킨다. 1. init 깊이를 5..
문제 링크 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 카메라 위치는 차량의 진입 시점으로 하되, 1. 카메라 위치를 갱신(카메라 개수 일정) 2. 카메라 개수 추가(카메라 개수 증가) 이렇게 나누었고, 카메라 개수를 추가하는 것에 대한 임계값을 차량의 나간 시점으로 하였다. (반복문을 돌면서 카메라를 최소 개수로 설치해야 하므로) // init 나간 시점으로 오름차순 정렬 --- 나간 시점(임계값)이 작은 것부터 비교해야 하므로 임계값 -30001로 초기화(차량 진입 시점은 -30000 이상이므로) --- 반복문을 0부터 돌면서 처음에 카메라 개수를 추가하기 위함 // process 반복문(모든 차량에 ..
문제 링크 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 "처음에 어떻게 태우지?" 하다가 구명보트는 2명이 제한이라는 것을 발견하고 바로 풀었다. deque을 이용하여 pop_front()와 pop_back()을 유용하게 쓰며 진행 대신, 처음에 정렬에 대해서는 vector로 정렬하고 역방향 반복자를 이용해 내림차순으로 정렬하였다. (deque은 조회에 대해서는 느리다구 한다, 대신 앞, 뒤로 pop이나 push가 용이하다) // init 1. people 벡터 컨테이너를 ..
문제 링크 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 두 가지의 부분해가 존재한다. 1. 상, 하 커서를, 바뀔 알파벳이 디폴트 'A'에서 최소로 조작한다. 2. 좌, 우 커서를, 디폴트 'A'가 아닌 곳과의 거리가 최소로 조작한다. deque을 사용하여 pop_front()와 pop_back()을 사용하였다. // init 방향 결정을 위해서 'A'가 아닌 인덱스만 deque에 push dq가 빌 때까지 { 우 커서로 움직일 경우 거리(right)와 좌 커서로 움직일 경우 거리..
문제 링크 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 첫 번째 풀이로, 완전탐색으로 풀리나 해봤지만 역시나 시간초과가 걸렸다. 그리고 두 번째 풀이로, 최댓값을 골라서 같은지 비교했으나 테스트케이스 10번에서 시간이 초과된다. 세 번째 풀이는 제거할 개수 범위 내에 가장 앞 숫자보다 큰 숫자가 있는지 검사하는 방법이다. 예를 들어, 현재 인덱스는 5라면, 제거할 개수가 4개라면 [5]가 [6] ~ [9]까지 비교했을 때, 가장 큰 값인지 검사하면 된다. [6]~[9]까지 max_element로 찾았더니 테스트케이스 10번에서 시간이 초과된다. 중간에 찾으면 break; 로 시간을 줄여야 통과할 수 있다. 여기서, 반복문의 탈출 조건은 1. 제거할 개수가 0일 때 2. 제거할 ..