본문 바로가기

Java38

[백준] 3584 가장 가까운 공통 조상 (Java) [3584 가장 가까운 공통 조상] 난이도: 골드4 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 입력 출력 [아이디어] 노드마다 부모는 단 하나만 존재한다. 그래서 노드의 부모를 저장해주는 배열을 따로 만들어주었다. parent[i] = j => i 의 부모가 j 이다. 그 다음 두 노드 중 하나의 노드부터 시작하여 루트까지 방문을 체크해준다. 그 후 나머지 노드에 대해 루트까지 올라가면서 방문한 노드를 만나면 그게 가장 가까운 공통 노드가 된다! .. 2022. 5. 12.
[백준] 18405 경쟁적 전염 (Java) [18405 경쟁적 전염] 난이도: 골드5 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 입력 출력 [아이디어] 사방으로 바이러스가 퍼져나가므로 BFS를 활용하면 된다. 이 때, 매 초다마 번호가 낮은 종류의 바이러스부터 증식하므로 단순 Queue를 사용하면 구현이 조금 복잡해질 수 있다. 따라서 나는 우선순위 큐를 사용해주었다. Point 클래스를 생성하여 바이러스의 위치, 종류, 걸린시간을 관리해주었고, 시간과 바이러스 종류로 우선순위를 정해주었다. 그 후는 일반 BFS.. 2022. 5. 5.
[백준] 5430 AC (Java) [5430 AC] 난이도: 골드5 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 입력 출력 [아이디어] 이 문제는 두가지 방법으로 풀어볼 수 있다. R이 나올 때마다 정말 배열을 뒤집으면 시간초과가 난다. 하나는 덱을 사용하는 방법이고, 다른 하나는 투포인터를 사용하는 방법이다. 덱을 사용하는 것은 단순하게 앞에서 삭제할지 뒤에서 삭제할지를 저장하는 변수를 통해 덱의 내장함수인 removeFirst(), removeLast(), pollFirst(), pollLast() 를 사용해주었다. 투포인터를 사용할 때는 st와 end 위치를 저장하는 변수와 삭제 위치.. 2022. 5. 2.
[백준] 14442 벽 부수고 이동하기 2 (Java) [14442 벽 부수고 이동하기 2] 난이도: 골드3 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 입력 출력 [아이디어] 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 위의 문제의 업그레이드 버전이다. 저 문제를 먼저 풀고 지금 문제를 푸는 것이.. 2022. 5. 1.
[백준] 2206 벽 부수고 이동하기 (Java) [2206 벽 부수고 이동하기] 난이도: 골드4 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 입력 출력 [아이디어] 빠르게 목적지에 도착하는 경우를 구해야하기 때문에 BFS를 활용하면 된다. 하지만 벽을 한 번 파괴할 수 있으므로 파괴한적이 있는지 따로 체크해주며 돌아준다. 그래서 Point 클래스를 따로 만들어주고, 안에는 위치와 이동한 횟수, 파괴했는지를 저장해준다. static class Point { int r, c, cnt; boolean distroyed; // 파.. 2022. 5. 1.
[solved.ac] Gold1 달성! 싸피를 시작하고, 알고리즘 수업을 들은 후부터 백준을 꾸준히 풀기 위해 노력했다. 특히 알고리즘 기간에는 문제를 많이 풀었고, 하루에 11문제까지 푼 적도 있었다. 하지만, 중간에 잔디밭에 구멍이 생기자 마음이 좀 풀어진 것 같았다. 싸피를 위해 아이디를 새로 만들었고, 첫 문제를 푼 1월 19일부터 4월 28일까지 총 214문제를 풀었고, 드디어 solved.ac 랭크인 GOLD1을 달성하게 되었다. 물론 혼자서 했다면 아직 골드3에 머물러 있었을 것 같다. 알고리즘 스터디원 중 문제를 엄청 많이 풀고, 잘 푸는 친구가 있어서 동기부여가 됐었던거 같다. (그래서 한 일주일정도 불태웠다 ㅎㅎ) 알고리즘 수업 이후로는 프론트부터 스프링까지 매주 엄청난 진도를 배워야했기 때문에 알고리즘에 이전만큼 시간을 쓸.. 2022. 4. 29.
[백준] 21939 문제 추천 시스템 Version 1 (Java) [21939 문제 추천 시스템 Version 1] 난이도: 골드4 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제 입력 출력 [아이디어] recommend 명령을 수행할 때 조건이 좀 까롭다. 문제의 번호와 난이도를 저장할 때 우선순위 큐를 여러개 사용하여 풀까 하다가 트리와 셋을 함께 사용하는 방법을 생각해냈다. TreeMap Quest = new TreeMap(); 우선 맵의 키는 문제의 난이도이다. 하나의 난이도에 대해 하나의 셋이 존재하고, 셋에는 문제 번호를 넣어준다.. 2022. 4. 29.
[백준] 23326 홍익 투어리스트 (Java) [23326 홍익 투어리스트] 난이도: 골드3 23326번: 홍익 투어리스트 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, www.acmicpc.net 문제 입력 출력 [아이디어] 구현이 중요한 문제같다. TreeSet을 활용하여 명소의 위치를 관리해주었는데, 이 이유는 3번 쿼리를 빠르게 다루기 위해서이다. 처음에 명소의 위치를 초기화해준 후 쿼리문을 수행하는데, 1번 쿼리는 단순히 set에 넣고 빼주기만 하면 된다. 2번 쿼리는 위치를 이동시켜주는데 now = (now + n - 1) % N + 1 이 식을 활용하면 된다. 이 때, now의 최.. 2022. 4. 27.
[백준] 14890 경사로 (Java) [14890 경사로] 난이도: 골드3 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 입력 출력 [아이디어] 단순한 구현 문제이다. 문제 설명대로 코드를 짜주면 되는데 경사로가 겹치게 놓이면 안된다는 것이 가장 까다롭다. 따라서 나는 경사로가 이미 놔져있는가를 체크하는 배열을 따로 써줬다. 그리고 열방향 탐색의 함수를 따로 만들지 않고, 열을 행으로 변환하여 하나의 함수를 재활용 하였다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import jav.. 2022. 4. 26.
[Java Collection] 자바 컬렉션 java.util 패키지에 collection framework 핵심 인터페이스가 들어있다. 다수의 데이터를 쉽게 처리하는 방법을 제공한다. interface 특징 구현 클래스 List 순서가 있는 데이터의 집합. 순서가 있으니까 데이터의 중복을 허락 ex) 일렬로 줄 서기 ArrayList LinkedList Set 순서를 유지하지 않는 데이터의 집합. 순서가 없어서 같은 데이터를 구별할 수 없다. -> 중복 허락하지 않는다. ex) 알파벳이 한 종류씩 있는 주머니 HashSet TreeSet Map key와 value의 쌍으로 데이터를 관리하는 집합. 순서는 없고 key의 중복 불가, value는 중복 가능 ex) 속성 - 값, 지역번호 - 지역 HashMap TreeMap 1. List 인터페이스 .. 2022. 4. 23.
[백준] 1593 문자 해독 (Java) [1593 문자 해독] 난이도: 골드4 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 문제 입력 출력 [아이디어] 문자열 S를 앞에서부터 탐색하면서 문자열 W의 길이만큼 잘랐을 때 그 안에 문자열 W의 원소가 전부 있는지 확인해주는 문제이다. 문자열 W의 원소를 전부 탐색할 때 문자열 S을 자른 문자열을 비교하는 방법이 중요하다. 아마 대부분 아래와 같은 함수를 먼저 떠올리기 쉬울 것이다. 하지만, 이런 방법을 사용한다면 시간초과가 날 것이다. // W: 문자열 W // sli.. 2022. 4. 22.
[백준] 1941 소문난 칠공주 (Java) [1941 소문난 칠공주] 난이도: 골드3 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제 입력 출력 [아이디어] BFS와 백트래킹 그리고 조합을 사용하는 문제이다. 단순한 BFS를 사용하면 십자가모양을 만들어낼 수 없기 때문에 조합을 사용하여 먼저 7명을 선택해준다. 이 때, 5 x 5 로 학생들이 주어지기 때문에 0 ~ 24로 번호를 정하고 조합을 구하면 편하다. n번 학생의 (행, 열)을 구하는 방법은 (n / 5, n % 5) 이므로 번호를 좌표로 변환하는 것은 크게 어렵지 않다. 7명을 모두 선택한.. 2022. 4. 20.

티스토리툴바