본문 바로가기

분류 전체보기1056

백준 4485 자바 - 녹색 옷 입은 애가 젤다지? (BOJ 4485 JAVA) 문제 : boj4485 1. 젤다가 활강하는 장면! 야숨2가 나오면 알고리즘을 당분간 못(안)풀 수 있으니 알고리즘을 미리 풀고 키핑해둬야겠다ㅋㅋㅋ 2. 만약 이런식의 문제에서 이동 가능한게 좌측과 아래쪽 뿐이었다면 DP로도 풀 수 있다. 하지만 이 문제와 같이 4방향으로 이동이 가능하다면, DP로 풀어보려면 결국 모든 경우를 다 봐야해서 시간초과가 나게 될 것이다. O((N^2)^2) 한가지 떠올릴만한 점은 결국 배열도 그래프라는 것이다. 예제 입력의 아래와 같은 부분을 그래프 형태로 그려보면 다음과 같다. 3 5 5 4 3 9 1 3 2 7 결국 이 문제는 가장 적게 잃으면서 진행해야 하므로, 그냥 그래프에서 start부터 goal 까지의 최단거리를 찾는 것과 동일하다! 그리고 가중치가 모두 양수이면.. 2021. 12. 24.
백준 2670 자바 - 연속부분최대곱 (BOJ 2670 JAVA) 문제 : boj2670 1. 모든 경우를 보면서, 이전 값이 1.0 보다 크다면 현재 입력받은 수를 곱해준다. 이전까지 구해둔 값이 1.0 이하라면 현재값을 곱하는 것이 손해이므로, 현재값부터 다시 연속된 수를 파악하면 된다. 예를들어 1.2 0.9 1.5 가 있고 현재 1.5를 살펴볼 차례라고 해보자. 이전까지의 값의 곱인 1.2*0.9는 1.08이므로 1.0보다 크다. 따라서 1.5까지 곱해서 1.620이 답이 된다. 반면에 1.1 0.9 1.5라면 1.1*0.9 = 0.99 이므로 1.5에 곱하면 오히려 손해이다. 따라서 1.5부터 다시 구해나가는 것이 더 이득이다. 정리하면 현재 입력받은 수가 cur, 이전까지 계산하던 값이 bf 라고 해보자. bf>1.0이라면 bf = bf * cur이 될 것이.. 2021. 12. 23.
[진행1] 안써본거 위주로 써보기 위한 토이 프로젝트 계획 단계 (0. [계획] / 1. [계획수정]) 이후 개념이 잡히지 않은 상태에서 거의 제로 상태에서 시작해본거라, 시행착오가 많았다. 꽤 열심히 진행했지만 생각보다 더뎌서 좀 마음이 급하긴하다. 부족한 부분에 대해 몰랐으면 괜찮았는데, 이미 알게된 이상 빨리 개념잡히고 싶다. 3~4일에 걸쳐 일단은 코드를 짜기보다는 기반 기술 및 환경을 잡아보며 토이프로젝트를 진행한 중간결과에 대해 작성해본다. 진행하며 모든 과정은 노션에 작성해두었다. 다만 시행착오가 많았기에 잘 안되던것도 많아 바로 여기에 옮길 순 없을 듯하고, 정리하여 토이 프로젝트와 별개의 포스트로 깔끔하게 정리해서 작성할 듯 하다. 이 포스트에서는 진행하면서 해본걸 작성하고 느낀점 위주로 작성할 것 같다. 어차피 볼 사람 없을테니 스스로 나.. 2021. 12. 22.
[계획수정] 안써본거 위주로 써보기 위한 토이 프로젝트 '0. [계획]' 단계에서 썼던 것들 중 수정한 것들과 그 이유를 작성해본다. 또한 계획을 적을 때 좀 없었던 개념에 맞는지 안맞는지 적은 부분이 있었고 지금도 그렇지만, 아무튼 좀 더 개념이 잡혔으므로 이전에서 수정된 부분에 대해 작성한다. 어차피 아무도 안보겠지만, 아무튼 계획단계의 글을 보고 읽어야 이해가 될 듯 한다. 1. MacOS에서 개발해보기 -> Mac을 실행시킬 HW가 없었기에 Vmware에 가상으로 올린 맥 OS를 사용해보려 했었다. 하지만 해킨토시이기도 하고, 일단 가장 크게 이 환경에서 Docker를 실행할수가 없었다. 구글링을 꽤 해봤으나 해결하지 못했고, 역시 vmware에 올린 맥에서 docker 실행을 성공한 포스트를 찾지 못해 포기했다. -> 대신 윈도우 환경 그대로에서, .. 2021. 12. 22.
백준 9001 자바 - Rectangle Coloring (BOJ 9001 JAVA) 문제 : boj9001 1. 우선 그룹의 개수는 어떻게 구할 수 있을까? 그룹 구하는데 특화된 union-find (분리 집합) 알고리즘을 사용하면 쉽게 그룹이 총 몇개인지 알 수 있다. 2. 그럼 입력받은 직사각형들에 대해 모든 경우를 다 보면서 O(N*N) 서로 직사각형이 겹치는지 여부만 알 수 있다면 union-find로 그룹으로 만들어주고, 최종적으로 그룹의 개수를 출력해주면 된다. 직사각형 겹치는걸 확인하는데 가장 쉬운 방법은 배열에 직접 직사각형에 포함된 면적을 기입하면서 겹치는지 확인하는 것인데, 문제는 이 경우 최대 O(N*10000*10000) 이 걸리므로 불가하다. N이 최대 200인것에 착안해 좌표 압축을 통해 해봐도 된다. 그럼 최대 O(N^3)이면 구해볼 수 있다. 내 경우엔 그냥.. 2021. 12. 22.
백준 14002 자바 - 가장 긴 증가하는 부분 수열 4 (BOJ 14002 JAVA) 문제 : boj14002 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘에 대한 설명은 생략하고, 가능한 수열을 찾는 방법에 대해 설명한다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제 정답은 '10 20 30'이므로 LIS 알고리즘 자체만 사용해서는 원하는 실제 수열을 출력할 수 없다. 2. 추가로 배열을 더 사용해서 .. 2021. 12. 21.
백준 20159 자바 - 동작 그만. 밑장 빼기냐? (BOJ 20159 JAVA) 문제 : boj20159 1. 정훈이가 받을 차례에 밑장빼기 한 경우 기본 아이디어는 직접 밑장빼기를 할 때 어떤 카드를 주게되는지 그려보면서 해보면 어렵지 않게 찾을 수 있다. 예제 입력 1 (3 2 5 2 1 3)을 홀수번째 카드(원래 정훈이가 받을 카드)와 짝수번째 카드(원래 상대방이 받을 카드)로 나눠서 그려보자. 그럼 밑장빼기를 하지 않는다면 다음과 같이 3, 5, 1을 받게 된다. 그럼 5번을 받을 차례 때 밑장빼기를 하면 어떻게 될까? '5'를 받을 차례에 짝수번째의 마지막에 있는 '3'을 받고, 이후 순서가 변경되면서 짝수번째를 정훈이가 받게 된다. 따라서 밑장빼기를 한 이후로는 짝수번째 카드를 받게 된다. 이런식으로 모든 경우를 다 그려보면 다음과 같다. 2. 정훈이가 상대방한테 밑장을 .. 2021. 12. 20.
백준 2806 자바 - DNA 발견 (BOJ 2806 JAVA) 문제 : boj2806 1. 문자를 하나씩 보면서 전부 A, 혹은 B로 변경해 나간다고 생각해보자. 그렇다면 8가지 경우가 나온다. case1. 현재 문자는 A, 이전까지 전부 A 였음, 전부 A로 유지할 것임 -> 이전 상태에 그냥 A를 붙이면 된다. (돌연변이 +0) case2. 현재 문자는 A, 이전까지 전부 A 였음, 전부 B로 유지할 것임 -> 이전 상태에 그냥 A를 붙인 후, 전체를 B로 변경한다. (돌연변이 +1) case3. 현재 문자는 A, 이전까지 전부 B 였음, 전부 A로 유지할 것임 -> 이전 상태 전체를 A로 변경하고 A를 붙인다. (돌연변이 +1) case4. 현재 문자는 A, 이전까지 전부 B 였음, 전부 B로 유지할 것임 -> 현재 문자를 B로 변경해서 붙인다. (돌연변이 +.. 2021. 12. 19.
LeetCode 25 - Reverse Nodes in k-Group - Hard (Java) 리스트 구현을 직접 해봤다면 어렵지 않게 풀 수 있는 문제이다. 다만 O(N)에 풀 수 있는 아이디어는 어쩌면 생각하기 어려울 수도 있을 것 같다. 원본 리스트를 순회하며 reverse 할 항목들을 tmp배열에 넣어둔 뒤, k개 만큼 채워졌다면 역순으로 결과 리스트에 넣는다.(코드에서 idx==k 일 경우) 그리고 마지막에 나누어떨어지지 않는 항목들에 대해서는 리스트의 끝을 만날 경우 tmp에 있는 남은 항목들을 역순이 아니라 원래순서대로 출력해주면 된다.(코드에서 head==null일 경우) 이전에 풀었던 5번 Medium이 더 어려웠던 것 같은데.. 리트코드 난이도 책정 방식이 좀 이상한 것 같다. 코드 : github /** * Definition for singly-linked list. * pu.. 2021. 12. 18.
백준 2636 자바 - 치즈 (BOJ 2636 JAVA) 문제 : boj2636 1. 우선 '치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.' 부분부터 생각해보자. 1로 막혀있는 0 부분은 공기로 치지 않는다는 의미로, 이 조건에 따라 단순히 '0'과 인접한 '1'만 찾아선 안된다. 탐색에 익숙하지 않다면 아이디어를 떠올리기 힘들 수 있다. 이 문제의 경우 외부 공기에서부터 탐색을 시작하면 치즈로 둘러쌓인 내부는 보지 않을 수 있다. 그리고 이 문제는 친절하게 판의 가장자리에는 치즈가 놓여있지 않다고 한다. 그러니 단순하게 0,0 지점에서 시작하면 언제나 외부 공기에서 시작함을 보장할 수 있다. 따라서 모든 치즈가 사라질 때 까지, 0,0 부터 시작하는 bfs 혹은 dfs를 계속 반복하고, 그때마.. 2021. 12. 18.

티스토리툴바