본문 바로가기

분류 전체보기61

[백준] 17141 연구소2 (Java) [17141 연구소2] 난이도: 골드4 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 문제 입력 출력 [아이디어] 바이러스가 들어갈 자리에서 M개를 조합으로 선택하여 완전 탐색하는 방법이다. 사방면으로 바이러스가 퍼져나갈 수 있고, 최소 시간을 구하는 문제이기 때문에 BFS를 사용하였다. 그 외는 단순한데, Queue에 처음 바이러스 자리 M개를 초기화 시켜줄 때 전체 맵을 탐색할지 M개를 바로 넣을지를 고민하였다. 직접 해본 시간이 별로 차이나지 않으므로 아무거나 써도 될 것 같다! [JAVA 코드] 1. M개를 바.. 2022. 5. 20.
[프로그래머스] SQL 고득점 Kit - 역순 정렬하기 [SELECT 역순 정렬하기] 난이도: Level 1 코딩테스트 연습 - 역순 정렬하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [MySQL 코드] SELECT NAME, DATETIME FROM ANIMAL_INS ORDER BY ANIMAL_ID DESC; 2022. 5. 14.
[프로그래머스] SQL 고득점 Kit - 모든 레코드 조회하기 [SELECT 모든 레코드 조회하기] 난이도: Level 1 코딩테스트 연습 - 모든 레코드 조회하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr [MySQL 코드] SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID; 2022. 5. 14.
[백준] 21924 도시건설 (Java) [21924 도시건설] 난이도: 골드4 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 입력 출력 [아이디어] 모든 노드를 이었을 때 가중치가 최소가 되어야 하므로 MST를 사용하였다. 기본적인 MST를 활용하였는데 모든 건물이 연결되지 않은 경우도 있기 때문에 방문한 노드의 수를 체크해주었다. 모든 가중치를 계산한 후 방문한 노드의 수가 전체 노드의 수 보다 적다면 연결되지 않은 경.. 2022. 5. 14.
[백준] 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.

티스토리툴바