백준133 [백준 1655] 가운데를 말해요 / 자바 / 우선순위 큐 #문제 레벨: G2알고리즘: 자료구조 (우선순위 큐)풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1655#문제 풀이 이 문제를 봤을 때 한 번에 떠올리는 아이디어로 한다면 시간초과가 날 것이다. 입력을 받을 때마다 정렬을 하고 중간값을 찾는 다는 생각은 오답이다. 배열 정렬의 최선의 시간복잡도는 O(n)이고 최악은 O(n^2)이다. 그래서 우리는 더 나은 정렬된 자료구조를 사용해야 한다. 그건 정렬의 특화된 우선순위 큐이다. 우선순위 큐 정렬(Heap정렬 사용)의 시간복잡도는 O(logn)이다.아이디어는 이러하다. 중간값보다 낮은 숫자들을 담을 maxHeap과 중간값보다 높은 숫자들을 담을 minHeap을 생성한다. maxHeap은.. 2024. 7. 20. [백준 14889] 스타트와 링크 / 자바 /dfs #문제 레벨: S1알고리즘: dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14889 #문제 풀이 dfs로 조합을 구한 후 조합이 완성될 때마다 답의 최솟값을 구하면 되는 쉬운 문제이다. 설명은 생략하겠다.#배운 점 dfs함수는 사람마다 구현하는 게 다 다르다. visited[] = true 순서이다. 재귀호출 전 true만들기 dfs(int i) { for (int j = i; j 재귀호출 후 첫 코드에서 true만들기 dfs(int i) { visited[] =true; for (int j = i; j 이것도 사고의 흐름이 편한대로 작성하면 될 것이다. 자기만의 d.. 2024. 7. 18. [백준 2573] 빙산 / 자바 / dfs #문제 레벨: G4알고리즘: dfs풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2573 #문제 풀이 이 문제는 두가지를 구현하면 되는 문제이다.1. 빙산의 개수 카운팅 함수2. 빙산을 녹이는 함수하지만 난 보다시피 dfs가 간접적으로 빙하를 카운팅 하는데 도움을 주면서 빙하를 녹였다. 원래 내생각에는 한번 배열을 순회하는 김에 다 처리하자. 그게 성능상 이점을 가져갈 것 같다였다. 그러나 두가지 일을 동시에 하는 코드를 짜니 코드를 짜기 복잡했다.그래서 위에 쓴 과정처럼 논리의 흐름대로 코드를 짰다.#풀이 코드 import java.io.*;import java.util.*;public class Main { st.. 2024. 7. 17. [백준 13023] ABCDE / 자바 / dfs #문제 레벨: G5알고리즘:dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/13023 #문제 풀이 이 문제에 key point는 dfs 경로를 다양하게 탐색할 수 있느냐이다. 보통은 그래프에서 dfs를 사용할 때 연관된 노드들을 모두 방문한다에 포커스가 맞춰져 있다. 그러나 이 문제는 경로에 포커스가 맞춰져있다. 그래서 우리는 dfs 함수 중 boolean[] = false 이 부분을 잘 봐야 한다. 이것 덕분에 이전dfs 경로에서 탐색했던 노드들도 다시 탐색하게 되는 것이다.#풀이 코드 import java.io.BufferedReader;import java.io.IOException;import java.io.I.. 2024. 7. 16. [백준 9466] 텀 프로젝트 / 자바 / dfs + cycle #문제 레벨: G3알고리즘: dfs + cycle풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/9466#문제 풀이 본 유형은 나에게는 신유형이다. 보통 dfs라면 cycle를 돌지 않고 한 번 간 곳은 visited[] 배열로 방문하지 않는다. 그러나 이 문제는 done[] 배열을 만들어 두 번 순회하여 dfs를 마친다. 한 번 순회로 dfs를 마칠 수 있지 않나? (그럴 수도 있을 것 같긴 하다..) 그러나. 가볍게 이해하기 위해서는 dfs를 두 번 도는 것이 좋다. 한 번 돌 때는 연결고리를 만드는 과정이고 두 번 순회할 때는 cycle인지 판별하여 팀원인지 가려내기 위함이다. #풀이 코드 import java.io.Bu.. 2024. 7. 15. [백준 2533] 사회망 서비스 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2533#문제 풀이 dp와 dfs를 섞은 문제이다. 이 문제에서 얻을 수 있는 점은 두가지이다.첫 째, 그래프를 배열로 표현하는 것. 둘 째, 큰 문제를 작은 문제로 쪼개는 방법.셋 째, vistied배열 대신 parentNode로 판별하는 방법(중복 탐색 예방)넷 째, dp 구현방식위 문제는 dp[node][0], dp[node][1]를 가지는 이차원 배열로 풀어내야 한다. 가장 아래에 있는 리프 노트부터 시작하여 루트 노드의 dp 값을 채우는 방식이다. 예를 들면 dp[5][0] 은 노드 5가 얼리어답터가 아닐 때이다. 그러니 반드시 부모(.. 2024. 7. 11. [백준 1937] 욕심쟁이 판다 / 자바 /dp #문제 레벨: G3알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1937#문제 풀이 위 문제를 순수 dfs 코드로 풀면 O(n x n x n x n)입니다. 값을 대입해보면 500 x 500 x 500 x 500 = 625억입니다. 시간제한은 2초이므로 2억 초과인 625억은 시간제한 초과입니다. 특별한 규칙이 없으니 dfs임은 확실하고 시간복잡도를 줄이기 위해서 dp를 도입해야 합니다. dp를 도입한다는 것은 이미 방문한 경로는 반복해서 가지 않는 것을 의미합니다. 그럼 각 배열을 한 번씩만 방문하면 되기 때문에 시간 복잡도는 O(n x n)입니다. 이만 오천으로 넉넉히 통과할 수 있습니다. (한 번씩만 방문하면 되므로.. 2024. 7. 10. [백준 11066] 파일 합치기 / 자바 /dp #문제 레벨: G5알고리즘: dp 풀이시간: 1힌트 참조 유무:https://www.acmicpc.net/problem/11066#문제 풀이 그리드 문제로도 착각할 수 있지만 연속된 파일들만 합칠 수 있기 때문에 그리드 문제는 아니다. (그리드 문제라면 파일을 합치고 정렬하고 합치고를 반복하기 때문에 연속된 파일임을 보장하지 않음) dp[i][j] = i ~ j까지 파일 합쳤을 때 최솟값+행은 시작인덱스를 나타내고 열은 끝인덱스를 나타낸다.{2,3}이면 2에서부터 3까지 더했을 때 최솟값이다. dp 배열을 이 방향으로 채워진다. 빨간색 숫자는 채워지는 순서를 뜻한다. 아래 코드르 보면 알겠지만 이중 for문이 뜻하는 것은 파란색 방향을 말하는 것이다.가장 깊숙히 있는 fo.. 2024. 7. 10. [백준 14002] 가장 긴 증가하는 부분 수열4 / 자바 / dp #문제 레벨: G4알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14002#문제 풀이 [1번째 시도: 실패]멍청한 풀이. 시간복잡도 n으로 풀 수 있지 않을까? 그리드 형식으로 랭킹을 매기는 방식. 혹시 나와 같은 사람이 있을까봐 기입해두었다. skip해도 된다.package project;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(.. 2024. 7. 10. 이전 1 ··· 5 6 7 8 9 10 11 ··· 15 다음
