본문 바로가기

전체 글

[프로그래머스][Level1][해시][C++] 완주하지 못한 선수 - 컴도리돌이 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completio.. 더보기
[알고리즘] 깊이 우선 탐색(DFS, Depth, First Search) - 컴도리돌이 깊이 우선 탐색 너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색(DFS, depth, first search)은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다. 시간 복잡도 : O(V+E) DFS는 대체로 시작 정점에서 멀이 있는 정점을 찾을 때 적합하다. DFS는 최단 경로를 보장하지 않는다. DFS에 의해 생성된 검색 트리는 길고 좁은 편이며, 상대적으로 적은 메모리를 필요로 한다. 깊이 우선 탐색 관련 문제 [프로그래머스] [level2] 타.. 더보기
[프로그래머스][Level2][해시][C++] 전화번호 목록 - 컴도리돌이 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 tru.. 더보기
[C++][백준 1463][DP] 1로 만들기 - 컴도리돌이 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 코드 #include #include #include using namespace std; int n; int main(void) { cin >> n; vector v(n+1,0); for(long long i=2; i 더보기
[프로그래머스][Level3][그리디] 단속카메라 - 컴도리돌이 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도.. 더보기
[프로그래머스][Level3][크루스칼알고리즘][그리디][C++] 섬 연결하기 - 컴도리돌이 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 co.. 더보기
[알고리즘] 너비 우선 탐색(BFS, Breadth,First Search) - 컴도리돌이 너비 우선 탐색 너비 우선 탐색(BFS, Breadth, First Search)은 시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성된다. 그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다. 다음에 나오는 그림을 보면서 BFS 동작에 대해 짐작하면 좋다. 시간 복잡도 : O(V+E) BFS는 시작 정점에서 가까운 정점을 찾는데 적합하다. BFS에서 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장한다. BFS는 현재 경계에 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며 많은 메모리를 필요로 합니다. 너비 우선 탐색 관련 문제 [프로그래머스] 2021.08.10 - [컴도리돌이 전공 공부/C++] .. 더보기
[프로그래머스][Level3][힙][C++] 디스크 컨트롤러 - 컴도리돌이 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문.. 더보기
728x90

티스토리툴바