본문 바로가기

알고리즘

 (179)
[프로그래머스] 단속카메라(Java, Greedy, 사고력, Lv3) programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr ## 접근방법 그리디 문제는 항상 코드는 단순하지만, 생각해내기가 쉽지 않다. 이 문제는 최소의 단속카메라를 통해서, 모든 운전자들을 단속할 수 있어야 한다. 어떤 운전자부터 카메라를 배치해야할까? 단속이 안된 운전자중에서, 가장 도착 거리가 작은 운전자를 확인해야 한다. 가장 도착 거리가 작은 운전자도 카메라에 찍혀야 되므로 카메라는 두는 것은 자명하며, 가장 도착 거리가 작은 운전자부터 확인해야 다른 운전자들이 해당 단속카메라로 단속이 된다면, 카메라를 불필요하게 설치할 일이 ..
[프로그래머스] 네트워크(Lv3, BFS/DFS, 시간복잡도, Java, 정답, 코드) programmers.co.kr/learn/courses/30/lessons/43162?language=java 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr ## 접근방법 같은 네트워크들끼리는 무조건 연결되어 있다는 점을 착안해서 문제를 풀어보자. 어떤 컴퓨터에서 탐색을 시작하면, 연결된 컴퓨터들을 모두 찾을 수 있다. 완전 탐색 기법인, BFS와 DFS를 둘다 가능하며, 시간복잡도는 O(N * N)이다. 완전 탐색 시에, 네트워크가 정해진 컴퓨터는 방문하지 않도록 체크한다. 생각보다 간단한 문제이므..
[프로그래머스] 광고 삽입(Java, Lv3, 카카오, 누적합) programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr ## 접근방법 광고를 삽입해서, 가장 많은 시간이 누적되도록 하는 구간을 찾아야 한다. 시청자들의 출입에 관한 로그 정보들이 있다. 출입에 관한 로그 정보들을 이용해서, 1초동안 누적된 시간들을 구할 수 있다. 만약에 1초에 시청을 시작하고, 10초에 시청을 종료한다고 생각해보자. 1초의 순간에 한 명이 ..
[프로그래머스] 단어 변환(Level 3, JAVA, 왜 BFS를 사용해야 하나?, BFS/DFS, 깊이 탐색, 너비 탐색) programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr ## 문제접근 시작 단어에서 출발하여서 타겟 단어로 만들어야 한다. 그 과정은 최소가 되어야 한다. 최소가 되기 위해선, 최적의 단어 순서를 찾는 것뿐만 아니라, 중복해서 단어를 방문해서는 절대 안된다. 단어의 중복 방문은 무한 루프에 빠지게 할 수 있다. 최적의 단어 순서를 찾기 위해서 완전 탐색을 이용하고 중복된 단어를 방문하지 ..
[Lowest Common Ancestor of a Binary Tree] 공통 조상 찾기(LeetCode, Java, Recursion, Iteration) 공통 조상 찾기는 트리 문제에서 유명하다. 릿코드에 기록되어 있는 문제기도 하다. 구글링해서 나오는 코드들이 복잡하거나 좋지 않아 보여서 직접 찾거나 작성한 좋은 코드들을 소개하려고 한다. 위의 문제를 번역하면 간단하다. 재귀함수는 정의가 가장 중요하다. getCount라는 함수는 P 혹은 Q의 개수를 의미한다. 어떤 노드에서, 왼쪽 트리의 P 혹은 Q의 개수와 오른쪽 트리의 P 혹은 Q의 개수의 합은 현재 노드를 포함한 P와 Q의 노드의 개수와 같다. P와 Q의 개수가 최초로 2가 되는 곳이 공통조상이라고 볼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 /** * Defi..
플로이드 워셜 알고리즘(그래프 이론, JAVA, V^3, 다이나믹 프로그래밍) ## 기본 정의 및 증명 플로이드 워셜 알고리즘은 시간복잡도가 N^3이고, 공간복잡도는 N^2의 알고리즘이다. 알고리즘 구현이나 설명은 매우 간단하다. 플로이드 워셜 알고리즘의 핵심은 다이나믹 프로그래밍이다. 임의의 두 노드가 있다고 가정해보자, 두 노드는 i와 j라고 하자. 두 노드의 최단 거리는 여러 점들을 경유할 수 있다. 이 점에 착안해서, 다이나믹 프로그래밍이 구현된다. i와 j사이에 k번 노드까지 경유할 수 있을 때 최소 거리에 대한 공식이다. k - 1번 노드까지 얻어진 거리 혹은 신규로 k번째 노드를 추가해서 얻을 수 있는 거리가 최소 거리가 될 것이다. 추가적으로 설명하자면, i와 j사이의 최단 거리에 k번째 노드가 들어갈 수 있는지 없는지가 핵심이다. 공간복잡도로 2차원 배열을 사용하면..
[LeetCode] 754. Reach a Number leetcode.com/problems/reach-a-number/ Reach a Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com ## 접근방법 이 문제를 전체 탐색을 한다고 생각하면, 2의 지수승이 되므로 전체 탐색은 무조건 TLE를 받는다고 생각하면 된다. 처음 순간에 +1, -1 이후에 +2, -2를 선택하는 과정을 쭉 생각해보면, 탐색해야 하는 노드의 수는 2 * 2 * 2 * 2...가 될 것이다. target만큼 접근하기 위해서, 어떻게..
TSP 외판원 문제 2-Opt, 3-Opt(TSP Problem) 2-Opt 및 TSP 기본 개념 외판원 문제는 NP-Hard 문제로 유명하다, 모든 경로를 확인할 경우 최선의 방법으로 메모이제이션과 비트마스크를 통해서 풀 수 있다. 하지만, 노드의 수가 증가하면 모든 경로를 방문하는 것은 불가능하게 된다. 따라서, 노드의 수가 엄청 많아질 경우에는 정확한 해를 구하는 것이 불가능해진다. 이 경우에 생각할 수 있는 것이, 지역 탐색 알고리즘인 2-Opt이다. 2-Opt를 사용하기전에 출발점에서 모든 노드를 거쳐서 출발점으로 돌아오는 임의의 경로를 구한다. 위의 그림을 떠올려 보자, 연결된 A와 B, C와 D를 잇는 방식을 변경해서 거리가 더 감소된다면, 해당 경로를 선택하는 것이 2-Opt의 기본이다. 2-Opt의 '2'는 2개의 연결된 선분을 변경한다는 의미이다. 이..

티스토리툴바