java
-
프로그래머스 Lv.2) 피보나치 수알고리즘/프로그래머스 2020. 5. 21. 16:36
피보나치 수 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 풀이 피보나치를 배열을 통해 푸는 방법과, 1234567로 나눈 나머지 값을 저장 및 return한다는 것 이외는 특별하게 신경써야하는 부분이 없다. 혹시 피보나치를 구현하는데 어려움을 겪는 분이 있다면, 피보나치를 배열로 풀기 전에 재귀를 통해 푸는 방법을 먼저 익히는 것을 ..
-
프로그래머스 Lv.2) 올바른 괄호 짝지어 제거하기알고리즘/프로그래머스 2020. 5. 21. 16:23
올바른 괄호 짝지어 제거하기 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 풀이 로직을 바꿔가며 세 번 시도한 문제다. 첫번째는 StringBuffer에 주어진 String을 두고, 겹치는 부분을 계속해서 지워나가고 StringBuffer의 길이가 0이면 1, 아니면 0을 리턴해주었는데, 역시나 시간초과가 떴다. 두번째로 시도한 로직은 먼저 String을 돌면서 연속되는 글자가 있는 두 index를 LinkedList에 넣어주었다. LinkedList를 돌면서 카운팅을 해주었고, 해당 문자를 제..
-
프로그래머스 Lv.2) N개의 최소공배수알고리즘/프로그래머스 2020. 5. 21. 16:15
N개의 최소공배수 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배�� programmers.co.kr 풀이 이 문제는 인터넷 검색을 통해 최대 공약수, 최소 공배수를 구하는 알고리즘을 찾았다. 평소같으면 몰라도 푸는 연습을 했겠지만, 이 문제는 찾고 이해하는게 더 좋다고 판단했기 때문이다. 분명 학부생 때는 이 알고리즘을 구현 했었다. 지금은 까먹었다는게 문제지만.. 아무튼 다시 한번 머리에 각인 시키는 계기가 되었으면 한다. 1. for문을 돌면서 최소공배수를 구한다. 2. 최소공배수는 두 숫자의..
-
프로그래머스 Lv.2) JadenCase 문자열 만들기알고리즘/프로그래머스 2020. 5. 21. 16:10
JadenCase 문자열 만들기 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 풀이 시작하는 단어에 대한 검증, 이후 이어지는 글자들에 대한 검증을 해서 Jaden Case로 바꿔주었다. 하지만 8번만 실패가 뜨길래 뭔가 했다. 결국 이 문제의 질문하기를 들어가보니 마지막에 " "와 같이 띄어쓰기가 주어지는 경우를 체크 해줘야 한다는 것이다. split을 통해 한 단어(?)씩 Jaden Case를 만들어줬고, 마지막 띄어쓰기가 있을거라는 상상도 하지..
-
프로그래머스 Lv.2) 올바른 괄호알고리즘/프로그래머스 2020. 5. 19. 23:06
올바른 괄호 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호� programmers.co.kr 풀이 괄호가 열리고 닫히는 것에 주목했다. 괄호가 여는 것 보다 닫히는게 더 많이 나온다면, 그 시점에서 불완전한 괄호가 된다. 이에 따라 스택개념으로 괄호의 갯수를 세주었다. 1. 괄호가 열리면 count를 세준다. 2. 괄호가 닫히면 count를 빼준다. 3. count의 수가 0보다 작은 수가 된다면 탐색을 마치면서 false를 저장한다. 코드 public class AlrightBracket_12909 {..
-
프로그래머스 Lv.2) 가장 큰 정사각형 찾기알고리즘/프로그래머스 2020. 5. 19. 23:01
가장 큰 정사각형 찾기 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 DP를 이용해 이 문제를 풀었다. Top-down을 이용해서 풀었고, board를 돌면서 어떠한 점이 1이라면 그 점을 기준으로 왼쪽, 왼쪽 상단, 상단 세 점의 최소값을 찾아 1을 더해줬다. 이후에 max값을 갱신했고, 탐색이 끝난 후에는 max값의 제곱을 리턴해주었다. 1. board의 모든 점을 탐색한다. 2. board가 1이라면 해당 점을 기준으로 좌측, 좌측 상단, 상단 세 점의 최소값을 찾는다. 2.1 최소값에 +1을 해주어 해당 점에서 만들 수 있는 정사각형의 최대 크기를 저장해주었다. 3. 2번이 끝난 후 m..
-
프로그래머스 Lv.2) 단체사진 찍기알고리즘/프로그래머스 카카오 2020. 5. 19. 22:51
단체사진 찍기 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 � programmers.co.kr 풀이 우여곡절이 많았던 문제다. 시간초과가 뜰까봐 문제를 보자마자 생각난 완전탐색을 미뤄두고 여러가지 시도를 했다. 하지만, 이마저도 다 시간초과가 떠서 어떻게 풀라는 건지 막막했다. 문제를 푼 지 오랜시간이 지나고 도저히 모르겠어서 검색을 했다. 맨 위에 나온 블로그를 켜자마자 첫 줄에 완전탐색으로 풀었다는 글을 보자마자 블로그를 껐다. 그리고 한숨을 쉬었다.. 완탐이 되는 문제라니.. 수학적 공식을 활용하려고 발버둥 쳤던 내 자신을 반성..
-
프로그래머스 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..