매일 조금씩

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하는 공식을 알면 쉽게 풀 수 있다. 트리 내 임의 정점을 선택하여 해당 노드에서 거리가 가장 먼 노드를 구한다. 해당 노드에서 DFS 알고리즘을 수행하여 가장 먼 거리를 구하면 그 값이 트리의 지름이 된다. 아래 블로그 내용을 참고하였다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 좌표 영역을 칠하고, DFS로 빈 공간의 개수와 넓이를 구한다. 영역 칸의 개수를 구해야 하기 때문에, 입력된 좌표를 그대로 사용하면 정확한 답을 구할 수 없다.- 이를 해결하기 위해, 칠할 영역 시작 좌표의 x, y 좌표는 +1을 해주어서 좌표의 기준을 우측 대각선 위로 동일하게 맞춰주었다. ex) 칠해야 할 영역의 시작 좌표가 0, 0 일 경우 1, 1로 변경해서..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 연합을 모두 찾은 후에 인구이동이 되어야 하므로, 찾은 연합을 저장해 둘 자료 구조를 생성한다. 1. 맵을 순회하면서 DFS로 연합을 찾아서 저장한다. 2. 연합을 모두 찾은 후에, 연합 내 총 인구/나라 개수를 계산하여 각 나라의 인구를 갱신한다. 이 두 과정을 반복 한다. 연합을 찾았는데 연합의 개수가 0개인 경우 Loop를 종료한다. 반복 횟수를 출력한다. 소스코드 ..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 1. 진출 방향에 따른 x, y 좌표 증가분을 미리 정의해 둔다. 2. 현재 파이프의 방향에 따라 진출 가능한 방향을 미리 정의해둔다. static HashMap dir = new HashMap(){{ put('V', new int[]{1, 0}); put('H', new int[]{0, 1}); put('D', new int[]{1, 1}); }}; stati..

문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 DFS + BruteForce 강수량 범위가 적기 때문에 완전 탐색으로 구현하였다. 각 강수량마다 safe영역을 구하면서, max값을 갱신 소스코드 package dfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2468 { pub..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 dfs + 구현 문제이다. 방문 체크를 하면서 로봇 청소기 작동 원리대로 코드를 구현하면 된다. 현재 방향에 따른 왼쪽 좌표와 후진 좌표, 회전 방향은 초반에 미리 정의 해두었다. (나중에 조건문으로 짜면 골치 아프당) 소스코드 package simulation; import java.io.BufferedReader; import java.io.InputStreamReader; imp..

문제 https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 8 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0..

문제 https://programmers.co.kr/learn/courses/30/lessons/1835?language=java 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 풀이 완전 탐색과 DFS로 풀었다. 데이터 개수가 8개로 정해져 있고 크지 않기 때문에 시간초과는 발생하지 않았다. 모든 경우의 수를 구하고, rule에 부합하지 않는 케이스는 count 하지 않는다. 소스코드 import java.util.*; class Solution { public boolean[] used; public ..

문제 https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 처음에 방문 체크를 HashSet을 이용했었고 예제가 맞아서 제출을 했지만 1번, 2번 테스트 케이스에서 런타임에러가 발생하였다. 원인은.... 바로 중복 티켓이 허용된다는 것이다. 다음과 같이 from-to가 동일한 티켓이 포함될 수있다. Tickets: [["ICN", "SFO"], ["SFO", "ICN"], ..

문제 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 DFS 알고리즘을 이용해서 풀었다. 중복 체크는 HashSet을 사용하였다. dfs 함수 호출 후, 다시 visitied에 해당 값을 제거해줘야 한다. 소스코드 import java.util.*; import java.lang.*; class Solution { public int answer; public ..