문제 링크 코딩테스트 연습 - 방문 길이 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() - 전위 순회는 먼저 방..
문제 링크 코딩테스트 연습 - GPS edge_list [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] programmers.co.kr 풀이 어렵다... 풀이를 봐도 처음에 이해하기 어려웠다. 주석으로 써놓긴 했지만 DP 문제로서 풀이는 최소 오류 수정값을 넣으면서 진행해간다. // 변수들 1) adj[201]; 이 변수는 한 점의 연결된 정점들을 모아둔 vector 컨테이너라고 보면된다. 201개로 설정한 이유는 정점은 1~n이므로 넘버링 되어 있기 때문이다. ex) adj[0] = 1, adj[0] = 2 라면 0에 연결된 점은 1과 2가 있다. 물론 문제에서는 양방향이기 때문에 adj[1] = 0, ad..
문제 링크 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 풀이 효율성 문제라길래 해설을 보았고 union-find 알고리즘으로 푸는 문제였다. 시간 복잡도는 O(nlogN)으로 풀어야 효율성 테스트 케이스가 풀린다고 한다. // findRoom() --- 전역 변수로 map을 선언하는 대신 참조자로 매개변수로 받아서 구현하였다. if(요구하는 방번호는 배정해도 된다) map에 요구하는 방 번호는 다음 방 번호 저장한다.(다음 방 번호를 재귀로 찾을 수 있도록) 배정 안된 것의 번호를 리턴 else(이미 배정된 것이 있다) 배정 안된 것의 번호를 찾아서 저장 map에는 배정 안된 것의 다음 번호를 저장(나중에 또 물어보면 바로 찾을 수 있도록, 순차적으로X) 배정 안된 것의 번호를 리턴..
문제 링크 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 블록 이동하기를 풀어서 그런지 비슷하게 풀었다.(다른 cost에 대해 중복 허용만 체킹) // Car 구조체 행, 열, 방향, 비용 // 함수 isRange() : 보드 범..