본문 바로가기

CS ﹒ Algorithm/Baekjoon

Java 백준 문제풀이 (55) 1167_트리의 지름
CS ﹒ Algorithm/Baekjoon 2022. 10. 21. Java 백준 문제풀이 (55) 1167_트리의 지름 한동안 티스토리 서버가 날아간 덕분에 문제 풀고 풀이를 못 올렸는데 정말 문제 푼 것 같지가 않았다.. ㅎ 오늘의 문제는 트리의 지름이다. 문제를 읽자마자 작성한 나의 주석을 먼저 보자. 1 2 3 4 5 6 7 8 9 10 11 12 // 트리의 지름 ? // 루트에서 가장 먼 노드 n1 n1과 가장 멀리 있는 노드 n2의 거리. // 가중치와 에지 정보가 모두 필요하므로 별도의 Node 클래스가 필요하다. // bfs dfs? dfs를 이상하게 구현하지 않는 이상 큰 의미 없을 듯..? 어차피 완전탐색해야함. // 다만 깊이가 깊어질수록 dfs가 불리해서 굳이 선택하면 bfs가 무난한데 난 dfs가 좋 - 아 // 가장 먼 노드 + 그놈하고 제일 먼 노드 => 두 번 탐색 필요 // 근데 노드가 1번..
Java 백준 문제풀이 (54) 미로 탐색
CS ﹒ Algorithm/Baekjoon 2022. 10. 15. Java 백준 문제풀이 (54) 미로 탐색 기본 중의 기본인 미로 찾기 문제다. 한 번 풀어보고나면 딱히 어려울 건 없지만 2차원 배열을 다루는 만큼 처음부터 생각을 잘 해놓고 시작해야 한다. 1 2 3 // 2차원 배열 길 찾기 문제 특) 상하좌우 이동용 배열 필요함 // 최단거리 문제 특) bfs가 좋다 // 메모리 192MB => 최대값인 int[100][100]으로 2개 만들고 visited[100][100] 만들어도 남아돈다. cs 처음 작성한 주석은 이렇게 세 줄이다. 2차원 배열 길찾기 문제라서 일단 상하좌우 이동용 배열이 필요하다. 1. {1,0,-1,0} . {0,1,0,-1} 이렇게 두 개 있으면 된다. 2. 최단거리 문제는 bfs가 dfs보다 유리하다. 왜일까요? dfs는 조건에 맞지 않으면 처음부터 다시 탐색하는 걸 반복한다..
Java 백준 문제풀이 (53) 13023 _ ABCDE
CS ﹒ Algorithm/Baekjoon 2022. 10. 13. Java 백준 문제풀이 (53) 13023 _ ABCDE 이 문제에서 가장 어려웠던 것은 문제 이해다.. 난 처음 이 문제를 읽고 모든 정점이 한 번에 이어지는 경우의 수를 찾는 것으로 이해해했으나, 그렇게 생각하면 도저히 문제에서 주어지는 예제와 출력이 맞지 않았다. 알고보니 말 그대로 정점 순서 관계 없이 ABCDE, 5개의 정점만 연속으로 이어지면 된다. 나만 바보인가..? 아무튼 풀어보자. 해당 문제를 읽고 전제조건을 먼저 주석으로 작성해보았다. // A,B,C,D,E가 한 번에 이어지는 경우를 찾아야 한다 -> DFS // 깊이가 5면 정답처리하면 될 듯 // 사람 수(정점)은 일반 그래프와 달리 0부터 순서대로 주어지니 주의하자 사실 이번에는 별달리 전제조건을 적어놓을 것들은 없어 보였다. 그냥 DFS로 탐색하는 거고 사람 A,B,C,D,E는 일반 ..
Java 백준 문제풀이 (52) 2023_신기한 소수
CS ﹒ Algorithm/Baekjoon 2022. 10. 12. Java 백준 문제풀이 (52) 2023_신기한 소수 문제 이름을 신기한 소수가 아닌 신기한 수빈이로 바꾸면 좋겠다. 바로 본론으로 들어가서 문제 조건을 정리해보자. 내가 처음 작성한 주석은 다음과 같다. // 신기한 소수 구하기 (모든 자리 수가 소수다) // N의 최대값이 8 -> 즉 입력값의 최대 값이 9999만 // 에라토스테네스의 체로 소수를 구할 경우 400mb(400000000byte)를 차지하는데 문제에서 제시하는 메모리 제한은 4MB // 따라서 매번 소수를 새롭게 구해야 한다. // 모든 경우의 수를 구하는 문제이므로 dfs 난 소수 문제를 풀 때 에라토스테네스의 체를 사용하는 것을 좋아하는데 예전에 메모리 문제로 삽질해본 이후 항상 이런 문제를 보면 문제에서 제시하는 메모리 부터 확인한다. 다만 지금 글을 작성하면서 생각해보니 주석의 내..
Java 백준 문제풀이 (51) 연결 요소의 개수
CS ﹒ Algorithm/Baekjoon 2022. 10. 9. Java 백준 문제풀이 (51) 연결 요소의 개수 간만에 풀어보는 그래프 문제다. 기초가 너무 부족한 것 같아서 한동안 그래프는 거들떠도 안보고 정렬 문제만 풀다가 왔는데, 확실히 그래프 문제를 오랫동안 풀지 않았음에도 예전보다 훨씬 쉽게 느껴진다. 우선 혹시나 애초에 문제가 잘 이해되지 않는 사람을 위해 짧게 설명하겠다. 위와 같이 생긴 게 그래프고, 문제에서 말하는 연결 요소의 개수란 (0-1-2-3-4-5), (6-7) => 2개 이런 식으로 구하라는 말이다. 혹시 그래프 자체를 모른다면 유튜브로 배우고 오자. 이 문제의 전제 조건은 별거 없다. // 방향이 없다. // 1번째 줄 정점 개수 N, 간선 개수 M // 두번째 줄부터 간선의 양 끝점 u, v 방향이 없다는 말은 3에서 5로 갈 수 있으면 5에서도 3으로 갈 수 있다는 뜻이다. 따라서 ..
Java 백준 문제풀이 (50) 1517 _ 버블소트
CS ﹒ Algorithm/Baekjoon 2022. 10. 7. Java 백준 문제풀이 (50) 1517 _ 버블소트 푸는 방법만 알면 거저먹는 문제지만 나는 푸는 방법을 몰라서 조금 헤맸다. 그래도 처음 풀어보는 플래티넘 문제인데 검색할 필요가 없었으니 어지간한 골드 문제보다 쉬웠던 것 같다. 오늘부터는 내가 처음 생각하고 시도하고 틀린 과정, 그리고 잘못 작성했던 주석까지 모조리 올리기로 했다. 이렇게 하면 남들한테 보여줘야하는 것이니 부끄러워서라도 과정 건너뛰지 않고 조금 더 차근차근 풀 수 있지 않을까 싶어서.. 그리고 풀이를 보는 사람도 나처럼 실력이 부족한 사람들은 정답만 보는 것보다 시행착오까지 보는 게 더 도움이 되지 않을까 싶다. 우선 나는 항상 문제의 조건을 읽으면서 바로바로 해당 요구사항을 어떻게 풀이에 적용할지 주석으로 작성한다. 내가 코드 작성 전 작성한 주석은 다음과 같다. // N개의 수로 이..
백준 문제풀이(49) 수 정렬하기2 병합정렬
CS ﹒ Algorithm/Baekjoon 2022. 10. 2. 백준 문제풀이(49) 수 정렬하기2 병합정렬 그냥 원하는 정렬 알고리즘 아무거나 연습하기 좋은 수 정렬하기 문제다. 그리고 난 옛날에 병합 정렬을 공부하다가 어려워서 때려치운 전적이 있다. 따라서 오늘은 병합 정렬이다. 우선 merge sort에 대해 간단하게 알아보고 넘어가자. 자세한 건 직접 찾아보삼 정말 이 그림대로 정렬한다. 우선 재귀를 이용해 최소단위까지 쪼갠 뒤, 수의 크기에 따라 정렬하며 다시 합치면 된다. 그리고 quickSort와 가장 큰 차이점이라면 mergeSort는 기존 배열에서 바로 재정렬하는 것이 아닌 추가 배열을 생성해서 해당 배열에서 먼저 정렬한 뒤 기존 배열에 적용하는 방식이다. 이런 형태다. mergeSort (배열, 인덱스작은놈, 인덱스큰놈) { if (인덱스작은놈 != 큰놈) { int 중간인덱스; mergeSo..
JAVA 백준 문제풀이 (48) ATM
CS ﹒ Algorithm/Baekjoon 2022. 9. 27. JAVA 백준 문제풀이 (48) ATM 별다른 거 없고 오름차순으로 정렬해주고, 누적합 구하면 끝나는 문제다. 정렬에 여러가지 경우의 수가 있는데 왜 별다른 거 없냐고 할 수도 있는데, 병합 정렬이나 퀵 정렬 삽입 정렬 중에 원하는 거 아무거나 사용해도 다 통과된다. 이 이상은 귀찮아서 테스트 안해봤다. 그 말은 즉 그냥 Arrays.sort()로도 다 된다는 말입니다.. 아무튼 그렇게 풀면 재미도 없고 공부도 안되니까 최대한 직접 삽질하면서 풀어보자 우선 정렬은 어떻게 해야할까? O(nlogn)의 시간 복잡도를 가진 퀵 정렬이나 병합 정렬을 구현해도 되지만 쓸 게 많아서 귀찮다. 사람 수가 1000명이기 때문에 시간 복잡도가 O(N^2)여도 별 문제가 안된다. 충분히 1초안에 가능한 수준의 연산이다. 따라서 나는 입력값을 받음과 동시에 정렬..

티스토리툴바