본문 바로가기
반응형

ProgramSoliving

 (197)
백준 : 18248 감시피하기 www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 감시 피하기 분류 : 완전탐색 N= N || nx >= N) break; if (map[ny][nx] == 'O' || map[ny][nx] == 'T') break; if (map[ny][nx] == 'S') return true; } } return false; } }
백준 : 4256 트리 www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 전위 순회 : root , 왼쪽 ,오른쪽 중위 순회 : 왼쪽 root 오른쪽 후위 순회 : 왼쪽 오른쪽 root 주어지는건 전위와 중위이다. 전위 특징 : 첫번째에 root가 나온다. 따라서 전위 순회에서 맨앞은 후위 순회에서 맨뒤에 나온다. 이젠 전위 순회를 왼쪽 지점 오른쪽 지점을 다시 새로운 전위순회로 쪼개주면됨.. 따라서 중위순회에서 root값을 스택형식으로 출력하면서 그 root값 중심으로 ..
백준 : 17182 우주 탐사선 www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 1. 플로이드 와샬로 각각의 에지에서 다른 에지로가는 최소비용 구하기 2. flag라는 현재 방문한 상태자체를 int형으로해서 보낸다 (N
백준 : 14466 소가 길을 건넌 이유 www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 문제유형 : 다익스트라 , 플로이드와샬 O(NM)이기때문에 다익스트라가 효율성이 더좋을거 같다. 문제의 아이디어는 소가잇는길을 가중치1 그이외에는 0으로 두고 다익스트라를 구한다. 그리고 소가 하나의 엣지에서 다른엣지로 가는길이 0이아닌 값이 무조건 다리를 건너야하는 경우다. 각각의 엣지에서 0이 아닌값을 구하면 a,b쌍 ,b,a 쌍이 나오므로 나머지 2를 해주면 정답..
백준 : 1800 인터넷 설치 JAVA www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 문제유형 : 이분탐색, 다잌스트라 접근 아이디어 : 다잌스트라에 특정 x값 이하로 이을수 있나 탐색 x값 이하면 비용 0 x값 초과시 비용1이라고한다면 x값 초과하는 연결선의 개수를 알게된다. 그 개수가 K이면은 true 이렇게 함수를 만들고 이분탐색 하면된다. package boj; import java.io.BufferedReader; import java.io.IO..
백준 : 16639 괄호추가하기 3 문제유형 : dp dp[i][j]는 i~j구간의 최대값, 최소값을 구한다. 각구간에 대한 최소값과 최대값을 구한다. ( a - b) 음수구간때문에 최소값을 뺄때가 최대값일 수 있음. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Boj16639 { static int N; static int dpMax[][]; static int dpMin[][]; public static void main(String[] args) throws IOException { BufferedReader br = new..
백준 : 18500 미네랄 www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 문제 유형 : 시뮬레이션 방법 : list하나를 클러스트라생각하고 진행. 리스트에 담을때 Map값을 리셋시켜서 클러스트 단위별로 내려가는지를 체크한다음 할당. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java...
백준 : 17780 새로운게임 www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제유형 : 시뮬레이션 새로운 게임2와 똑같은문제인데 조건에 가장 밑에있는 말들만 움직일 수 있다는 조건 추가. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; impo..
반응형

티스토리툴바