배움 저장소

programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 처음 문제를 보고 단방향 그래프로 문제를 풀어야 하는 줄 알았다. 이긴 사람 기준으로 단방향 그래프를 그려보고, 진 사람 기준으로 단방향 그래프를 그려보고, 방문개수가 적은 순에서 중복이 생기지 않을 때까지 승부가 결정된다고 가정해보고 문제를 풀었다. 아주 멋진 삽질이었다. 정답은 Floyd Warshall 알고리즘을 사용해서 풀어야한다. 2차원 벡터를 사용해 노드 i에서 노드 j까지 가는 최소 거리를 구한다. 그래서 모든 노드 간 최단 이동 거리를 2차원 벡터에 저장하게 된다. 그..

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 문제를 보고 떠오른 풀이는 다익스트라. 다익스트라로 풀어야되는 건 알겠는데 구현 방법은 생각나지 않았다. GeeksForGeeks를 보는데 너무 길어서 programiz를 참고했다. www.programiz.com/dsa/dijkstra-algorithm Dijkstra's Algorithm It differs from the minimum spanning tree because the shortest distance between two ver..

programmers.co.kr/learn/courses/30/lessons/43236# 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 돌 사이 거리를 새로운 벡터로 만들어 문제를 풀려고 했는데 이분탐색을 적용할 방법이 떠오르지 않았다. 1. 풀이. 문제의 실마리는 돌 간 거리의 최소값을 이분탐색으로 찾아가는 것이다. 이 때 이분탐색의 기준은 돌 간 거리가 아니라 제거된 돌 개수이다. 찾는 값과 기준이 되는 값이 다르기 때문에 문제 해결이 더 어렵고, 다른 사람의 해답을 처음 봤을 때 뭔지 이해..

programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 하루 종일 붙들고 있었던 문제. 변수 타입을 int로 놓고 풀어서 삽질을 했다. long long int 타입을 사용해야 했다. while Loop를 돌면서 n과 비교하는 값인 pass도 long long 타입으로 설정해주어야 문제가 풀린다. long long 타입이 나올 때는 모든 변수를 long long으로 바꾸고 여유가 있으면 int에 맞는 값들은 바꾸어주는 것이 편할 것..

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 최소신장트리를 확인할 수 있는 알고리즘을 사용하여야 한다. 크루스칼 알고리즘을 사용하여 풀었다. GeeksForGeeks의 코드는 복잡해서 www.programiz.com/dsa/kruskal-algorithm를 참고했다. int find_Root(vector &root, int i){ if(root.at(i)==i){ return i; } return find_Root(root, root.at(i)); } bool compare(vector a, vector b){ ret..

programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 간단하게 문제를 풀 수 있는 아이디어는 자동차를 빨리 진입한 순서대로 정렬하는데서 부터 시작한다. 그 후 첫 자동차와 두 번째 자동차가 공유하고 있는 도로를 업데이트하는 것이 문제풀이의 핵심이다. int solution(vector routes) { sort(routes.begin(), routes.end()); int answer = 1; // 공유하고 있는 도로의 시작 지점 int common_begin = routes[0][0]; // 공유하고 있는 도로의 끝 지점 int c..

programmers.co.kr/learn/courses/30/lessons/42885# 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 문제 조건을 제대로 읽지 않아 삽질 한 문제. vector을 따로 만들어 사용 여부를 체크하다가 포기하고 3명이상 탈 경우를 고려해서 , 힙을 이용하여 풀었다. 문제만 제대로 읽었으면 Leetcode에서 유명한 twoSum 문제와 풀이방법이 같았음을 알 수 있었는데 ..

programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 레벨 2라고 되어있지만 체감은 훨씬 어려웠던 문제. 문자를 조이스틱의 최소한의 움직임으로 출력하라는 문제를 읽고 막막했다. 조이스틱이 움직이는 걸 일일이 세는 것도 생각해야 하는데, 최소한의 움직임까지 고려하라니. 일단 간단한 사례를 직접 실행해보고 문제를 풀려고 하는 편이라 머리가 아팠다. 갓글 검색 덕분에 아이디어를 얻었다. 그 중에 A에서 출발할지 Z..