분류 전체보기 (119) 썸네일형 리스트형 [백준] 15681 트리와 쿼리 문제링크: www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 너무 많이 풀어본 유형이라 쉬웠다. 문제 설명이 아주 구체적이어서 그래프와 트리의 개념을 이해하기에 좋고, 그것을 실습 해보는 목적으로 풀기에 좋은 문제인 것 같다. import java.io.*; import java.util.*; public class Main { public static int N,R,Q; public static .. [백준] 7579 앱 문제링크: www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 1년 전에 풀다가 실패했던 문제다. 다시 풀려고 했는데 나아진 게 없는지 잘 풀리지 않았다. 반성했다. 그때 답을 보고도, 제대로 이해하지 않고 넘어갔던 것 같다. 이번 기회에 차근차근 이해 해보려 했다. 또, 재귀 호출을 통한 메모이제이션 방법이 떠오르지 않아서 bottom-up 방식으로 풀었지만 검색해보니까 재귀로 해결한 코드가 있었다. bottom-up을 어려워 하는 내겐 좋은 공부가 됐다. 다음번엔 .. [백준] 11066 파일 합치기 문제링크: gaegosoo.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F TISTORY 나를 표현하는 블로그를 만들어보세요. www.tistory.com 문제를 풀 때 항상 완전탐색을 먼저 고려해본다. 부분 문제로 나눌 수 있는게 직관적으로 보여서 그렇게 풀었다. 리턴이 많아서 깔끔해 보이진 않지만 예외 없이 한번에 통과하는 코드를 짜고자 할때 나오는 습관이다. import java.io.*; import java.util.*; public class Main { public static int N; public static int []arr; public static int[][] dp; public static final i.. [백준] 1956 운동 문제링크: www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제를 보자마자 플로이드 워셜로 모든 경로를 저장할 수 있다는 것을 알았다. N이 400이기 때문이다. 정답을 제출한 다음 이것보다 더 빠른 속도를 보이는 풀이를 보니 배열을 초기화 할 때 Arrays.fill을 쓰는 것 같았다. 나도 넣어줬더니 제출결과가 30% 빠르게 나왔다. import java.io.*; import java.util.*; public clas.. [백준] 1504 특정한 최단 경로 문제링크: www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 난 다익스트라를 조금만 응용해도 감을 못잡는 경우가 있는 것 같다. 최단경로 문제를 조금 더 풀어봐야겠다. 최단경로 문제는 재밌기도 하고. 어쨌든 위 문제는 시작점 세 군데에 대해 다익스트라를 수행하면서 정보를 저장했다. 1번 시작점에서 갈 수 있는 모든 최단거리 반드시 들러야 하는 두 곳을 시작점으로 갈 수 있는 최단거리를 저장했다. 이 과정에서 이미 저.. [백준] 11286 절대값 힙 문제링크: www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 큐 두 개를 활용해서 해결했다. 코드가 긴 것 같아서 다른 사람의 풀이를 보니 우선순위 큐 하나로 담길 정보에 절대값, 원본값 두개를 같이 담아서 절대값으로 비교하고 원본값을 출력하는 방법을 사용하더라 그게 더 깔끔할 것 같다 import java.io.*; import java.util.*; public class Main { public static void main(Stri.. [백준] 1927 최소 힙 문제링크: www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int loop = Integer.parseI.. [백준] 11279 최대 힙 문제링크: www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 자바의 priorityQueue는 기본적으로 최소힙으로 구현되어 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReade.. 이전 1 ··· 9 10 11 12 13 14 15 다음