프로그래머스_가장 먼 노드
https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 해당 문제는 그래프 내에서 정점 1로부터 가장 멀리 있는 노드들의 개수를 구하는 문제였다. 나는 BFS를 통해 탐색하면서 가장 멀리 있는 노드들의 수를 계산하는 방식으로 처리하였다. 이 때, edge들이 양방향이라는 문제 조건에 맞춰 반대 방향의 edge들도 추가해주었다. 그리고 pair를 활용해 현재 방문중인 index와 1로부터의 거리를 함께 queue에 저장하여 처리하여서 손쉽게 해결할 수 있었다. (해당 문제..
프로그래머스_여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 | 프로그래머스 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 문제 자체는 dfs로 경로를 탐색하며 전개하면 되는데, 알파벳 정렬 순으로 진행되어야 하기에 정렬이 필요하다. 그런데, 문제 조건에서 애매한 부분이 있는데 ["ICN", "BOO"], ["ICN", "BOO"] 와 같이 동일한 티켓이 두번 주어졌을 경우에 어떻게 처리해야 하는가 이다. 예제 테스트 케이스에서는 동일 티켓을 제외하고 처리하는게 맞다고 처리되는데 실제 채점..
프로그래머스_ 정수 삼각형
https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 | 프로그래머스 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 삼각형을 타고 내려오면서 가장 큰 경로 값을 가져올 경우를 찾는 문제였다. 기본적인 DP로, 이전 경로에서 가장 큰 값에다 현재 경로 중 가장 큰 값을 더해주는 방식으로 경로를 확장해나가면서 해결할 수 있었다. 단, 삼각형의 둘레변 부분에서는 무조건 둘레변에서만 내려올 수 있으므로 이 부분들은 예외적으로 따로 처리해줬다. #include #include #include using namespace std; int solu..
프로그래머스_단속카메라
https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 | 프로그래머스 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 처음 풀이를 생각했을 때는 3 가지 경우를 생각했었다. 범위 내에 감싸고 있을 경우, 최소 지점과 만날 경우, 최대 지점과 만날 경우 저런 식으로 3 가지 경우를 생각하여 코드를 구현하였는데 계속 틀렸었다. 생각해보니, 저런식으로 bound를 줄여나가면 예전에 줄였던 경우에서 커버가 가능한 경우가 있을 수 있었다(말이 굉장히 어색하고 어려운데, 어쨋든 Routes간의 순서에 따라 값이 달라져버리게 될 수 있었다는 뜻이다). 밑의 코드는 처음 생각했던 ..
