본문 바로가기

algorithm68

[JAVA] 백준 - 동전0 - 11047 (그리디) www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net # 풀이 스택을 이용하여 가장 단위가 큰 동전 부터 사용하면된다. 동전의 단위는 서로 배수 관계이므로 큰 동전 부터 사용해도 된다. 만약 동전끼리 배수 관계가 아니라면 적용되지 않는다. 예를 들어) ( 1, 3, 5, 6 ) 가 있다고 해보자. 8 원을 만들기 위해 큰 동전 부터 사용한다면 6원 1개 1원2개로 총 3가지 동전을 사용한다. 하지만 .. 2020. 10. 16.
[JAVA] 백준 - 4연산 14395( BFS) www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 처음 숫자가 s 라고 할때 다음 숫자는 = s + s || s - s || s * s || s / s 이다. '-' 와 '/' 는 반드시 0 과 1 이된다. 사실 t 가 0 이면 '-' 를 반환하면 되고 t가 1이면 '/'를 반환하면 된다. 그렇다고 해서 '/' 와 '-' 를 연산에서 제거하면 안된다. 모든 경우의 수를 살펴야 한다. 예를 들어 s = 10 / t = 8 이라면 (((10 / 10) + .. 2020. 10. 16.
[JAVA] 백준 - 적록색약 10026 ( BFS ) www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 단순히 그룹으로 묶어주고 그룹이 몇개 나오는지 BFS 를 이용하여 해결한다. 관건은 적록색약이 있는 경우 초록색과 빨간색을 어떻게 처리 할지다. 본인은 아래 코드 처럼 처리하였다. if((curColor=='R' || curColor=='G') && (otherColor=='R' || otherColor=='G')) return true; else return curColor == otherColor; .. 2020. 10. 16.
[JAVA] 백준 - 소수 경로 1963 ( BFS + 에라토스테네스의 체) www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 1000 에서 9999까지 미리 모든 소수를 체크해놓는 것이 좋다. 소수를 체크하는 알고리즘은 에라토스테네스의 체를 사용하여 소수를 체크한다. public static void makePrimeNumber(){ for(int i=2;i 2020. 10. 16.
[JAVA] 백준 - 레이저 통신 6087 (BFS) (테스트케이스 제공) www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 시작점 부터 도착점 까지 BFS 로 최소 개수의 거울 수를 업데이트한다. 처음에는 DFS로 쉽게 풀 수있을 거 같았지만 100 * 100 배열을 돌리니까 stackoverflow 가 발생했다. BFS 로 최소 거울 수 를 업데이트 해야한다. # 풀이 1. 클래스 정의 static class Pair{ int x,y,dir,mirror; public Pair(int x, int y, int dir, in.. 2020. 10. 15.
[JAVA] 백준 - 아기상어 16236 (BFS) www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net # 풀이 (핵심 로직) 1. BFS 를 사용하여 현재 아기 상어 위치에서 먹을 수 있는 모든 먹이를 찾는다. 2. 가장 가까운 먹이를 찾고 거리가 같다면 왼쪽 위에 있는 먹이를 고른다. 2번을 구현하기 위해 편하게 Comparable 을 구현하여 Collections 의 정렬 함수를 사용하였지만 메모리도 줄이고 속도도 늘릴 수 있는 방법도 존재한다. 코드가 늘어나고 정렬함수를 사용하더라도 메모리 사용.. 2020. 10. 15.
[JAVA] 백준 - 탈출 (3055) - (BFS) www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제�� www.acmicpc.net "움직이는 미로 탈출" 과 똑같은 문제다. onejunu.tistory.com/98 [JAVA] 백준 - 움직이는 미로 탈출 - 16954 ( BFS) www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가 onejunu.tistory.com 2차.. 2020. 10. 15.
[JAVA] 백준 - 움직이는 미로 탈출 - 16954 ( BFS) www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 미로가 움직이기 때문에 현재 좌표의 상태에 미로가 추가 되어야 한다. 즉, 현재 상태를 기억하는 정보에 미로를 추가해야한다. int 배열로 정보를 만든다면 메모리가 많이 들겠지만 다행히도 boolean 배열로도 정보를 기억할 수 있다. 또한 미로 역시 8*8 로 크기가 크지 않기 때문에 충분히 미로에 대한 정보를 들고 다녀도 된다. # 풀이 1. 현재 위치가 도착지점인가? 1-1. 도착지점이면 ok .. 2020. 10. 14.
[JAVA] 백준 - 벽 부수고 이동하기3 - 16933(BFS) www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽을 몇개 부수는지 + 낮/밤 인지 까지 다양한 조건들이 들러붙은 BFS 문제다. 풀이의 앞서서 방문 체크를 한 배열에 대해 설명한다. ch[x][y][0~1][0~k] 3번째 차원의 의미는 0 이면 낮 / 1이면 밤이다. 4번째 차원의 의미는 0이면 0개의 벽을 부순 상태/ 1이면 1개의 벽을 부순 상태/ .../ k 이면 k개의 벽을 부순 상태 이다. ch[1][2][1].. 2020. 10. 14.