문제 링크 코딩테스트 연습 - 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) 배정 안된 것의 번호를 리턴..
문제 링크 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 풀이 감이 안잡혀 해설을 보고 풀었다. 시계, 반시계 이동때문에 감이 안잡혔는데 한 방향이 최적이였다. 순환을 직선화 시키는 법과 친구들을 모두 완전탐색(순열)하여 풀었다. // 요약 1) weak[0]+n을 push하고 weak[0]을 erase하여 순환하는 것을 직선화 시켰다. 2) 친구 수를 next_permutation으로 취약 위치가 순환할 때 전부 점검했다. 3) answer가 signed int이므로 -1값을 unsigned int로 비교할..
문제 링크 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스�� programmers.co.kr 풀이 stage 번호와 실패율의 pair 변수를 vector 컨테이너로 선언하였다. 그리고 오름차순으로 정렬 후 단계 수와 맞는 인원수를 second에 증가시킨 후 전체 totalPerson로 나눈 것을 second에 다시 넣어주었다. totalPerson은 계속 감소시켜주었다. 마지막에 실패율을 compare 비교함수를 정의하여 정렬하면 first값이 실패율에 따른 stage 번호이다. 더보기 #include #include #include #i..