메이쁘

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 안녕하세요. 이 문제는 Sliding Window 와 DP를 활용했습니다. 그냥 DP만 사용해도 되지만, 문제 조건을 보면 1초와 메모리 제한이 4MB 이기 때문에 모든 숫자를 배열로 담고 활용할 수 없습니다. 그래서 슬라이딩 윈도우 를 사용해야 합니다. 근데 문제를 보면 한 줄씩 확인해서 DP로 최댓값, 최솟값을 구하기만 하면 굳이 이전 값을 알 필요가 없습니다. 즉, DP[i][k] 2차원 배열이 있다고 할..

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net 안녕하세요. 단일 노드 -> 단일 노드 의 최단 경로(시간)를 구하는 문제이기 때문에, 다익스트라와 DP를 사용했습니다. 왜 다익스트라와 DP를 사용해야 하느냐? https://dragon-h.tistory.com/26?category=789780 위의 포스팅을 참고해서 이유를 적어봤습니다. ------------------------------------..

https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 안녕하세요. 슬라이딩 윈도우 문제입니다. 참고로, 정답은 맞는데 시간 초과로 실패했습니다. 통과된 코드를 제출해봐도 시간 초과가 떠서 포기했습니다. 그렇지만 소스코드가 틀리진 않기 때문에 이 문제를 포스팅해보려고 합니다. *** 슬라이딩 윈도우에 대해 짚고 넘어가고 싶으시면 아래 포스팅을 참고해주시면 감사하겠습니다. https://maivve.tistory.com/..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 안녕하세요. 이 문제는 우선순위 큐를 활용한 슬라이딩 윈도우 문제 입니다. 보통 슬라이딩 윈도우 == 투포인터 라고 생각하시는데, 반은 맞고 반은 틀립니다. 투 포인터와 슬라이딩 윈도우는 배열의 처음부터 순차적으로 탐색하고 부분 배열을 꺼내보는 것은 같습니다만 투 포인터는 부분 배열의 길이가 가변적(늘었다 줄었다) 이지만 슬라이딩 윈도우는 부분 배열의 길이가 고정적(일정) 입니다. 그렇기 때문에, 문제 ..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 안녕하세요. 투포인터의 기초 문제 입니다. 투포인터 알고리즘에 대해서는 별도의 포스팅에서 다뤄보겠습니다. 이 분이 작성하신 포스팅이 이해하는데 큰 도움이 되서 한 번 링크 적어봤습니다! https://code0xff.tistory.com/128?category=723754 17. 투 포인터, 슬라이딩 윈도우 (1) 투 포인터와 슬라이딩 윈도우는 비교적 간단한 알고리즘이지..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 � www.acmicpc.net 안녕하세요. 문제 이름을 들으면 알 수 있듯이 플로이드 - 와샬 알고리즘을 사용하는 기본 문제입니다. 플로이드 와샬 알고리즘에 대해서는 별도로 정리할 예정이지만, 정의만 간단하게 말하면 모든 노드 -> 모든 노드 로 가는 최단 거리 를 2차원 배열로 정리하는 알고리즘입니다. 추가로, 거쳐가는 모든 경유 지점까지 고려해서 도출한 최단거리 라고 생각하시면 됩니다. 알고리..

https://www.acmicpc.net/problem/2420 2420번: 사파리월드 첫째 줄에 두 도메인의 유명도 N과 M이 주어진다. (-2,000,000,000 ≤ N, M ≤ 2,000,000,000) www.acmicpc.net 안녕하세요. (|N - M|) 을 구하는 문제입니다. 왜 정답률이 낮은지 모르겠는데, 저에게는 쉬웠습니다. Math.abs(N + ((M) * (-1))) 하면 됩니다. 아, 그리고 N과 M, 위의 계산 결과 값은 int 범위를 초과하기 때문에 꼭 long 타입을 사용해야 합니다. 감사합니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

https://www.acmicpc.net/problem/1076 1076번: 저항 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 색은 모두 위의 표에 쓰여 있는 색만 주어진다. www.acmicpc.net 안녕하세요. 구현 문제인데, 매우 쉽습니다. 저는 굳이 HashMap을 써서 풀었는데(공부할 겸, 복습할 겸) 어차피 색깔의 값이 순차증가하기 때문에 이를 인덱스로 생각해서 String 배열 만들어서 원소를 곱으로 넣던가 더 단순하게 함수 하나 써서 switch 만들어도 됩니다. 그럼 끗! 감사합니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream..

https://www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net 정답률에 낚인 문제. 너무 쉬웠다. 내 생각에는 long 을 사용하지 않고 int를 사용해서 틀린 사람들이 많은 것 같다. 풀이는 단순하다. AB + CD 인데, A 문자열과 B 문자열을 합친 숫자는 int 범위를 초과한다. CD도 마찬가지. 그래서, 각각의 변수 타입은 long 이고, 두 값을 더한 값 또한 long 이다. 끝! 이상입니다. 감사합니다. *** 아래 로직으로 진행해도 됩니다! 소스코드

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절� www.acmicpc.net 안녕하세요. DFS 관련 문제 입니다. (완전탐색 느낌도 있음) 이 문제를 푸는데 오래걸렸습니다. 풀이 방법은 떠올랐는데, 예외에 대한 처리를 하지 못하는 상황이어서 결국 해설을 조금 참고했었습니다. 이 문제의 핵심은 바로 사이클 입니다. 첫 번째 카드들은 1,2,3 ... n 이렇게 순차적이고, 두 번째 카드들은 임의의 1~n 까지 숫자 입니다. 첫 번째 카드들 중 뽑은 숫자들과 ..