본문 바로가기

전체 글1047

백준 15779 자바 - ZigZag (BOJ 15779 JAVA) https://www.acmicpc.net/problem/15779 i번째 데이터에 대해, i-2, i-1, i 번째 데이터를 살펴보며 단조증가 수열이거나 단조감소 수열일 경우 arr[i] = 0을 기입했고, 지그재그 수열일 경우 1을 기입함.(13line) 그럼 예를들어서 문제에 제시된 2번째 예시 (1,3,4,2,5)의 경우 제가 짠 로직으로는 arr = [0, 0, 0, 1, 1] 와 같이 기입됨. 근데 이 때 1이 연속된 갯수가 결국 지그재그 수열의 길이이므로, 13line처럼 이전값+1을 해주면 연속된 길이도 한꺼번에 구할 수 있음. 최종적으로 arr 배열에 있는 가장 큰 수가 가장 긴 지그재그 수열의 길이이므로 max값을 찾아주고 (19line) 거기에 2를 더해준게 답임. (+2를 해준 것은.. 2021. 10. 8.
백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA) https://www.acmicpc.net/problem/2759 알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다. Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리.. 전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다. 결론적으로 제 풀이는 다음과 같음. 가장 큰 .. 2021. 10. 7.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA) https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀.. 2021. 10. 7.
백준 22866 자바 - 탑 보기 (BOJ 22866 JAVA) https://www.acmicpc.net/problem/22866 풀이방법을 생각하기보다는 구현이 복잡한(==귀찮은) 문제였다. 일단 3가지로 나눠서 생각해봐야 하는데, 1. 각 건물에서 좌측으로 보이는 건물의 개수 2. 각 건물에서 우측으로 보이는 건물의 개수 3. 각 건물에서 가장 가까운 건물 번호 중 작은 번호 위와 같다. 일단 '각 건물에서 좌측으로 보이는 건물의 개수' 어떻게 구할지 생각해보자. 문제에서 제시된 예시를 예시로 들겠다. 3 7 1 6 3 5 1 7 에서 좌측부터 차례로 봐보자. 1번째 건물 : 3 이다. 현재 좌측으로 보이는건 없다. 뭐 일단 어딘가에 넣어둬보자. 2번째 건물 : 7 이다. 현재 좌측으로 보이는건 없다. (7보다 높아야 보임). 그 이후로는 모두 7에 막힐것이므로.. 2021. 10. 5.
백준 12931 자바 - 두 배 더하기 (BOJ 12931 JAVA) https://www.acmicpc.net/problem/12931 우선 처음으로 생각할 부분이, 만약 시작지점인 0,0,0,... 에서 시작해서 제시된 B 배열을 찾아가려면 결국 모든 경우를 봐야한다. 매번 B 배열과 비교하며 최소 연산 횟수를 찾게 짜는건 사실상 무리라고 본다. 그럼 반대로 B 배열에서 0,0,0,...을 찾아가는걸 생각해보자. 제시된 연산은 각각에대해 1을 더하는 것과 전체에 대해 2를 곱하는 것이므로, 반대로 B배열에서 0,0,0,... 을 찾아가기 위해서는 각 배열에 대해 1을 빼는 연산과, 전체에 대해 2로 나누는 과정을 거쳐야 한다. 그럼 N=1일 때 조차도 무조건 2로 나누는 것이 이득인 것을 쉽게 알 수 있다. (더 적은 연산으로 차이를 더 많이 낼 수 있음) 최종적으로 .. 2021. 10. 5.
백준 15989 자바 - 1, 2, 3 더하기 4 (BOJ 15989 JAVA) https://www.acmicpc.net/problem/15989 처음엔 무지성 DP 돌리면 될줄 알았는데, 수의 순서가 다른 것은 하나로 처리해야 한다. 무작정 dp 진행하며 모든 쌍을 확인하고, 그 중 겹치는 것을 확인하기엔 메모리가 부족해보인다. 풀이1. 2차원 DP https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15900/BOJ_15989_2D-DP.java 우선 서로 겹치는 쌍이 생기지 않도록 하려면 어떻게 해야할까? 각 n에서 더해지는 숫자에 제한을 두면 된다. 예를 들어 서로 겹쳐도 된다고 생각하고 n = 1~4 일 때 1,2,3의 덧셈으로 표현 가능한 경우를 보자. 1 : 1 2 : 2, 1+1 3 : 3, 1+1+1, 1+.. 2021. 10. 4.
백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3.
백준 21772 자바 - 가희의 고구마 먹방 (BOJ 21772 JAVA) https://www.acmicpc.net/problem/21772 BFS로 착각할 여지가 있는 문제이다. 하지만 한번 지나간 곳을 다시 올 수 있다는 점과, 지나간 경로상에 있는 고구마의 갯수를 세야 하는 문제이므로 방문체크를 할 수 없다. 따라서 모든 경로를 보는 Brute Force 문제이다. 정확히 따지자면 내 로직의 경우 사실 모든 경우를 보진 않았고, 답이 될 수 없는 경로인 경우 취소시켰으므로 Back Tracking이라 봐도 되는데, 어차피 모든경로 다 봐도 시간초과가 나진 않으므로 큰 의미는 없다. t가 최대 10이고 한 장소에서 상하좌우 4개의 방향으로 이동 가능하므로 최대 O(4^10) 짜리 BF라고 보면 된다. 그냥 DFS 돌리면서 모든 경우를 확인하면 된다. 주의점은 '가희가 고구.. 2021. 10. 3.
백준 11048 자바 - 이동하기 (BOJ 11048 JAVA) https://www.acmicpc.net/problem/11048 만약 이동이 상하좌우로 가능했었다면, 혹은 [우측, 아래, 우측아래, 좌측]과 같이 좌측으로도 이동이 가능했다던지 하면 BFS 등의 방법으로 전체 경우를 보면서 풀어야 한다. 하지만 이처럼 방향이 우측, 아래, 우측아래 대각선 처럼 한쪽 '사분면'으로 고정되어 있다면 Dynamic Programming(DP; 동적계획법)으로 더 간단하게 풀 수 있다. 일단 다음의 그림을 보자. 위 그림은 이 문제에서 (1,1)에서 (N,M)으로 갈 때 각 위치에서 이동할 수 있는 방향을 나타낸 것이다. 그럼 위 그림에서 예를들어 정중앙의 '5'로 올 수 있는 화살표만 남겨보겠다. 다음으로 중앙 우측의 '6'으로 오는 화살표이다. 그럼 벽에 붙어있는 '2.. 2021. 10. 2.
백준 2825 자바 - 수업시간에 교수님 몰래 교실을 나간 상근이 (BOJ 2825 JAVA) https://www.acmicpc.net/problem/2825 알고리즘 분류랑 솔브닥 티어 표시 끄고, 문제 검색 옵션에서 실~플로 랜덤으로 나오게 하고 문제푸니 쫄깃하게 재밌다. 이건 처음엔 실버상위~골드하위 정도일줄 알았는데, 생각할수록 최소 골드 중간쯤은 될꺼란 생각이 들었다.. 처음엔 단순하게 1이 포함된 숫자 리스트, 2가 포함된 숫자 리스트, ... 이렇게 분류해서 union-find나 각 쌍을 hashset에 넣으면서 nCr로 계산하면 될 것 같았다. 하지만 아무리 생각해봐도 시간복잡도를 O(N^2)에서 줄일수가 없었다. 이쯤에서 실~골하위는 아닐꺼라 일단 생각이 들었다 ㅋㅋ N이 100만개이므로 O(N^2) 풀이는 아예 불가하고, 못해도 O(NlogN) 정도 수준으로 생각해내야 한다. .. 2021. 10. 2.

티스토리툴바