알고리즘
-
프로그래머스 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으로 움직일 때 두 좌표를 이어주기 위해) ..
-
프로그래머스 Lv.3) 리틀 프렌즈 사천성알고리즘/프로그래머스 카카오 2020. 5. 28. 23:01
2017 카카오코드 본선 리틀 프렌즈 사천성 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr 풀이 문제를 꼼꼼히 읽지 못해서 푸는데 많은 삽질과 시간을 투자했다.. 첫번째로 간과한 부분은 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다) 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다) 선분이 3개 이하일 경우 블록을 제거할 수 있다고 생각..
-
프로그래머스 Lv.3) 보행자 천국알고리즘/프로그래머스 카카오 2020. 5. 27. 22:57
2017 카카오코드 예선 보행자 천국 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 풀이 DP 문제임을 눈치 챘고, DP로 풀기위해 노력했다. 하지만, 눈치챈 것 이상도 이하도 아니었다. DP임을 알고도 어떻게 해야할지 감이 안잡혔기 때문이다.. 처음에는 2차원 배열 DP를 만들어 x축과 y축이 각각 0인 좌표들에 통행 금지 표지판을 만나기 전까지 1을 저장해주었다. (y=0일 때, x를 증가하면서 저장, x=0일 때, y를 증가시키면서 저장) 하지만, 나중에 회전 불가 표지판을 만날 때 어떤 경로..
-
프로그래머스 Lv.3) 가장 긴 팰린드롬알고리즘/프로그래머스 2020. 5. 27. 22:42
가장 긴 팰린드롬 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 풀이 세 가지 풀이를 시도한 문제다. 첫번째로 시도한 방법은 이분 탐색이었다. binary search로 답이 충분히 나올 수 있다고 생각했지만, 답이 홀수개라면 mid가 답보다 작은 짝수가 됐을 때 팰린드롬이 형성되지 않아서 답까지 mid가 커지지 못하는 경우가 있었다. (홀 짝 반대의 경우도) 그래서 여러가지를 고려하다가 결국 실패했고, 완전탐색을 하고자 마음먹었다. 두번째로 시도한 방법..
-
프로그래머스 Lv.2) n진수 게임알고리즘/프로그래머스 카카오 2020. 5. 26. 23:06
2018 KAKAO BLIND RECRUITMENT [3차] n진수 게임 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0� programmers.co.kr 풀이 개인적으로는 가장 어려운 문제였다. 오랫동안 풀지 못해서 카카오 해설을 봤는데 정답률이 96%정도..? 된 것 같았다. 마음이 아프다... 어떻게 해야 효율적일지, 수학식을 생각하다가 시간을 보내고 머리가 복잡해지면서 지친 것같다. 도저히 안되겠길래 문제 풀이 포스팅을 찾아보았는데, 최대가 16진수니까 16진수에 맞춰 미리 char 배열을 만들어 두고, 최대 경우의 ..