문제 링크 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 전형적인 크루스칼 + 유니온파인드 문제다. 최소신장트리(MST)를 만들고 간선에 대해서 모든 비용을 합한다. // cmp 함수 크루스칼 알고리즘을 이용하기 위해 간선(비용)에 대해서 오름차순 정렬한다. // find_root 함수 root 찾는 함수다. 1) root가 지금 나라면 바로 리턴 2) 아니면 나의 부모로 재귀로 호출 // solution 함수 map을 이용해 연결됨을 이용했다(어차피 정점에 대해서 중복하지 않으므로) 1) init - 각 정점은 자신을 루트로 지정 2) MST가 만들어질 때까지 반복문을 돌린다(MST는 간선의 수와 ..
문제 링크 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 풀이 이분탐색 문제였다.(구글링해서 앎) // 요약 1) 처음에 최대값, 최소값을 구한다. 2) 최소값이 최대값과 같아질 때까지 반복문을 돈다. 중간값은 (최소값+최대값)이 홀수일 때는 2로 나누고 +1, 짝수일 때는 2로만 나눈 값이다 (가능한 최대값을 기준으로 진행) (stones의 원소 - 중간값)이 음수가 연속으로 K번 이상으로 나올 때 최대값을 중간값으로 갱신 (stones의 원소 - 중간값)이 음수가 연속으로 K번 미만 나올 때, 최소값을 중간값으로 갱신 대신, 최대값을 갱신할 때는 불가능했던 값이므로 중간값-1로 갱신 해준다. 3) answer에 최소값..
문제 링크 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 �� programmers.co.kr 풀이 재귀 DFS로 풀었다. // check_equal 함수 불량 사용자인지 판별하는 함수다. '*'에 대한 처리를 한다. // solution 함수 banned_id가 각각 어떤 것에 해당되는지 미리 "vv" vector 컨테이너에 담는다. "vv" 컨테이너는 user_id의 인덱스로 담는다.(중복 검사하는데 string보다 정수 하나 비교하는게 더 간편하기 때문에) 그리고 DFS 진행한다. // dfs 함수 중복을 제거하기 위해 을 사용하였고 재..
문제 링크 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이 범위 검사, 방문 이력 검사 함수와 x, y는 row, column으로 대조하여 풀었다. // Node 구조체 row, column의 int 타입을 가지며 1)생성자와 2)복사 생성자, 3)비교 연산자 오버로딩, 4)대입 연산자 오버로딩을 정의하여 다른 외부에서 편하게 사용하였다.(참고로 Java에서는 this가 참조자고 C++에서는 this가 포인터라는 것을 일깨워줌) // check_range 함수 범위 체크 함수. size를 받아 범위를 초과하는지 체크한다. // check_visit 함수 방문 이력 체크 함수. tuple을 모아놓은 vector 컨테이너를 방문 이력으로 참조자를 사용하여 갱신(push_back)되도록 한..
문제 링크 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 풀이 주어진 문제가 구하는 것은 "최대 승점"이다. A팀의 점수보다 큰 B팀의 점수 중에서 최소 값으로 1경기씩 나간 것이 "최대 승점"이다. 그래서 sort로 정렬해서 할까하다가 priority_queue에 넣고 (넣은 방향 기준)내림차순 정렬로 하나씩 빼면서 승점을 올렸다. // 요약 1) 우선순위 큐에 push 2) 승점 추가(A팀의 점수보다 큰 B팀의 점수 중 최소 값을 결정) 반복문(B팀원의 수가 없을 때까지) { A팀원 숫..
문제 링크 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 전달되지 않는 범위를 ranges 컨테이너에 담아서 최소 개수를 리턴하여 풀었다. 최소 개수만을 리턴하는 문제이므로 전달되지 않는 범위(vector 컨테이너 값) / 전달 범위(2w+1)가 최소 개수고 전달되지 않는 범위(vector 컨테이너 값) % 전달 범위(2w+1)로 나머지가 있다면 기지국 1개를 더 추가해준다. 더보기 #include #include using namespace std; // 아파트 개수 n, 사전 기..
문제 링크 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 풀이 자신의 점에서 모든 점까지의 최소 거리를 구하는 "다익스트라"문제다. 우선순위 큐를 이용해 풀었다. 우선순위 큐의 정렬방식이 디폴트로 오름차순으로 먼저 나오는 것이 최소값이지만 pair의 first로 기준하여 정렬하기 때문에 second에 cost(weight)값을 기준으로 정렬하기 위해서 struct cmp 구조체에서 () 연산자를 오버로딩(?)한다. 순서는 1) 초기화, 2) 다익스트라 로 진행한다. 1) 초기화 ve..
문제 링크 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 전위 순회(preorder), 후위 순회(postorder)를 리턴하는 문제다. Node 구조체를 만들어 order하였다. 1단계) node들을 vector 컨테이너에 담기 2단계) vector 컨테이너에 있는 node들을 y값으로 정렬(순회하면서 노드들을 추가하기 위해) 3단계) 이진트리 생성(y값은 미리 정렬했으니 x값만 신경썼다) - 부모의 x보다 작으면 left, 부모의 x보다 크면 right 4단계) order() - 전위 순회는 먼저 방..