알고리즘/프로그래머스
-
프로그래머스 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. 27. 22:42
가장 긴 팰린드롬 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 풀이 세 가지 풀이를 시도한 문제다. 첫번째로 시도한 방법은 이분 탐색이었다. binary search로 답이 충분히 나올 수 있다고 생각했지만, 답이 홀수개라면 mid가 답보다 작은 짝수가 됐을 때 팰린드롬이 형성되지 않아서 답까지 mid가 커지지 못하는 경우가 있었다. (홀 짝 반대의 경우도) 그래서 여러가지를 고려하다가 결국 실패했고, 완전탐색을 하고자 마음먹었다. 두번째로 시도한 방법..
-
프로그래머스 Lv.2) 영어 끝말잇기알고리즘/프로그래머스 2020. 5. 24. 16:43
영어 끝말잇기 코딩테스트 연습 - 영어 끝말잇기 3 [tank, kick, know, wheel, land, dream, mother, robot, tank] [3,3] 5 [hello, observe, effect, take, either, recognize, encourage, ensure, establish, hang, gather, refer, reference, estimate, executive] [0,0] programmers.co.kr 풀이 ArrayList를 이용한 풀이(WordChain 메소드)와 이중 for문을 돌면서 조건 검사(getInfo 메소드) 두 방법으로 풀어봤다. ArrayList도 언뜻 보면 2중 포문 같겠지만, turn과 person을 나눴을 뿐 단일 for문과 같다. ..
-
프로그래머스 Lv.2) 예상 대진표알고리즘/프로그래머스 2020. 5. 22. 22:35
예상 대진표 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N� programmers.co.kr 풀이 이 문제를 2일 전인가 쯤 같이 취준하고있는 형한테 문제를 받았었다. 풀이는 비트 연산을 통해서 경기 수를 구하는 것이었다. 하지만, 내가 비트연산으로 문제를 풀기에는 아직 무리라는 생각이 들어서 나만의 방식으로 풀기로 했다. 궁금하신 분은 여기에서 확인하시면 좋을 것 같습니다. : ) 처음 풀었을 때는 1번과 25번이 시관초과가 떴었다. 그래서 바로 매치를 할 수 있는 경우를 추가시켜주었다. if(left%2 ==1..
-
프로그래머스 Lv.2) 숫자의 표현알고리즘/프로그래머스 2020. 5. 21. 16:51
숫자의 표현 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 풀이 이 문제도 삽질을 조금 한것같다. 수식을 통해 풀어야한다는 압박감에 이것 저것 시도해본 문제였다. 이분탐색을 통해서 풀어보려고도 하고, 점화식을 세워서 풀어보려고도 했는데 코드에서 보시면 알 수 있듯 모두 실패했다.. 시간초과거나 정답이 아닌 경우가 많았기 때문이다. 이 문제도 질문하기 탭을 통해 깨달음을 얻었다. 그냥 완전탐색을 하면 된다는 사실을 알고 허무했다. n이 최대 10000인데 완전탐색하면 효율이 안좋지 않나 생..
-
프로그래머스 Lv.2) 행렬의 곱셈알고리즘/프로그래머스 2020. 5. 21. 16:48
행렬의 곱셈 코딩테스트 연습 - 행렬의 곱셈 [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] programmers.co.kr 풀이 행렬의 곱셈에 대해 배열의 곱셈이라고 이해하고 문제이해를 5분정도 못했다... ㅎㅎㅎㅎ 아무튼 행렬의 곱셈을 구글링해서 곱셈법을 다시 배웠다.. ㅠㅠ 1. 배열 arr1과 arr2를 통해 답이되는 answer 배열을 만들어 준다. 1-1. 이때 크기는 arr1의 행, arr2의 열이 된다. (행렬의 연산 특징) 2. 각각 배열의 idx에 대해 행렬 곱셈식을 구해 더해준다. 코드 class Solution { public int[..