알고리즘 문제/Programmerse42 [Programmers] 타겟 넘버 문제 : https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 방식으로 탐색하면서 모든 인덱스의 숫자들을 더하거나 빼는 경우의 합을 구한다. 모든 numbers 를 탐색했을 때 합이 targetSum과 같다면 정답 +1을 해준다. 시간복잡도는 하나의 인덱스에 더하거나 빼는 경우, 두 번을 탐색하므로 O(2^N). N = |numbers| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84.cpp 2021. 8. 5. [programmers][2021카카오인턴십] 거리두기 확인하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/81302 BFS로 풀었다. 하나의 대기실을 탐색하면서 people 좌표를 찾으면 BFS를 돌린다. 탐색하면서 테이블을 만나면 계속 탐색, 파티션을 만나면 탐색 중지, 또다른 people을 만나면 거리두기 실패임을 알 수 있다. 만일 탐색하면서 3이상의 거리가 된다면 거리두기를 성공적으로 하고 있으므로 BFS 탐색을 중지해도 된다. 시간복잡도는 하나의 people 좌표에서 BFS를 돌리는데 people 좌표 탐색 O(NM). 한 번의 BFS 탐색시 O(NM)이 소요되므로 총 O((NM)^2). 하지만 거리두기 2 이상은 탐색할 필요가 없으므로 BFS 탐색 시간복잡도는 상하좌우 4방향으로 2번만 탐색하면 되.. 2021. 7. 30. [Programmers] 하노이의 탑 문제 : https://programmers.co.kr/learn/courses/30/lessons/12946 오랜만에 풀어보는 하노이의 탑. 재귀로 풀었다. A -> C로 N개의 원판을 옮긴다고 해보자. 가장 아래에 있는 원판을 제외한 N-1개의 원판은 커다란 덩어리로 보자. 먼저 N-1개의 원판을 하노이의탑 규칙에 어긋나지 않게 A -> B 위치로 옮긴다. 그 뒤, N 번째 원판을 A -> C로 옮긴다. 다시 N-1개의 원판을 N-2번째 원판과 그 외의 원판들로 보자. N-2 개의 원판들을 규칙에 어긋나지 않게 B -> A로 옮긴 후, N-1번째 원판을 B -> C로 옮긴다. 이를 반복하며 다시 N-2개의 원판들을 C로 옮긴다. // n개의 원판을 from -> to로 이동 fun hanoi(int .. 2021. 7. 6. [Programmers] 단속카메라 문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 그리디로 풀었다. 먼저 루트들을 시작위치를 기준으로 오름차순정렬한다. 변수를 만들어서 커버가능한 시작위치 종료위치(let, cover)를 저장한다. 루트들을 처음부터 탐색하면서 탐색 중인 루트(let, route)가 이전 가능한 카메라 위치로 커버가능한지 체크한다. 만약 route.시작위치 > cover.종료위치 이거나 route.종료위치 < cover.시작위치 라면 범위가 커버가 불가능하므로 카메라를 한 대 더 설치해야한다. 카메라 대수를 한 대 증가시키고 cover 변수를 현재 route 범위로 갱신한다. 이전 카메라로 커버가 가능하다면 현재 route 범위와 cover 범위의 교집합으로 c.. 2021. 6. 16. [Programmers] 섬 연결하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42861 오랜만에 푸는 최소신장트리문제~ 크루스칼 알고리즘으로 풀었다. 먼저 cost 오름차순으로 costs 배열을 정렬한다. costs 배열을 탐색하면서 Union-Find로 해당 간선을 연결하면 사이클이 생기는지 확인한다. 만일 두 정점의 부모노드가 같다면 연결하면 사이클이 생기기 때문에 해당 간선을 선택하지 않는다. 두 정점의 부모노드가 다르면 해당 간선을 연결해도 사이클이 생기지 않기 때문에 해당 간선을 선택하고 해당 간선의 비용을 정답에 더해준다. 시간복잡도는 간선들을 오름차순 정렬하는데 드는 시간인 O(ElogE) 소스코드 : https://github.com/fpdjsns/Algorithm/.. 2021. 6. 14. [Programmers][2020 카카오 인턴십] 보석 쇼핑 문제 : https://programmers.co.kr/learn/courses/30/lessons/67258 투포인터로 풀었다. gems를 돌면서 보석 종류 수를 구한다. 보석의 개수를 저장하는 cnts map을 하나 만든다. key = 보석이름, value = 보석 수. 그리고 탐색하면서 만난 보석들의 종류를 저장하는 set을 하나만든다. (let, exists) 투포인터의 오른쪽 인덱스(right)를 0부터 1씩 증가시키며 left 인덱스를 갱신한다. 탐색중인 보석의 수를 cnts 맵에 1더해서 갱신시킨다. exists set에 탐색한 보석을 추가한다. 정답가능한 배열의 크기를 최소화로 만들기 위해 left인덱스를 갱신한다. 만일 gems[left] 에 해당하는 보석의 개수(cnts 참고)가 1보다.. 2021. 6. 13. 이전 1 2 3 4 ··· 7 다음
