백준

평생 못 갈 줄 알았던 플레가 되었다! 기념으로 후기 글을 써보려고 한다. 참고로 여기서 말하는 공부방법은 개인적으로 도움이 됐던 공부방법을 공유하는 거라 이 방법이 다른사람에게는 정답이 아닐 수 있다. 참고용으로만 읽고 자신과 잘 맞는 공부방법을 찾는 게 좋을 것 같다. 글쓴이는 알고리즘 관련 강의를 하나도 사지 않았고, 알고리즘 유형들은 대학교 수업에서 많이 접해서 어느정도 아는 수준이었다.(돌아가는 로직만 알고 코드는 짤 줄 몰랐다) 공부기간(2023.7 ~ 2024.2) 브론즈 문제를 찔끔찔끔 풀다가 작년(2023) 7월쯤부터 본격적으로 공부를 시작했다. 이후 개발동아리를 하면서 조금 손을 놓고있다가 9월 중반부터 싸피입과 전까지 계속 알고리즘을 공부했다. 싸피 입과 후에는 알고리즘 스터디를 하면..

이전 글(Union-Find 정리 글) https://fladi.tistory.com/348 [JAVA] Disjoint Set과 Union-Find 알고리즘(백준 1717 집합의 표현) 서론 백준 1717번 문제를 몇 시간동안 못풀어서 결국 구글링을 해봤는데, 이 문제는 Union-find알고리즘을 써야한다는 걸 알게되었다. Union-Find 알고리즘을 처음 접했을 땐 너무 참신해서 짜릿했다! fladi.tistory.com 이전에 Union-Find 알고리즘에 대해 공부했다 활용문제를 조금 더 풀고싶어 비슷한 문제를 풀어보려고 한다! 4195 친구 네트워크 - 골드2 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진..

서론 백준 1717번 문제를 몇 시간동안 못풀어서 결국 구글링을 해봤는데, 이 문제는 Union-find알고리즘을 써야한다는 걸 알게되었다. Union-Find 알고리즘을 처음 접했을 땐 너무 참신해서 짜릿했다! 이 알고리즘을 정리해두면 나중에도 유용하게 쓰일 것 같아 글을 포스팅한다 Disjoint Set(서로소 집합)이란? Union-find 알고리즘은 Disjoint set을 표현할 때 사용된다 Disjoint는 "뿔뿔이 흩어지다"라는 뜻이다 Disjoint set은 공통원소가 없는 집합을 뜻한다 (백준 1717번 문제는 Disjoint Set이 주어진다) Union-Find 알고리즘이란? Disjoint Set(서로소 집합)을 효율적으로 표현하는 알고리즘이다 집합을 트리구조로 표현한다 각 값이 자..

24416 알고리즘 수업 - 피보나치 수 1 - 브론즈1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 그냥 하라는대로 따라가면 된다. 의사코드만 잘 구현하면 될듯 dp가 재귀호출보다 성능이 좋다는 걸 알려주려는 듯 하다 한 번 구한 값을 재활용하는 dp와 달리 필요할 때마다 계속 값을 구해야하는 재귀호출이 훨씬 성능이 나쁜 것을 알 수 있음 풀이 class Main { static int cnt1 = 0; static int ..

Dynamic programming(동적계획법)이란? 1950년대 Richard Bellman에 의해 개발된 알고리즘 패러다임 복잡한 문제를 더 간단한 하위 문제로 분해하여 단순화하는 것을 의미 간단한 문제의 해를 구하고, 이를 이용하여 복잡한 문제를 푼다 동적계획법 문제는 두 가지 특성을 가진다 1. 최적의 하위 구조 최적화 문제에 대한 솔루션이 해당 하위 문제에 대한 최적 솔루션의 조합으로 얻어낼 수 있다 작은 문제로 큰 문제를 해결할 때 사용되는 관계가 존재하고, 이를 함축적 순서라고 한다 2. 중첩되는 하위 문제 동적계획 알고리즘은 분할 정복 알고리즘과 구분된다 분할 정복 알고리즘은 해결이 어려운 문제를 분할하여 문제를 해결한다는 점에서 동적계획법과 비슷하지만 차이점이 존재한다. 동적계획법은 하위..

어느정도 이진탐색 기본기를 다진 것 같으니 활용을 열심히 해보자! 2512 예산 - 실버2 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 처음부터 배정이 가능한 경우 -> 예산의 최댓값 출력 배정 불가능 경우 -> 상한액 출력 그냥 상한액을 이진탐색으로 찾는다고 생각하면 되겠다 배정이 가능하면 오른쪽을 탐색, 배정이 불가능하면 왼쪽 탐색 [가능, 가능, 가능, 불가능, 불가능, ...] 이런식으로 나올 것이니 upperbound값을 구하..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 체스를 안한 지 오래돼서 퀸이 갈 수 있는 곳이 기억안났음. 구글링 해봤다 딱히 규칙이 보이지 않음. visit배열과 백트래킹을 사용해야겠다고 생각함. 1행의 모든 칸에 대해 퀸이 놓였다고 생각하고 다음 놓을 수 있는 자리에 퀸을 놓기 (visit = true) 퀸이 놓인 행은 올킬이니까 다음 행부터 빠르게 찾기(가지치기) 행마다 한 개씩 안놓이면 N개의 queen을 놓을 수 없음 -> 가지치기 풀이 public..

https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 규칙도 전혀 없고, 계산하다 중간에 멈추고 가지치기할 만한 규칙도 보이지 않는다. 그냥 다 구해서 완전제곱수를 찾아 최대인지 비교하는 게 최선일 것 같다. 최대 9x9 배열이고 -> 81 step은 최대 -8부터 8까지 될 수 있음 -> 최대 1~8 81 x 8 x 8 = 5184 5184 정도의 경우의 수면... 다 비교하는 게 나쁘지 않을 지도 모르겠다. 완전제곱수인지 판별하는 방법은..

https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 가장 먼저 떠오른 방법은 갈 수 있는 길 중 k개를 선택하는 것이었다. 하지만 해당 선택한 길이 이어지는지도 체크해야하는 번거로움이 있었기 때문에 다른 방법을 사용하기로 하였다. 선택한 방법은 백트래킹이고, 가지치기 조건은 다음과 같다. k보다 커지면 가지치기 T를 지나는 경우 가지치기 dfs로 visit배열을 채워가면서 백트래킹하는 방식으로 구현하였다. 백..

https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 문제풀기 전 생각 물건을 쪼개서 넣을 수 있다면 그리디 문제이지만, 사람을 쪼갤 수 없으니 완전탐색이다 최대 가치의 물건을 넣는 배낭문제로 생각할 수 있고 완전탐색 백트래킹 방법으로 생각할 수 있다 배낭문제로 생각하면 배낭의 크기가 체력의 크기(100)이므로, 크지 않은 숫자라서 배낭문제로 풀기 적합하다 세준이의 체력은 최소 1까지만 줄어들 수 있고, 0이나 음수가 되면 안되는거 고려 백트래킹으..