알고리즘/백준

최근에 MST를 공부해서 MST 뿌수기 시리즈를 해보려고 한다. 6497 전력난 - 골드4 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 전체 간선의 길이가 최소가 되어야한다 최소 스패닝 트리를 생각할 수 있음 그냥 최소스패닝 트리를 잘 만들면 되겠다. 길의 수가 적다고 정해져있지 않으니 크루스칼, 프림 아무거나 해도 될 것 같다. Prim 알고리즘 풀이 class Node implements Comparable { int end; int distanc..

보호되어 있는 글입니다.

대망의 구현 뿌수기다. 가장 기본이면서 가장 중요하고 문제도 가장 많다. 긴 여정이 될 것 같다. 2167 2차원 배열의 합 - 실버5 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 누적합 냄새가 너무 나서 그렇게 풀었다 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffe..

비트마스킹 시즌2다. 비트마스킹은 뿌수기 시리즈 중 가장 어렵다고 느껴진다.. 비트마스킹이 내 취약점인 것 같다. 더 열심히해야지.. 17419 비트가 넘쳐흘러 - 실버4 https://www.acmicpc.net/problem/17419 17419번: 비트가 넘쳐흘러 🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶 DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다! N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용 www.acmicpc.net 0이 될 때까지 계속 연산을 반복하면 시간초과가 날 것 같았지만, 규칙이 떠오르지 않아서 그냥 해봤다가 51%에서 안움직였다 N의 개수가 100만이었기 때문에 long으로도 처리가 안된 것이었다 어쩔 수 없이 규칙을..

13023 ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 친구관계와 관련되어 있어서 union-find인가 생각도 들었지만, A-B-C-D-E 로 이어져야하고, 네트워크와는 관련이 없기 때문에 다른 방식으로 풀어야한다는 걸 느꼈다 4만큼 떨어져있다면 촌수계산처럼 bfs로 푸는 게 맞나 싶었지만, visit관리를 어떻게 해야할 지 몰라 dfs로 풀었다. class Man { int num; int count; public Man(int num, int count) { this.num = num; this.count = count; } } ..

이전글 https://fladi.tistory.com/405 [JAVA] 백준 트리 뿌수기1 다익스트라에 이어 트리를 뿌숴보겠다. bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다. 이번에는 트리를 정복해보겠다. 트리(tree)란? 계층적 자료를 표현하는데 fladi.tistory.com https://fladi.tistory.com/406 [JAVA] 백준 트리 뿌수기2 이전글 https://fladi.tistory.com/405 [JAVA] 백준 트리 뿌수기1 다익스트라에 이어 트리를 뿌숴보겠다. bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다. 이번에는 트리를 fladi.tistory.com https://fladi..

이전글 https://fladi.tistory.com/405 [JAVA] 백준 트리 뿌수기1 다익스트라에 이어 트리를 뿌숴보겠다. bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다. 이번에는 트리를 정복해보겠다. 트리(tree)란? 계층적 자료를 표현하는데 fladi.tistory.com https://fladi.tistory.com/406 [JAVA] 백준 트리 뿌수기2 이전글 https://fladi.tistory.com/405 [JAVA] 백준 트리 뿌수기1 다익스트라에 이어 트리를 뿌숴보겠다. bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다. 이번에는 트리를 fladi.tistory.com 트리부수기 시즌3이다! ..

이전글 https://fladi.tistory.com/405 [JAVA] 백준 트리 뿌수기1 다익스트라에 이어 트리를 뿌숴보겠다. bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다. 이번에는 트리를 정복해보겠다. 트리(tree)란? 계층적 자료를 표현하는데 fladi.tistory.com 트리 부수기 2탄이다! 아직 트리부분이 많이 부족해서 얼른 성장하고싶다 20364 부동산 다툼 - 실버1 https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N

다익스트라에 이어 트리를 뿌숴보겠다. bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다. 이번에는 트리를 정복해보겠다. 트리(tree)란? 계층적 자료를 표현하는데 사용되는 자료구조 구성요소 루트노드 단말노드 비단말노드 간선 차수 = 자식개수 레벨 = 루트부터 1 시작 트리높이 = 최대레벨 forest = 트리들 집합 종류 포화 이진트리 = 각 레벨에 노드가 꽉 차있음 완전이진트리 = 왼쪽부터 오른쪽으로 노드가 차있는 트리 트리순회 전위순회: 중 왼 오 중위순회: 왼 중 오 후위순회: 왼 오 중 최소신장트리(MST, Minimum Spanning Tree) 최소 연결 부분그래프 모든 정점을 연결시키고, 사이클을 포함해서는 안됨 가중치의 합이 최소/ n-1개의 간선..

2151 거울 설치 - 골드3 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 진짜 감도 안잡혀서 구글링 후 답을 봤는데도 납득이 안간다 이 경우에 답이 나와야하는데, 다른 사람들이 올린 정답코드는 왜 이 경우를 고려하지않을까? 거울 반사각을 생각하면 대각선의 경우도 고려해야하는 게 아닌가? 짜증난다 다른 사람의 풀이를 보면 그냥 수직/ 수평만 고려하고, 반사하는 경우 90도 꺾기만 한다. 문제 어디에 수직/수평으로만 진행된다고되어..