Hello, Freakin world!

11월 코드 챌린지 3문제 도전 - 백준 최소 500문제 돌파하기(현재 390) 동기를 잃어버렸다. 알고리즘 분야에 너무 과하게 투자하는 것은 아닌가? 라는 생각이 들자 동기를 잃어버렸다. 이제는 실제로 뭔가를 만들어 봐야 한다.. 그리고 이제 코딩테스트에서 어이없게 떨어지는 실력은 아니라고 판단되기 때문에 우선 순위를 좀 낮출 필요가 있다. 그럼에도 완전 놓치는 않았다. 현재까지 백준 420 문제 정도를 풀었다. (2020.11.08) Web - 인프런 무료 강의 시청 (하루에 하나씩) 애초에 다 보기로 했던 김영한 님의 무료 강의는 다 봤다. 다른 강의들도 조금씩 보는 중. 기타 자기 계발 - 책 2권 읽기 시작의 기술, 습관의 재발견을 읽었으나 서평은 쓰지 않았음. - 매일매일 코틀린 매일 1 페이..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP 문제를 계속 풀고 있는데, 패턴이 참 다양하다는 생각이 듭니다. 그리고 꽤 재밌네요 ㅋㅋㅋ 핵심 아이디어는 위처럼 (i,j) 위치의 값이 1일 때 위, 왼쪽 위, 왼쪽 위치의 요소도 1이면 정사각형 만들어 진다에서 출발합니다. 나머지는 저 위의 아이디어를 기반으로 점화식을 작성하면 됩니다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이때까지 DP와는 성격이 조금 다른 문제였다. 이전까지는 단순히 완전 탐색의 바텀업 버전이었지만 이 문제는 재귀를 이용한 탑다운 방식에 cache배열을 추가하면서 해결할 수 있다. 이 문제에서 가장 중요한 한 문장이 있다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는..

www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제를 제대로 이해만 하면 쉽게 풀 수 있는 문제입니다. 비행기의 종류에 간선 하나가 대응하기 때문에모든 도시를 탐색할 수 있는 최소한의 비행기 종류는 그냥 단순히 모든 노드를 다 탐색하는데 필요한 간선의 수입니다. 네. 그냥 단순 그래프 순회 문제입니다. import java.io.*; import java.util.ArrayList; import java.util.Lis..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 글의 초점은 문제 풀이에 있지 않다. 그러므로 바로 본론으로 들어가겠다. 이 문제의 점화식은 다음과 같다. 아직 몇 문제 풀어보진 않았지만 지금까지 풀어본 DP 문제들은 '완전 탐색의 바텀-업 버전'이었다. 이런 문제들은 완전 탐색을 바텀업으로 구현하기 위해 점화식을 세울 필요가 있다. 이 점화식도 그냥 하늘에서 떨어지는게 아니라 완전 탐색의..

www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 단순히 DFS 한 번에 풀 수 있는 문제인 줄 알았지만, 처리해야될 예외 사항이 좀 있습니다. 각 서브트리 루트에 리프노드의 개수를 저장하는 알고리즘이 있다고 합시다. 그 알고리즘을 이용해 위와 같은 결과를 만들어 냈습니다. 여기서 2번 노드를 지우려면 루트 노드의 값(3)에서 2번 노드의 값(1)을 빼면 답이 됩니다. 하지만... 다음의 경우는 어떨까요? 위에서 1번 노드를 제거하면 값이 0이 되어버립니..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이 문제를 풀면서 너무 아쉬웠다. 아마 10월 코드 챌린지 3번과 비슷한 문제가 아닌가 싶었다. 트리 부분을 너무 소홀히했다. 크 3솔이 눈에 아른거린다. 풀이 방법은 트리를 순회하면서 현재 노드를 기점으로 가장 긴 간선을 계산하고 자손의 수에 따라 가장 큰 2개나 한개를 현재 노드가 중심이 되는 지름이라고 한다. 아 이게 말로 설명하기는 조금 버겁다. 재귀를 이해한다면 코드를 보는게 낫다...

www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 방법 전체 배열을 반으로 나눠 완전탐색을 통해 모든 부분수열의 합을 찾아내 각각 leftList, rightList에 저장합니다. 그리고 부분수열의 합이 저장된 leftList, rightList를 크기순으로 정렬합니다. (저는 하나는 오름차순, 다른 하나는 내림차순 정렬했습니다.) 인덱스를 조정해가면서 N^2 복잡도로 모든 합을 검색하는게 아니라 스위핑 방식으로 N..

아 ... 목표했던 바는 이뤘지만 사람의 욕심이란... 목표는 2문제를 맞추는 거였는데, 백준에서 꽤 많이 풀다보니 여기까진 쉬웠다.(나도 놀람 ㅋㅋㅋㅋ 다 풀 수 있을 것 같은 느낌이었다) 1번은 간단한 구현, 2번은 간단한 분할 정복 알고리즘을 짤 수 있느면 풀 수 있는 문제. 3,4 문제가 어려웠다. 3번은 아이디어가 떠오르질 않아 패스했고 4번을 집중적으로 공략했지만 실패. 효율성 무시하고 점수를 긁으면 각 문제당 50점 정도 긁어지는 것 같았다. (4번은 그렇게해도 52점 주더라) 근데 뭐 별 의미가 있나 싶다. 3문제를 100점으로 풀어야 프로그래머스에서 코딩 테스트때 프리패스권을 주기 때문. 아 아쉽다... 3,4번을 두 시간 넘게 팠지만 아쉽게도 fail. (최종 성적은 252점) 일단 풀..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻�� www.acmicpc.net 문제 이름이 뭔가 엄청나보이지만 그냥 전형적인 플로이드 와샬 문제였다. 모든 정점에 대해서 BFS를 수행해서도 풀 수 있는 듯 보인다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer..