알고리즘
-
프로그래머스 Lv.2) 땅따먹기알고리즘/프로그래머스 2020. 5. 19. 22:40
땅따먹기 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 풀이 나를 좌절하게 만든 문제였다... 분명 DP를 활용하는 문제임을 눈치챘고 유사한 문제도 풀어냈었는데, 검색과 자동완성 기능 없이 풀어야한다는 생각이 들어서 그랬을까 못풀었다. 그래서 프로그래머스에서 제공하는 문제의 해답 영상을 봤다. 마지막 행의 4개의 x에 대해 bottom-up 방식으로 dp를 진행하는 것이었다.. 분명 이렇게 풀었던 dp문제가 있었던게 기억났다. 생각보다 간단했다.. 로직 1. 행의 길이와 x의 개수(4..
-
프로그래머스 Lv.2) 다음 큰 숫자알고리즘/프로그래머스 2020. 5. 19. 22:30
다음 큰 숫자 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 풀이 Lv2 문제를 풀고 있는 이유는 내 생각보다 생각을 많이 해야하는 문제가 존재하고, 기본을 다시 한 번 되돌아보기 좋기 때문이다. 또한, IDE를 사용하지 않고 문제를 푸는 연습을 하고있어서, 코드가 많이 길어지지 않는 문제들로 먼저 연습하고 있기 때문이다. 아무튼 이 문제를 처음 마주했을 때는 '이건 검색을 해야 알 수 있는 문제다' 였다. 물론 코드를 검색하고 이런 것이 아니라 JAVA에서 숫자를 2진수로 ..
-
프로그래머스 Lv.2) 튜플알고리즘/프로그래머스 카카오 2020. 5. 19. 22:21
튜플 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 풀이 답의 규칙을 찾은 결과 가장 작은 크기의 부분 수열이 가진 원소의 순서대로 답의 순서가 정해진다는 것이었다. "{{1,2,3},{2,1},{1,2,4,3},{2}}" 위의 예제로 설명하면, 가장 작은 크기의 부분수열 {2}로부터 2가 정답의 맨 첫번째임을 알 수 있고, 그다음 {2,1}을 통해 2->1, {1,2,3}을 통해 2->1->3, {1,2,4,3}을 통해 2->1->3->4가 되는 것이다...
-
프로그래머스 Lv.2) 124 나라의 숫자알고리즘/프로그래머스 2020. 5. 16. 17:30
124 나라의 숫자 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 풀이 이 문제도 고민의 시간이 길었다. 문제 자체는 이해하기 쉬웠다. 모든 10진법 숫자는 1,2,4 세 개를 통해 표현해야하는 문제이고 3진법과 비슷한 느낌이라고 생각했다. 다만 다른 점?은 세가지 숫자만 이용하는데 1,2,3이 아닌 1,2,4라는 것이다.. ㅎㅎ 조금 특이하게 이 문제는 로직 자체는 쉽게 떠올랐으나, 구현이 오래걸렸다. (멀쩡한 사각형과 이 문제는 어제 푼 문젠데, 어제 컨디션이 별로였..
-
프로그래머스 Lv.2) 멀쩡한 사각형알고리즘/프로그래머스 2020. 5. 16. 17:06
멀쩡한 사각형 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 �� programmers.co.kr 풀이 평소에 레벨 3,4 혹은 카카오 문제를 풀어왔기에 레벨 2는 쉽다고 생각하며 접근했다가 큰코다쳤다. 너무너무 어려웠고 푸는데 오랜 시간이 걸렸다. 먼저, 처음에 생각했던 로직은 직선이 타일과 정수 좌표에서 만나는 구간을 구해 반복되는 만큼 수를 빼주는 것이었다. 그래서 Linear Equation(1차 방정식)을 세우고 해당 직선과의 거리를 구하면서 진행했다. 정수인 x,y 점을 돌면서 루트 2(sqrt 2)보..
-
프로그래머스 Lv.2) 스킬트리알고리즘/프로그래머스 2020. 5. 16. 16:42
스킬트리 코딩테스트 연습 - 스킬트리 programmers.co.kr 풀이 (2020.05.16) 스킬을 찍어야하는 순서를 ArrayList에 char로 담아주었다. 또한, char를 담으면서 해당 스킬이 ArrayList에 부여된 인덱스 넘버를 HashMap을 통해 저장해주었다. 이후, 스킬 트리 배열을 돌면서 String값을 검증했다. 우선 모든 스킬이 가능하다는 가정을 두고 스킬트리 배열의 길이 만큼 return할 결과에 담아주었다. String을 돌 때마다 해당 SkillTree를 위한 ArrayList에 스킬을 저장하면서 확인했다. String의 index마다 그 스킬이 찍어야하는 스킬 ArrayList에 담겨있는지 먼저 확인하고, 배워야하는 스킬이면 이 스킬 이전에 배워야하는 스킬을 배웠는지 ..
-
프로그래머스 Lv.2) 카카오프렌즈 컬러링북알고리즘/프로그래머스 카카오 2020. 5. 16. 16:34
카카오프렌즈 컬러링북 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 그림의 난이도를 영역의 수로 정의했다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다. picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다. 이 두 부분만 유의하면 어렵지 않게 풀 수 있었다. 영역의 갯수와 가장 넓은 공간을 가지고 있는 영역의 넓이를 리턴해야하기 때문에 1. 먼저 grouping을 해주고 2. 해당 그룹의 넓이를 HashMap에 저장해주었다. grouping을 할때는 out of index..
-
프로그래머스 Lv.4) 추석 트래픽알고리즘/프로그래머스 카카오 2020. 5. 15. 00:00
카카오 2018 Blind Recruitment 추석 트래픽 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 결국은 다시 풀어서 맞았다. 전에 문제를 풀었을 때는 확실히 겁에 질렸던 것 같다. 날짜 검사를 해야한다는 압박감에 평소에 쓰지도 않는 Date 라던지 SimpleDateFormat을 검색해서 적용하려고 하고, 그 이후에는 0.001초 마다 검사하면 time over가 뜰텐데 하는 마음에 HashMap에 초단위로 저장을 하고 그랬다. 틀릴줄알고 작성한 코드가 78점이나 나와서 당황했지만, 그게 독이었던 것 같다. 아무튼 문제를 다시 보니까 생각..