분류 전체보기 (645) 썸네일형 리스트형 백준 : 3109 https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 문제를 보다가 최대의 파이프를 설치하는 경우의수는 출발점에서 미로찾기처럼 위쪽벽을 따라서 파이프를 연결하면 된다는 것을 알았다. 이방법으로 .. 백준 : 2842 JAVA https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 www.acmicpc.net 집배원 한상덕 문제... 문제를 푸는데 사용한 알고리즘은 우체국에서 K를 갈수있는 가를 검증하기 위한 BFS 그리고 java의 Tr.. DFS를 Stack을 이용해서 풀어보자. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 재귀함수를 이용하는게 아닌 Stack구조를 이용하여서 문제를 풀어보았다. 기존 DFS 탐색은 Stack 많은 값이 쌓이면 스택오버플로우를 일으킨다. 하지만 Stac.. 유니온 파인드 : JAVA 정의 어떤 그래프에서 서로 인접한 그래프가 있을때 특정 노드 u와 v가 서로 같은 그래프에 있는가를 판별할 때 사용하는 방법이다. graph[i][j] = 1 이라는 것은 서로 연결되어 있다는 뜻이다. 만약 서로 연결되어 있다면 Union 두개의 노드를 같은 집합으로 합친다는 뜻이다. 이때 Find(i) Find(x) 를 하게 되는데 Find는 가장 위에 있는 부모의 값을 리턴하고 재귀과정에서 연결되 Node를 부모 노드에 바로 붙여준다. 이렇게 되면 처음 parent값은 한다리를 거쳐간다는것인데 이렇게되면 parent[x]의 값은 x가속한 집합이라고는 할수 없다. 하지만 각각에대해 Find를 돌리면 find가 재귀적으로 가장 부모노드에 연결시켜주므로 값이 제대로 나오는 것을 확인 할 수 있다. 소스코드.. 정렬 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 package test; import java.util.Arrays; import java.util.Comparator; public class test { public static class Chemi implements Comparable{ int x; int y; public Chemi(int x, int y) { super(); this.x = x; this.y = y; } @Override public int compareTo(Chemi o) { // TODO Auto-gener.. 백준 : 11279 우선순위 힙을 사용해보자 자바의 PriortyQueue 라이브러리는 기본적으로 min힙으로 구성되어있다. 하지만 다음과 같은 방법으로 우선순위를 바꾸어서 쉽게 문제를 해결할수있다. 출력은 속도를 올리기위하여 Builder를 이용했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 package com.ssay.algo; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; pu.. 백준 : 16637 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9× www.acmicpc.net package com.ssay.algo; import java.io.BufferedReader; import java.io.IO.. 백준 : 17471 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net package com.ssay.algo; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B17471 { public static int N; public static int population[]; public sta.. 이전 1 ··· 70 71 72 73 74 75 76 ··· 81 다음
