Algorithm (41) 썸네일형 리스트형 [Java] BOJ1620_나는야 포켓몬 마스터 이다솜 www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 포켓몬 이름과 도감 번호를 Key, Value로 갖기 위해 HashMap을 이용했다. 탐색을 빨리하기 위함도 있다. 하지만 key값으로 값을 찾는 것은 빠르지만 value를 이용해 값을 찾는 것은 오래 걸리기 때문에 도감 번호를 key로, 포켓몬 이름을 value로 하는 HashMap을 하나 더 만들었다. 그렇게 하여 key값으로만 탐색을 하도록 구현하였다. import java.i.. [Java] BOJ1600_말이 되고픈 원숭이 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net Knight처럼 이동하거나 상, 하, 좌, 우 네 방향을 이동해서 도착점까지 이동해야 한다. 이때 Knight처럼 이동하는 것은 K번만 가능하다. BFS로 탐색하는 문제에서 Knight로 이동하는 조건이 추가된 문제이다. 이런 경우 Knight이동을 1번만 한 경우, 2번 한 경우,... K번 한 경우를 다 고려해서 최소 동작 수를 구해줘야 한다. 따라서 방문 처리 배열을 index와 knigh.. [Java] BOJ15686_치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net M개의 치킨집을 골라 도시의 치킨 거리를 가장 작게 만드는 경우를 구하는 구현 문제이다. M보다 크거나 같은 치킨집의 수에서 M개를 고르는 조합으로 해결하였다. M개의 치킨집을 고른 후 각 집에서 치킨집들까지 거리 중 가장 작은 값들을 더해 해당 경우의 치킨 거리를 구했다. 그 후 최솟값 비교를 통해 결과를 도출했다. import java.io.*; import java.util.*; pu.. [Java] BOJ15683_감시 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 감시카메라를 방향별로 다 놓아보고 사각지대를 찾아야 하는 브루트 포스 구현 문제이다. 감시 영역이 겹치는 부분에 대한 처리를 하기 위하여 빈칸(값이 0)인 부분을 값 7로 세팅했다. 카메라 종류별로 CASE를 나누어 주었고 종류에서 방향별로 반복문을 돌아 부분집합을 구성했다. 어떤 카메라가 특정 방향으로 감시를 할 때 감시가 되는 부분 중 값이 7인 곳은 빈칸이므로 사각지대를 하나 감소시켰고 그 부분.. [Java] BOJ2473_세 용액 www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 두 용액 문제에서 포인터가 하나 더 추가된 문제이다. 방식은 두 용액과 유사하여 왼쪽과 오른쪽을 포인터로 두고 그 가운데 값 중 합을 가장 0과 가깝게 만드는 값을 찾아 최솟값 비교를 해주었다. 하지만 이 코드로 통과하지 못하여 다른 방식으로 접근하였다. 왼쪽 값은 고정되어 있고 왼쪽 값을 기준으로 가운데 값고 오른쪽 값을 두 포인터로 잡아 탐색하는 것이다. 위 두 방식 모두 전 범위를 탐.. [Java] BOJ2470_두 용액 www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 용액 문제에서 정렬이 되지 않은 값이 들어온다는 점만 다르다. 따라서 정렬 코드를 추가해주면 된다. import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatE.. [Java] BOJ2467_용액 www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net jihunworld.tistory.com/28 위의 용액 합성하기 문제와 거의 같은 문제이다. 가장 0과 가까운 수를 찾았을 때 왼쪽과 오른쪽 용액을 저장해 두고 출력하면 된다. import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberForm.. [Java] BOJ14921_용액 합성하기 www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당 www.acmicpc.net 두 용액을 섞어서 0과 가장 가까운 수를 만드는 문제이다. 두 용액을 선택하기 위해 두 포인터 알고리즘을 사용했다. 포인터를 양 쪽 끝으로 잡고 두 용액의 합이 음수일 경우 왼쪽 포인터를 증가시켰고 양수일 경우 오른쪽 포인터를 감소시켰다. 값들이 오름차순으로 정렬되어있기 때문에 두 용액을 섞었을 때 0과 가까운 수를 만들기 위함이다. 왼쪽 포인터를 증가시키면 두 용액의 합은 커지고 오.. 이전 1 2 3 4 5 6 다음