본문 바로가기

구현218

[백준] 17472번 - 다리 만들기 2 [Java] https://www.acmicpc.net/problem/17472 1.  아이디어 BFS, DFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 설치할 수 있는 모든 다리를 찾아서 섬은 노드, 다리를 간선으로 하는 최소 스패닝 트리를 구하는 방식으로 해결했다.2. 문제풀이 각 섬에 번호를 붙여서 섬들을 구분하려고 했고 지도를 순회하며 섬을 발견하면 BFS, DFS 알고리즘으로 해당 섬 전체에 번호를 부여했다. 이후 지도를 순회하며 현재 위치가 섬이면서 오른쪽이 바다인 경우, 현재 위치가 섬이면서 아래쪽이 바다인 경우, 다시 섬을 발견할 때까지 해당 방향으로 계속 가며 섬을 발견하면 이 정보로 다리를 생성해서 우선순위 큐에 넣어줬다. 이후 이 우선순위 큐로 크루스칼 알고리즘을 돌려 모든 섬을 연결하는 다리 .. 2025. 2. 11.
[백준] 16236번 - 아기 상어 [Java] https://www.acmicpc.net/problem/16236 1.  아이디어 우선순위 큐와 BFS를 활용한 시뮬레이션으로 해결할 수 있다.2. 문제풀이 아기 상어와 관련된 정보인 위치와 크기는 static 변수로 관리하며 BFS 알고리즘을 적용했다. 아기 상어의 위치를 입력 받으면 해당 정보로 초기화를 하고 공간에서 아기 상어의 표시인 9를 빈칸인 0으로 변경해서 이후 탐색이 용이하게 했다. 시뮬레이션은 무한 루프에서 BFS를 적용해서 엄마 상어에게 도움을 요청하는 표시인 -1을 반환하면 종료하고 아니면 누적 시간을 더하고 먹은 물고기를 세줬다. 먹은 물고기 수가 아기 상어의 크기와 같아지면 아기 상어의 크기를 키우고 먹은 물고기 수를 0으로 초기화했다. BFS는 아기 상어가 물고기를 먹는 조건이.. 2025. 2. 10.
[백준] 14500번 - 테트로미노 [Java] https://www.acmicpc.net/problem/14500 1.  아이디어 모든 테트로미노의 모양을 미리 구한 후 각각에 대해 종이에 순회하며 계산하는 방식으로 구현했다.2. 문제풀이 init 메서드로 모든 테트로미노의 모양을 2차원 배열로 구해서 List에 담았다. init은 5가지 기본 모양을 2차원 배열로 만든 후 90도, 180도, 270도 회전 메서드와 좌우반전 메서드를 작성해서 이 기본 모양을 회전 및 반전시켜 모든 테트로미노의 모양을 구했다. 테트로미노의 경우의 수- 하늘색 테트로미노는 기본 모양, 90도 회전, 총 2가지- 노란색 테트로미노는 기본 모양, 총 1가지- 주황색 테트로미노는 기본 모양, 90도 회전, 180도 회전, 270도 회전, 반전 모양, 반전+90도 회전, 반전.. 2025. 2. 10.
[백준] 25703번 - 포인터 공부 [Java] https://www.acmicpc.net/problem/25703 1.  아이디어 N이 1일 때, 2일 때 3이상일 때만 잘 구분해서 출력하면 되는 문제로 StringBuilder를 활용해서 포맷팅하면 간단하게 해결할 수 있다.2. 문제풀이 for문의 인덱스를 활용해서 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new Outp.. 2025. 2. 10.
[소프티어] 6255번 - 플레이페어 암호 [Java] https://softeer.ai/practice/6255 1.  아이디어 문자열을 통한 구현 문제로 열심히 구현하면 간단하게 해결할 수 있다.2. 문제풀이 먼저 주어진 메시지로 문자를 두 글자씩 나누는 조건을 구현했는데 for문에서 인덱스를 i+=2로 두 칸씩 건너가는 방식으로 두 글자를 뽑아서 다르면 StringBuilder에 넣고 같으면 X가 아니면 X를 넣고 X면 Q를 넣도록 했다. 이때 X 또는 Q를 넣으면 두번째 글자가 X 또는 Q로 대체되는 것이므로 i--로 인덱스를 하나 줄이도록 했다. 또 이때 삽입한 문자의 수를 저장해서 이후 기존 메시지와 삽입한 문자 수의 합이 홀수면 뒤에 X를 추가로 넣는 조건을 구현했다. 주어진 키를 표로 변환하는 것은 변환 후 남은 칸은 다시 A부터 없는 알파벳을.. 2025. 2. 7.
[백준] 1790번 - 수 이어 쓰기 2 [Java] https://www.acmicpc.net/problem/1790 1.  아이디어 N의 크기에 비하면 메모리 크기가 작아서 진짜 수를 문자열로 이어 쓰는 방식으로는 해결할 수 없다.(아마)출력할 K번째 자리수가 실제로 어떤 수에 포함되어있는지를 구하는 방식으로 해결했다.2. 문제풀이 1부터 9까지는 1자리, 10부터 99까지는 2자리 이렇게 수가 커지면 자리수도 점차 커지며 커지는 순간은 10의 거듭제곱이 되는 순간이다.이를 활용해 현재 수와 현재 수의 자리수를 가지고 K에서 현재 수의 자리수를 빼는 과정을 반복해서 더 빼면 K가 음수가 되기 전까지 반복한다. 그러면 현재 수에서 K번째 위치의 수를 구해서 정답을 알아낼 수 있다.3. 코드 import java.io.*;import java.util.*;.. 2025. 2. 7.
[소프티어] 6250번 - 성적 평가 [Java] https://softeer.ai/practice/6250 1.  아이디어 참가자의 각 대회에서 등수와 모든 대회의 점수의 합의 등수를 출력해야하는 문제다. 참가자 번호, 참가자 점수, 참가자 등수를 필드로 갖는 클래스와 정렬을 통해 해결했다.2. 문제풀이 주어진 입력값을 받은 후 이를 참가자의 3가지 정보를 갖는 노드 배열로 반환하는 init 메서드를 활용했다. 노드 배열은 입력으로 참가자 번호와 참가자 점수는 알 수 있으므로 참가자 점수로 정렬을 해서 참가자의 등수를 구했고 이를 다시 참가자 번호로 정렬해서 원래 순서를 유지하도록 했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { .. 2025. 2. 6.
[백준] 1193번 - 분수찾기 [Java] https://www.acmicpc.net/problem/1193 1.  아이디어 분수를 찾는 과정에서 배열을 지그재그로 탐색한다. 이때 같은 대각선에 위치하는 수들은 분자와 분모의 합이 동일하다는 점과 대각선에 있는 수의 크기가 1, 2, 3 이렇게 선형적으로 증가함을 활용하면 해결할 수 있다.2. 문제풀이 X가 존재하기 이전 대각선까지의 모든 수의 개수를 구해서 sum 변수에 저장했다. 이후 N이 짝수번째 대각선이냐 홀수번째 대각선이냐에 따라 시작 위치만 바꿔서 위치를 찾아주는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { Buf.. 2025. 2. 6.
[백준] 1316번 - 그룹 단어 체커 [Java] https://www.acmicpc.net/problem/1316 1.  아이디어 각 알파벳에 대한 방문체크를 한 후 방문한 알파벳을 만났을 때 이전 알파벳과 현재 알파벳이 다르면 그룹 단어가 아님을 이용하면 간단하게 해결할 수 있다.2. 문제풀이 알파벳 소문자만 등장하므로 26칸 짜리 방문체크 배열을 만들고 첫번째 알파벳을 방문 체크한 뒤 두번째 알파벳부터 마지막 알파벳까지 방문한 알파벳을 만났을 때 이전 알파벳과 동일하지 않으면 종료하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Bu.. 2025. 2. 6.
[백준] 5622번 - 다이얼 [Java] https://www.acmicpc.net/problem/5622 1.  아이디어 각 알파벳이 위치한 다이얼에 적힌 숫자 + 1 만큼의 시간이 걸림을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 알파벳마다 걸리는 시간을 표현하는 26칸짜리 알파벳 배열을 만들고 걸리는 시간을 미리 저장했다. 0번 인덱스에 A부터 25번 인덱스를 Z에 매칭한 후 이를 통해 시간의 합을 구하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy.. 2025. 2. 6.
[백준] 2845번 - 파티가 끝나고 난 뒤 [Java] https://www.acmicpc.net/problem/2845 1.  아이디어 각 다섯 개의 숫자에서 사람의 수와 넓이의 곱을 빼주면 간단하게 해결할 수 있다.2. 문제풀이 아이디어 그대로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out.. 2025. 2. 2.
[백준] 15792번 - A/B - 2 [Java] https://www.acmicpc.net/problem/15792 1.  아이디어 소수점에 대한 정밀도가 매우 높은 문제로 BigDecimal 클래스를 활용하면 해결할 수 있다.2. 문제풀이 BigDecimal 클래스의 divide 메서드로 나눗셈을 수행할 수 있으며 정밀도에 맞춰 scale에 10000, 반올림을 하는 방식으로 적용했다.3. 코드 import java.io.*;import java.math.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRe.. 2025. 2. 2.

티스토리툴바