본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm143

[DFS] 경주로 건설 - 2020 카카오 인턴십 해결 방법 DP와 DFS를 병행하여 해결하였으며, DP없이 DFS로만 해결하면 시간초과가 나온다. 이 문제의 경우에는 나아가는 방향이 직진인지 코너인지를 판별하여 100 또는 600(코너 비용 500추가)을 더해야 한다. 이를 위해서는 다음 DFS 재귀함수를 반복할 때 현재의 진행 방향이 전달되어야 한다. 이 때, 동서남북을 일일이 가려낼 필요는 없으며 가로(동서) 방향과 세로(남북) 방향만 알면 된다. 연산시간 절약을 위해 현재 dfs 재귀에서 cost가 answer값을 넘는다면 더 이상 dfs 재귀를 수행하지 않도록 했다. 그리고 진행 칸에 대한 최소 비용이 갱신되지 않았다면 이 역시 더 이상 dfs 재귀를 수행하지 않도록 하되, 직선 도로와 코너 건설 비용의 차이인 500이 있을 수 있다는 사실을 .. 2022. 5. 11.
[구간합] 쿠키 구입 - Summer/Winter Coding(~2018) 문제를 해결한 후에도 다른 풀이법에 대한 호기심이 생겨서 찾아보았다. 내 풀이법도 간단하다고 생각하지만 이 블로그에 설명된 풀이법이 더 간단해보이니 궁금한 분들은 참고하길 바란다. https://hwan-shell.tistory.com/308 이제 내 풀이법을 소개한다. 해결 방법 cookie 벡터에 대한 누적합 배열 cookie_acc을 만들어 놓았기 때문에 구간합 공식을 쉽게 구할 수 있었다. 예를 들어, 구간 [a, b]에 대한 구간합은 cookie_acc[b]-cookie_acc[a-1]이다. 이 문제에서는 a 2022. 5. 1.
[시뮬레이션] 스킬트리 - Summer/Winter Coding(~2018) 해결 방법 먼저 스킬트리의 순서를 map에 저장해두고, 뒤에 나와야 할 스킬이 앞에 나왔다면 그 스킬트리는 잘못 됐다고 판단하면 된다. 소스 코드 #include #include using namespace std; map m; int solution(string skill, vector skill_trees) { int answer = 0; for(int i=0;i 2022. 4. 29.
[그리디] 기지국 설치 - Summer/Winter Coding(~2018) 해결 방법 아파트의 개수 N의 범위는 2억까지이기 때문에 O(N) 이상의 시간복잡도로 풀면 시간초과가 나올 것이다. 그래서 범위가 1만까지인 stations 벡터를 이용해서 해결하였다. 문제의 접근법은 다음과 같다. Step 1) 전파가 닿지 않는 연속된 아파트의 길이들을 벡터에 저장한다. - 예를 들어, 아래 예제의 경우에는 1~2, 6~9 구역에 전파가 닿지 않으므로 2, 4를 벡터에 저장하면 된다. Step 2) 벡터에 저장된 거리들을 하나씩 꺼내어 각 거리마다 설치할 수 있는 최소 기지국의 수를 합산한다. - 거리 n에 설치할 수 있는 최소 기지국의 수의 공식은 ceil((float)n/(2*w+1)) (ceil()은 올림 함수)가 된다. 소스 코드 #include #include using na.. 2022. 4. 26.
[그리디] 숫자 게임 - Summer/Winter Coding(~2018) 해결 방법 A, B 벡터를 각각 오름차순으로 정렬해서 낮은 숫자를 가진 사람들부터 출전시켜가며, A팀에서 숫자가 낮은 사람들은 반드시 매칭이 이루어지도록 하는 식으로 접근하면 쉽게 해결할 수 있다. A의 n번째 팀원을 an이라고 하고, B의 n번째 팀원을 bn이라고 하자. A팀과 B팀의 각 첫 번째 사람인 a1, b1부터 출전시켜서 a1의 숫자가 더 크다면, b1는 A팀의 모든 뒷 사람들을 이길 수 없는 상태임을 알 수 있다. 왜냐하면 A를 오름차순으로 정렬해놓았기 때문이다. 그래서 B팀의 다음 사람(b2)을 출전시켜서 a1와 비교하면 된다. 만약에 b1의 숫자가 더 크다면 B팀의 승점을 1만큼 카운트하고 A팀과 B팀의 다음 사람을 출전시키면 된다. 그리고 매칭에 시도한 B의 팀원은 더 이상 매칭할 일이.. 2022. 4. 24.
[수학] 멀쩡한 사각형 - Summer/Winter Coding(2019) 해결 방법 일차 함수의 특성을 이용하여 문제를 해결했다. 입출력 예 #1에서 좌측 하단 꼭짓점을 원점이라고 했을 때, 일차 함수식은 다음과 같다. y=-(h/w)x+h x축으로 좌표를 1씩 옮겨가며 선에 걸치는 사각형들을 제거해주는 방법을 사용하면 문제를 해결할 수 있다. 이제, 좌측에 있는 사각형부터 제거해보자. 먼저 x=0일 때 y=12이고, x=1일 때 y=10.5다. 이 경우에는 y의 좌표가 10~12 사이에 있는 사각형 2개가 제거된다. 그 다음에 x=1일 때 y=10.5이고, x=2일 때 y=9다. 이 경우에는 y의 좌표가 9~11 사이에 있는 사각형 2개가 제거된다. 이런식으로 계속 두 좌표를 비교하여 사각형을 제거해나가면 되는데, 이 때 왼쪽 좌표의 y값은 올림을 하고 오른쪽 좌표의 y값은.. 2022. 4. 22.
[BFS] 배달 - Summer/Winter Coding(~2018) 제대로 동작하도록 구현하는건 쉽지만 시간 초과에 막힐 수 있는 문제다. 이 문제는 최대한 효율적으로 구현해야 한다. 해결 방법 필자는 BFS로 해결했다. Step1) 이 문제는 인접한 두 노드를 연결하는 간선이 여러개가 있을 수 있다. 그래서 인접한 두 노드를 연결하는 최소 비용의 간선들을 저장해둬야 한다. Step2) 노드와 간선을 연결한다. Step3) BFS를 수행하면서 1번 노드(마을)로부터의 최소 비용(시간)이 갱신된 노드만 Queue에 넣는다. 참고로, 갱신된 노드의 비용이 K를 넘어가는 경우에는 굳이 Queue에 넣지 않도록 처리하면 처리시간을 단축할 수 있다. Step4) 1번 노드로부터의 최소 비용이 K 이하인 노드를 모두 카운트한다. 단, 1번 노드는 당연히 카운트 해야하고, BFS를 .. 2022. 4. 15.
[동적계획법] 스티커 모으기(2) - Summer/Winter Coding(~2018) 서로 인접한 요소를 선택하지 않으면서 합이 최댓값이 되는 요소들을 선택하는 유형의 문제다. 프로그래머즈의 도둑질 문제와 동일한 유형의 문제다. 물론 점화식도 같다. https://kimcoder.tistory.com/92 [동적계획법, 난이도 중상] 프로그래머즈, 도둑질 Programmers의 문제들은 난이도별로 다섯 레벨로 나뉘는데, 그 중 Level 4에 속하는 난이도 있는 문제이다. 그래도 백준에서 DP를 50문제 넘게 푼 짬이 있어서 그런지 크게 어렵지는 않았다. 집이 일렬 kimcoder.tistory.com 차이점이 있다면, 도둑질 문제는 입력 배열의 크기가 3 이상으로 정해져 있고, 이 문제는 입력 배열의 크기가 1, 2일 수도 있다는 것이다. 그래서 sticker.size() 값이 1 또는.. 2022. 4. 12.
[그리디] 튜플 - 2019 카카오 개발자 겨울 인턴십 해결 방법 Step1) 문자열을 파싱하여 각 집합을 벡터 v로 만들고, 벡터 v들로 이루어진 2차원 벡터 allv를 구성한다. Step2) allv의 v들을 크기가 작은 순으로 정렬한다. allv를 구성하는 벡터들의 크기는 순서대로 1, 2, 3, ..., allv.size()가 될 것이다. Step3) allv의 마지막 벡터를 이용하여 각 요소의 개수를 카운트 한다. Step4) allv의 n번째 벡터에서 카운트(element_cnt)가 0이 아닌 요소를 answer의 n번째 요소로 넣고, 해당 요소의 카운트를 1 감소시키는 작업을 allv의 첫 번째 벡터부터 수행한다. Step4 예시 {{1}, {2, 1}, {1, 2, 2}, {4, 1, 2, 2}} -> 요소를 카운트해보면 1은 1개, 2는 2개.. 2022. 4. 10.

티스토리툴바