알고리즘
-
프로그래머스 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..
-
프로그래머스 Lv.3) 거스름돈알고리즘/프로그래머스 2020. 5. 29. 18:27
거스름돈 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5�� programmers.co.kr 풀이 정말정말정말정말 어려운 문제라고 생각한다 주관적으로. n이 100,000 화폐가 100이나 되는 문제기 때문에 dfs로는 풀 수 없다. 가능한 방법이 있다면 알고싶다.. 내가 알고있는 선에서는 풀 수 없었다. 그래서 DP로 풀어야한다는 생각이 들었는데 점화식이 감이 잡히지 않았다. 정말 오랫동안 생각하고 수식을 짜보려 해도 보이지 않았다. 그래서 다른 분의 해설을 보기로 했다. 거스름돈이 0원인 경우 경우의 수가 1이라는데, 문제 ..
-
프로그래머스 Lv.3) 멀리 뛰기알고리즘/프로그래머스 2020. 5. 29. 18:11
멀리 뛰기 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2�� programmers.co.kr 풀이 dp 문제이고, 피보나치 문제임을 바로 눈치챘다. 바로 1차원 배열을 만들어서 제출했는데, 1번 문제가 틀렸다고 나왔다. 피보나치 문제가 아닌가? 생각에 다시 문제를 꼼꼼히 봤으나 피보나치가 맞았다. 문제점을 모르겠어서 질문하기 탭을 확인했는데, n만큼 배열을 만들면 메모리 초과가 뜬다는 것이었다... 충격.. 최대 n이 고작 2000인데 메모리 초과가 난다.. 아무튼 그래서 변수 두개..
-
프로그래머스 Lv.3) 방문 길이알고리즘/프로그래머스 2020. 5. 29. 18:07
Summer/Winter Coding(~2018) 방문 길이 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이 간단한 시뮬레이션 문제였다. 로봇이 맵 정 중앙에서 시작해서 명령어에 따라 이동하는데, 맵 범위를 벗어나는 명령은 듣지 않는다는 조건이 있다. 움직이면서 처음 간 길이 몇 개인지 세는 문제다. 일단 제일먼저 한 것은 Pos 클래스를 만드는 것. 2차원 배열로 하면 귀찮고 한 라인에 코드가 길어지기 때문이다. 또한 URLD 명령에 따른 이동, Out of index 방지 메소드를 만들었다. 그리고 총 맵의 크기가 11인 것을 고려해보고 계산한 결과 14,xxx가 나오길래 그냥 4차원 배열로 visit 체크를 해주었다. (5,5에서 5,6으로 움직일 때 두 좌표를 이어주기 위해) ..