알고리즘 문제 풀이 53

백준 1766 문제집 (JAVA 자바)

문제 출처 - www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 유형 - 위상 정렬 문제는 단순 위상 정렬인데 이제 문제 조건 중에 쉬운 문제부터 풀어야한다는 조건이 있다. 그러니까 문제에서 주어진 테케 경우에 저 조건이 4 2 3 1라면 4 3 2 1 이렇게 풀 수도 있지만 저 조건 떄문에 3 1 4 2 이렇게 풀어야 한다. 맨 처음에는 위상정렬 + DFS로 풀까 하고 생각했는데 일이 좀 커질 것 같았다. 그래서 그냥 큐가..

BJ16948 데스나이트(JAVA 자바)

문제 출처: www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 문제 유형: BFS import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.String..

백준 2252 줄 세우기 (JAVA 자바)

문제 출처 - www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제 유형 : 위상 정렬 문제 접근: 처음엔 인접 행렬로 접근했는데 메모리 초과가 떴다. arraylist를 활용한 인접 리스트로 푸니 맞힐 수 있었다. 그래프 문제는 대부분 인접리스트로 푸는게 유리한 것 같다. import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import..

백준 16235 나무 재테크(Java 자바)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Scanner; import java.util.StringTokenizer; public class bj16235_나무재테크 { static int map[][]; static int nutri[][]; // 겨울에 S2D2가 양분 줄 거 저장해둔 배열 static int N, M, K; // N 맵 크기 M 나무 수 K 햇수 static int x, y, ..