백준 썸네일형 리스트형 [백준 14466] 소가 길을 건너간 이유 6 (Java) 문제 링크 : www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 풀이 소의 위치를 시작점으로 하여 BFS를 통해 목초지를 탐색하되, 다리가 존재하는 경우는 탐색하지 않도록한다. 탐색이 끝나고 다른 소 위치에 대한 방문 여부를 체크하는데 이 때 방문이 되지 않은 경우는 다리를 지나지 않으면 만날 수 없다는 것을 의미하기 때문에 해당 경우를 모두 찾으면 된다. 2차원 int 배열 map은 BFS탐색을 할 목초지로 소 위치.. [백준 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 풀이 이분 탐색 + 다익스트라 응용 문제로 개인적으로 많이 어렵게 느껴졌던 문제였다. (나중에 다시 한 번 풀어볼만한 문제) 참고한 블로그에 설명이 잘 나와 참고하여 풀었다. [참고] - batory.tistory.com/371 - justicehui.github.io/usaco/2019/07/12/BOJ1800/ 코드 import java.io.Buffe.. [백준 16639] 괄호 추가하기 3 (Java) 문제 링크 : www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 dfs로 완탐하는 방식으로 시도하다가 경우가 너무 많아서 자력으로 풀지 못했다. 다른 분의 블로그를 참고하여 해결할 수 있었다. DP 방식을 통해 풀이가 가능했는데, 2차원 배열을 생성하고 i번 째부터 j번 째 숫자들을 포함한 연산 결과들의 최솟값, 최댓값을 구했다. 최종적으로 최댓값을 구하는 것이지만, 연산 숫자가 음수 * 음수 인 경우 최댓값의 후보가 될 수 있기 때문.. [백준 17780] 새로운 게임 (Java) 문제 www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 풀이 크게 체스판에 대한 데이터, 체스말(Node)에 대한 데이터, 쌓여있는 체스말에 대한 데이터를 어떻게 저장할 것인지 고민했다. - 체스판에 대한 데이터(빨, 파, 흰)는 2차원 int 배열로 입력 받는 그대로 저장한다. - 체스말에 대한 데이터는 x, y좌표 값과 방향 값을 필드 데이터로 갖는 Node 객체를 생성해 ArrayList에 저장하였다. (방향 별 이동을 쉽게 하기 위해 dir_x, dir.. [백준 15591] MooTube (Silver) (Java) www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 그래프 문제라고 2차원 배열을 사용하면 시간 초과가 발생한다. 불필요한 연결을 탐색하기 때문에 ArrayList를 담는 배열을 만들어 입력 받은 연결만 탐색하도록 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor.. [백준 3197] 백조의 호수 (Java) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 풀이 문제를 처음 보고 다음과 같은 방법으로 시도를 했다. 1. BFS로 얼음을 녹이고 map을 업데이트 시킨다. 2. 해당 map에서 두 백조가 만날 수 있는지 BFS 탐색을 시도한다. 3. 만날 수 없다면 day++를 하고 1, 2번을 반복한다. 4. 만나는 경우에 day를 출력한다. 위 방법으로는 시간 초과가 발생할 수 있다. 예를 들어 백조가 만날 수 있는 날이 n일차라면 (이 n이 아주 .. [백준 1665] 가운데를 말해요 (Java) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 배열이나 ArrayList를 이용하여 풀이를 시도하였더니 메모리초과, 시간초과 문제가 발생했다. MaxHeap, MinHeap 개념을 이용하여 문제를 풀었다. (Heap은 PriorityQueue로 구현) 입력받는 숫자를 MaxHeap과 MinHeap에 번갈아 가면서 add를 하되, MaxHeap의 첫번째 값과 MinHeap의 첫번째 값을 비교했을 때 (MaxHaep.peek.. [백준 1976] 여행 가자 (Java) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 union-find 알고리즘을 이용해 푸는 문제였다. int[][] map : 입력받은 도시 간 연결을 나타내는 행렬을 담음 int[] route : 여행자의 이동 경로 도시 번호를 담음 int[] join : 도시 간 집합 index를 담음. 집합 원소 중 가장 도시 번호가 작은 번호 기준으로 담김. map을 탐색해 1인 경우의 좌표값 i, j를 기준으로 union()메소드에서 집합을 합친.. 이전 1 2 3 4 ··· 6 다음 목록 더보기
