알고리즘/프로그래머스
-
프로그래머스 Lv.3) 기지국 설치알고리즘/프로그래머스 2020. 6. 1. 17:48
Summer/Winter Coding(~2018) 기지국 설치 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 두번의 수정을 거쳤고, 푸는데 20분? 30분?정도 걸린 것 같다. 우선, 문제의 조건에 N이 2억 이하의 자연수 임을 보고 배열은 안된다는 판단을 내렸다. 된다 하더라도 효율이 안좋을 것이기 때문에 사용을 안하려고 마음먹었다. 다음으로 stations 배열은 오름차순으로 정렬되어 있다는 것을 보고, 이전에 설치된 5G망과 현재 설치된 5G망 사이에 커버하지 못한 아파트 세대..
-
프로그래머스 Lv.3) 숫자 게임알고리즘/프로그래머스 2020. 6. 1. 17:27
Summer/Winter Coding(~2018) 숫자 게임 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 � programmers.co.kr 풀이 처음에 문제가 쉽다고 생각하고 대충 풀었을 때, 30점 정도 나왔다. 처음 풀고 한 다섯시간 지나서 다시 풀기 시작했는데, 같이 공부하는 형이 풀어던 문제였고, B 배열이 정렬이 안되어 있다는 것을 알았다. ( 물론 혼자 풀었어도 눈치 챘을거다 ^^) 아무튼, 배열 정렬만 해주니까 바로 70점이 되었고, 나머지 30점이 시간 초과였다. 다시 수정하기가 귀찮아서, LinkedLis..
-
프로그래머스 Lv.3) 배달알고리즘/프로그래머스 2020. 5. 31. 23:03
배달 코딩테스트 연습 - 배달 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 풀이 문제를 보고 많은 생각이 스쳐 지나갔다. MST가 먼저 떠올랐는데, 모든 경로를 잇는 것이 중요한 문제가 아니기 때문에 아니라고 생각했다. 다음은, 최단 거리 알고리즘이었다. 다익스트라(dijkstra) 이름이 기억나지 않았지만, 이 로직이 떠올랐다. 하지만, 처음에 풀었을 때는 edge를 따로 저장하지 않고, 주어진 road만 돌면서 우선순위 큐에 저장하고 최소 비용으로 잘 잇는다면 가능하지 않을까 싶었다. 결과는 40점, ..
-
프로그래머스 Lv.3) N-Queen알고리즘/프로그래머스 2020. 5. 31. 22:37
N-Queen 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 풀이 체스 규칙을 알고있는데, 처음 코드를 짤 때 전체 대각선을 확인하지 않아서 한번의 수정을 거쳐 풀었다. 처음에는 1차원 배열인 visit을 남겨 각 column마다 방문 여부만 저장하고, 방문하지 않은 곳과 바로 위의 퀸과 위치 비교만 했다. 위치 비교는 좌상단, 상단, 우상단 세 부분만 체크를 했고, 결과적으로 40점이 나왔다. 행 = 세로, column 열 = 가로, row 틀렸다는 것을 확인하고 나서야, 대각선 확인에 대해..
-
프로그래머스 Lv.3) 하노이의 탑알고리즘/프로그래머스 2020. 5. 31. 22:07
하노이의 탑 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대�� programmers.co.kr 풀이 문제에서 n이 15이하로 주어졌기 때문에, 메소드 재귀 호출을 이용해 문제를 풀어야겠다는 생각을 했다. 그리고, 문제 조건을 쭉 써본 결과 n에 대해 최소 이동 횟수는 2^n -1이 된다는 것을 파악했다. 우선, 최소 이동 횟수만큼 result 배열을 만들어 주었다. ( 0 : 원판을 가져온 기둥, 1 : 원판을 옮긴 기둥을 저장해야하기 때문에 2차원 배열) 그리고 이리저리 삽질을 한 것 같다. 재귀로 풀었지만 몇개 ..
-
프로그래머스 Lv.3) 최고의 집합알고리즘/프로그래머스 2020. 5. 30. 18:14
최고의 집합 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족 programmers.co.kr 풀이 중복 집합이라는 조건 때문에 비교적 간단한 문제였다. 문제는 3가지 조건으로 정리할 수 있다. 1. 입력받은 자연수 n개로 이루어진 중복 집합(Answer)을 구한다. 2. Answer의 각 원소의 합 : 입력받은 S가 되어야 한다. 3. 각 원소의 곱(즉 전체 원소의 곱)이 모든 경우의 수 중 최대가 되야한다. 이 세 조건을 충족시키는 중복 집합을 구하는 것이다. Answer를 구할 수 없을 때는, [-1]을 리턴해야하..
-
프로그래머스 Lv.3) 야근 지수알고리즘/프로그래머스 2020. 5. 30. 17:26
야근 지수 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 N : 야근을 해야하는 총 시간 ~> 1시간 마다 한 작업에 대해 -1을 해줄 수 있음 works[] : 각 작업마다 해야하는 총 일의 양 야근 피로도 = 각 work를 시작하는 시점 + (work의 남은 작업량)^2 이 문제는 위의 세 가지로 정리할 수 있다. 즉 각 작업마다 작업량이 많을 수록 야근 피로도가 쌓이기 때문에, 제곱이 되어 커지는 수를 최대한 줄여주어야하는 문제이다. 그렇다면 여기서 생각해야하는 것은, 최대한 고르게..
-
프로그래머스 Lv.3) 줄 서는 방법알고리즘/프로그래머스 2020. 5. 30. 17:14
줄 서는 방법 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 풀이 오랜만에 문제가 잘 풀리는 날이다. 문제를 보고 규칙을 찾기위해 머리를 굴렸다. 그러면서 생각한게, 답이 될 앞쪽 인덱스부터 몇 번째 순서까지 어떠한 수가 오는지 규칙을 찾았다. 우선 예제의 n이 너무 작다고 생각해서, n=5 일 때를 가정하고 생각했다. n=5 일때는 answer 배열의 크기는 5가 되고, 0~4 idx 까지 알맞은 순서를 찾아야 한다. 우선 규칙에 따라 모든 순열을 적어보고 규칙을 찾았다. 이 문제는 Fact..