kwang2134 님의 블로그

[Programmers] 아이템 줍기 - LV 3접근bfs풀이좌표 평면에 여러 개의 사각형이 주어지고 겹쳐진 사각형의 외부 테두리만 따라 이동하며 아이템을 주우러 갈 때 최단 경로를 구하는 문제이다. 간단하게 생각하자면 모든 사각형의 테두리만 2차원 배열에 매핑한 뒤 매핑된 경로만 bfs를 사용해 따라가면 된다. 문제는 좌표를 그대로 가져 쓰면 (4, 5) (4, 6)처럼 움푹 들어간 부분을 제대로 표시할 수 없다. 각 좌표마다 점을 찍어 매핑하기 때문에 (3, 5)와 (3, 6) 은 좌표상에서 붙어있는 것처럼 보이기 때문에 정확하게 구현을 하기 위해선 좌표를 두 배로 확장해주어야 한다. private static final int[] dx = {0, 0, 1, -1}; private sta..

[백준] 요세푸스 한 번 더! - GOLD II 6523번접근map풀이오랜만의 백준 문제인데 팀원이 재밌다고 공유해 준 문제이다. N명의 사람이 원탁에 앉아 수식을 통해 다음 술 마실 사람을 정하고 똑같은 사람이 3번 걸렸을 때 술자리가 종료되는데 그때 술을 마시지 않았던 사람의 수를 구하는 문제이다.  문제 내용만 보면 정말 쉬워 보이는데 재밌을 거라는 뜻이 처음엔 뭔지 몰랐으나 알게 되었다. 로직은 정말 간단하게 map을 사용해 술 마신 사람과 횟수를 저장하고 3번이 되면 술 마신 사람들 수를 전체 인원에서 빼면 구할 수 있을 거 같았다. 다만 사람의 수가 최대 10의 9 제곱으로 10억 명까지 존재가 가능하기 때문에 다음 술 마실 사람의 번호를 구하는 ax^2+b mod N 이 수식에서 오버플로우가..

[백준] 가장 긴 증가하는 부분 수열 - SILVER II 11053번접근dp풀이주어지는 숫자들 중 증가하는 가장 긴 수열의 개수를 찾아내는 문제이다. 처음 문제를 보고 한 생각은 따로 정렬된 배열을 두고 정렬된 숫자를 원본 배열에 매칭시키며 개수를 구하면 되는 게 아닌가 했는데 수열에 위치할 다음 숫자를 무조건 골라야 하는 게 아닌 스킵하고 넘어갈 수 있으므로 사용할 수 없는 방법이었다. 이 문제처럼 보통 바로 다음만 고려하는게 아닌 뒤의 경우도 고려해야 하는 조건인 경우 dp를 사용하면 해결할 수 있다. 동적 배열을 이용하여 각 단계별 가장 긴 경우의 길이를 구해 차근차근 쌓아가는 것이다. 앞의 최댓값들을 활용해 늘려나가는 bottom-up 방식이기 때문에 각 인덱스까지의 부분수열의 최대 길이를 구할..

[백준] 곱셈 - SILVER I 1629번접근빠른 거듭제곱풀이곱셈이라는 제목의 문제로 설명을 대충 봤을 땐 이게 왜 실버 1의 문제인 건지 이해할 수 없는 내용의 문제이다. a, b, c 세 정수가 있고 a를 b번 곱한 결과에 c를 나눈 나머지를 출력하는 문제이다. 처음에 a와 b를 곱한 값에 c를 나눈 나머지를 출력하는 문제인 줄 알고 바로 제출했다 한 번 틀렸고 a의 b제곱을 구하는 문제인지 다시 인지한 후에 아무 생각 없이 Math.pow를 사용하여 제출했다 또 틀렸다. 문제에 주어진 값의 최대가 Integer.MAX_VALUE 이기 때문에 오버플로우가 났구나 하고 반복문으로 만들어 매번 c를 나눠 줬다가 또 틀렸다. 값의 최댓값이 21억인데 그걸 반복문으로 돌리려 했으니 통과할리가 없는데 말이다..

[백준] 최소비용 구하기 - GOLD V 1916번접근플루이드-워셜 (시간 초과)다익스트라 (Dijkstra's Algorithm)풀이N개의 도시에서 출발하는 M개의 버스를 통해 목표로 주어진 출발지에서 목적지까지 가는데 드는 비용의 최솟값을 구하는 문제이다. 이 문제는 가중치가 있는 방향 있는 그래프에서 최단 경로의 가중치를 구하는 문제이다. 저번에 풀었던 경로 찾기 문제에서 간단하게 설명했던 플루이드 워셜 알고리즘을 사용해서 풀려고 했으나 N의 최댓값이 1,000으로 플루이드-워셜 알고리즘을 사용할 경우 최악의 경우 10억의 연산이 발생해 주어지는 0.5초의 제한 시간 내 통과는 불가능하다. 플루이드-워셜은 모든 경로의 가중치를 다 구하다 보니 이번 문제에선 사용할 수 없는 방법이었다. 전체 코드 부..

[백준] A -> B - SILVER 2 16953번접근bfs풀이A의 값을 정해진 연산을 수행하여 B로 만드는데 걸리는 최소 연산 횟수를 구하는 문제이다. 최소 연산, 역시나 bfs 문제로 실버 난이도의 문제인 만큼 어려움은 없지만 한 가지 조심할 점이 있다. 바로 문제에서 주어지는 A와 B의 범위인데 최댓값이 10억이다. 물론 int 정수는 21억까지 값을 표현할 수 있어 문제가 있나 싶지만 이번 문제에서 주어지는 두 번째 연산 방법 때문에 문제가 생길 수 있다.  첫 번째 연산은 단순 숫자에 2를 곱하는 연산이다. 이 연산은 범위 체크만 잘해준다면 int 정수를 사용하여도 문제가 되지 않는다. 주의할 점은 두 번째 연산으로 숫자 맨 뒤에 1을 추가하는 연산이다. 수학적 연산이 아니라 문자 연산으로 1..

[백준] 테트로미노 - GOLD IV 14500번접근dfs풀이Class 3에 남았던 마지막 문제로 대미를 장식하는 만큼 정말 많은 제출로 통과를 시도했고 이때까지 백준에서 푼 문제 중에 가장 많은 시간을 사용했던 문제이다. 문제의 내용은 값이 적혀있는 2차원 배열에 테트리스에서 나오는 모양들의 블록을 배치했을 때 각 자리 값들의 합이 가장 클 때의 값이 얼마인지 구하는 문제이다. 문제는 모든 경로를 깊게 탐색하여 살펴봐야 하기 때문에 dfs를 사용해서 풀어주었다. 문제를 풀긴 했지만 원하던 대로 시원하게 풀지 못했고 일단 크게 겪었던 이슈에 대해서부터 언급하고 넘어가겠다. 1. T 모양 블록 처리 처음 문제를 풀 때 단순 dfs를 사용하면 모든 경로를 깊숙하게 탐색을 하기 때문에 4칸의 깊이 제한을 두면..

[백준] 뱀과 사다리 게임 - GOLD V 16928접근bfs풀이단순한 주사위를 사용한 보드게임으로 사다리가 있는 칸이라면 사다리를 타고 앞의 칸으로 이동하게 되고 뱀이 있는 칸이라면 뱀에 미끄러져 밑에 칸으로 떨어지게 되는 게임에서 몇 턴만에 마지막 칸에 도달할 수 있는지 구하는 문제이다. 문제를 보고 굉장히 단순해 보여 금방 풀고 넘길 수 있을 거 같았는데 잘못된 생각으로 시간을 날려먹고 중복 처리를 실수해 메모리 초과로 한 번 더 시간을 날려먹은 문제이다. 첫 번째로 잘못된 생각이란 사다리의 경우 한 번에 많은 칸을 전진할 수 있기 때문에 무조건 타는게 좋다고 생각했다. 뱀의 경우 강제로 많은 칸을 후진 당하기 때문에 다음 위치가 뱀이라면 큐에 추가하지 않고 일반 칸이거나 사다리 칸만 큐에 넣으면 ..

[백준] 적록색약 - GOLD V 10026번접근bfs풀이Red, Green, Blue 세 가지 색이 주어지는데 일반인의 시선으로 봤을 때 나눠지는 색 구역 개수와 적록색약을 가진 사람이 봤을 때 나눠지는 색 구역 개수를 구하는 문제이다. 대체적으로 실버1~골드5 난이도 구간에는 bfs를 사용하는 문제가 참 많은거 같다. 물론 이 문제도 bfs를 사용한 문제로 이전에 풀었던 단지번호 붙이기 문제의 코드를 인용해 수정하여 풀었다.2024.09.26 - [알고리즘/코딩테스트-백준] - [백준] 단지번호 붙이기 JAVA [백준] 단지번호 붙이기 JAVA[백준] 단지번호 붙이기 - SILVER I 2667번2667번: 단지번호붙이기 (acmicpc.net)접근bfs풀이2차원 배열로 주어지는 지도를 탐색하며 붙어..

[백준] 토마토 - GOLD V 7579, 7576번접근bfs풀이토마토 농장에는 덜 익은 토마토와 다 익은 토마토가 존재하는데 덜 익은 토마토가 다 익은 토마토 옆에 있을 때 하루가 지나면 익게 되고 그렇게 전파되어 모든 토마토가 다 익을 때까지 며칠이 소요되는지 구하는 문제이다. 흔히 볼 수 있는 옆으로 상태를 전파하여 모두 같은 상태가 될 때까지 걸리는 시간을 구하는 문제다. 현재 백준 사이트에 토마토의 이름으로 2 문제가 존재하는데 한 문제는 평면 구조로 2차원 배열에 있는 토마토들의 상태가 전파되는 문제이고 다른 한 문제는 2차원 배열로 들어있는 토마토가 3차원으로 확장되어 층층이 쌓일 수 있다는 조건이 추가된 문제이다. 2차원을 다루는 문제와 3차원을 다루는 문제로 약간 더 심화된 문제인데 왜 ..