알고리즘
백준 1967 - 트리의지름
1. 유형 트리 2. 문제 분석 2-1. 문제 설명 트리에서 가장 긴 두 점은 리프 노드끼리의 거리임을 직관적으로 알 수 있습니다. 따라서 리프노드에서 재귀의 리턴 값을 사용해서 문제를 풀어야 합니다. [그림 1]에서 지름은 9->5->3->6->12입니다. 저 케이스를 예시로 들어봅시다. DP [k] = n => 노드 k를 기준으로 한 가장 긴 지름은 n이다.라고 정의 우선은 리프 노드까지 dfs를 진행합니다. 9에서 15를 리턴하고, 10에서 4를 리턴합니다. 노드 5에서는 15와 4중 더 긴 큰 값을 리턴합니다. 노드 3 에서는 왼쪽에서 오는 가장 큰 값 26, 오른쪽에서 오는 가장 큰 값 19를 DP [3]에 저장 2-2. 주의할 점 자식 노드가 3개 이상일 수 있습니다. 따라서 둘 중에 최댓값이..
백준 1613 - 역사
[문제 바로가기] 1. 유형 프롤이드 와샬 2. 문제 분석 2-1. 해설 플로이드 와샬을 쓰는 문제였습니다. N=400이기 때문에, 3중 for문을 돌려도 시간안에 들어옵니다. 플로이드를 사용해서 출발점에서 도착지점 까지의 최단거리를 구해서 저장합니다. 맵 초기화 알고리즘 적용 후 S개의 인풋값이 (1,5) (2,4) (3,1)이 주어집니다. (1,5)는 무한대 이니깐 0출력 (2,4)는 1이니깐 관계를 알 수 있음, -1 출력 (3,1)는 무한대이지만 (1,3)은 관계를 알 수 있음. 1 출력 2-2. 설계 2차원 배열을 INF로 초기화 -> 플로이드 와샬 -> 인풋 쌍을 보면서 출력 3. 코드 import java.io.*; import java.util.*; //https://www.acmicpc...
백준 17255 - N으로 만들기
[문제 바로가기] 1. 유형 DFS 2. 문제 분석 2-1. 설계 시작 위치를 탐색 -> 함수 시작 -> 현 위치에서 왼쪽, 오른쪽으로 재귀 진행 -> 총 N-1개를 탐색하면 종료 2-2. 설명 투포인터를 사용했습니다. [그림1]은 "521"중 2를 시작위치로 설정했을 때의 경우 입니다. 왼쪽, 오른쪽에 포인터를 두고 path변수에 만든 루트를 저장합니다. 그리고 Set 컬렉션에서 중복을 제외해주면 됩니다. 3. 코드 import java.io.*; import java.util.*; public class Main { static char[] arr; static Set set; public static void main(String[] args) throws IOException { BufferedR..
백준 9548 - 무제
[문제 바로가기] 1. 유형 문자열 2. 문제 접근 더 좋은 풀이법이 있는 것 같지만, 생각이 안나서 StringBuffer를 사용했습니다. 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int T = stoi(st.nextToken()); while (T-- > 0) { st = new StringT..
백준 17141 - 연구소2
[문제 바로가기] 1. 유형 BFS, 조합 2. 문제 접근 2-1. 설계 일단 설계부터 해봅시다. 위치의 조합 찾기 문제에서 2는 바이러스를 퍼트릴 수 있는 곳 입니다. 따라서 List에 2의 위치를 모두 넣어주고, 그 중에서 M개를 선택합니다. List에 위치를 넣는 방법은 (r,c)를 넣어줘도 되고, 저는 인덱스 값만 넣어줬습니다. 예를들어 N=3이라면, 아래 그림처럼 나올 것이고. 인덱스8은 의 좌표는 (8/N, 8%N)이 됩니다. 0 1 2 3 4 5 6 7 8 bfs로 퍼뜨리기 bfs구현에서 특별한것은 없습니다. 총 탐색한 칸수를 카운트해주고, bfs가 끝나고 카운트해준 값이 바이러스를 퍼뜨릴 칸수와 일치하면 정답을 갱신합니다. M=1일때, 아래 인풋값을 가정합시다. 바이러스를 유출해야하는 칸수..
백준 1622 - 공통 순열
[문제 바로가기] 1. 유형 정렬 2. 문제 분석 문자열 최대 길이가 1000입니다. 따라서 딕셔너리를 만들어서 두 문자열을 비교해줬습니다. Map {문자, 문자가 나온 횟수} 예를들어 "abccc"라는 문자가 있다면, {a=1,b=1, c=3} 형식으로 됩니다. 두 문자열을 딕셔너리로 만들고, 공통 요소가 있을 경우 더 더 낮은 횟수만큼 정답에 넣어주면 됩니다. 아마도 이 문제의 가장 어려운 점은 EOF입니다. Scanner를 사용해서, 아래처럼 다음 문자열이 존재하는지를 판단했습니다. Scanner sc = new Scanner(System.in); while(sc.hasNextLine()) { // } BuffredReader를 이용해 보려고 했지만 계속 런탐에러가 나와서 포기...왜 안될까요.....
백준 1937 - 욕심쟁이 판다
[문제 바로가기] 1. 유형 DFS, 메모리제이션 2. 문제 접근 처음으로 든 풀이법은 배열을 완전탐색하면서 DFS를 한번씩 사용하는 것 입니다. 하지만 이러면 500^4의 시간이 걸리기 때문에 시간초과가 날 것입니다. 따라서 이 문제에선 DFS+DP를 써야됩니다. 9 10 1 11 위와 같은 원본 테이블이 있습니다. 최대 길이는 1->9->10->11으로 4가 나옵니다. DP[r][c] = val val은 현재 좌표에서 최대 길이를 의미. DP테이블을 구해봅시다. 그림1은 DP테이블 초기화. (0,0)에서 DFS를 한번 돌립니다. 그럼 그림2와 같은 테이블이 될것입니다. 그 다음 (1,0)에서도 DFS를 돌려야 할까요? 아닙니다. (1,0)에서 4방향을 탐색합니다. 원본배열에서 1 < 9 이니깐, 본인..
leetcode - 350. Intersection of Two Arrays II
[문제 바로가기] 1. 유형 구현, 정렬 2. 문제 분석 두 배열의 교집합을 구하는 문제였습니다. 요즘 Stream을 공부 중인데, for을 최소한으로 사용을 연습을 위해 풀어봤습니다. 3. 코드 static public int[] solution(int[] nums1, int[] nums2) { List list = new ArrayList(); Map n = new HashMap(); Map m = new HashMap(); Arrays.stream(nums1).forEach(x -> n.put(x, n.getOrDefault(x, 0) + 1)); Arrays.stream(nums2).forEach(x -> m.put(x, m.getOrDefault(x, 0) + 1)); for (int k : n..
백준 2146 - 다리 만들기
[문제 바로가기] 1. 유형 BFS 2. 문제 접근 2-1. 설계 2-2. 해설 BFS를 사용해서 섬을 구합니다. 섬의 개수를 구하는 문제는 아래와 같습니다. [문제 바로가기 - 백준, 섬의 개수 - 4963] 섬의 개수를 구했으면, 섬에서 다른 섬까지의 최단거릴 구하기 위해 다시 BFS를 돌립니다. bfs를 돌릴 때, 그림 1처럼 조건을 정해줘야 합니다. 맵을 이탈할 경우 예외처리, 그리고 다름 섬을 만났으면 그 자리에서 거리를 리턴해주면 됩니다. 3. 코드 import java.io.*; import java.util.*; public class boj_2146_다리만들기 { static int map[][], N, d[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -..
백준 19542 - 전단지 돌리기
[문제 바로가기] 1. 유형 깊이 우선 탐색, 트리 2. 문제 접근 2-1. 해설 우선 저는 현재 위치와 leaf노드까지의 깊이를 탐색했습니다. 그림 1처럼 만드는 것은 재귀를 사용해서 return값에 +1을 해주면 됩니다. 하지만 저기서도 문제가 있습니다. 2,3,4 노드 같은 여러 가지로 뻗어나가는 부분이 까다롭습니다. 그래서 그림2 처럼 여러 가지로 뻗어나가는 경우는 리턴 값 중 최댓값을 노드의 깊이로 선택하면 됩니다. 그림 1처럼 노드의 최대 깊이를 탐색했으면 D보다 큰 녀석들의 갯수를 카운트해주고, 왕복이니깐 *2를 해주면 정답이 나옵니다. 2-2. 설계 3. 코드 import java.io.*; import java.util.*; public class Main { static boolean ..
백준 16202 - MST게임
[문제 바로가기] 1. 유형 MST 2. 문제 분석 2-1. 해설 크루스 칼 알고리즘을 여러 번 사용해서 푸는 문제입니다. 크루스 칼을 한번 돌리고, 가중치가 가장 작은 선분을 하나 빼고, 다시 크루스 칼 돌리고... 이걸 반복해주면 끝나는 문제였습니다. 2-2. 설계 3. 코드 부노노드가 전부 같은지 확인하는 코드 부모 노드가 같지 않으면 union을 사용해서 부모 노드 동일하게 만들어줌 import java.io.*; import java.util.*; public class Main { static int N, M, K, parent[]; public static void main(String[] args) throws IOException { BufferedReader in = new Buffer..
백준 - 2406 안정적인 네트워크
[문제 바로가기] 1. 유형 MST 2. 문제 접근 2-1. 해설 컴퓨터가 고장 난 경우 1. 1번 컴퓨터가 고장남 -> 나머지들이 MST 구조이다 2. 1번을 제외한 컴퓨터가 고장남 -> 어차피 1번과 연결되어 있어서 구할 필요 없음. 두 컴퓨터 간 연결이 끊어짐 1. 1번과 그 외의 컴퓨터 간의 연결이 끊어짐 -> 1번을 제외하고 MST 구조를 구해야 함 2. 1번을 제외한 두 컴퓨터 간 연결이 끊어짐 -> 1번을 제외한 MST 구조를 구해야 함. 위의 4가지 경우를 전부 따져보면 어쨌든 1번을 제외한 최단거리를 구해하는 걸 알 수 있습니다. 문제 이해가 어렵지 구현 난이도는 일반적인 크루스 칼 알고리즘입니다. 2-2. 설계 3. 코드 import java.io.*; import java.util.*..
백준 17090 - 미로 탈출하기
[문제 바로가기] 1. 유형 dfs, 동적프로그래밍 2. 문제 분석 2-1. 설계 2-2. 설명 가장 먼저 떠오른 생각은 완전 탐색 입니다. 하지만 500^4을 하면 1억이 넘어가 시간초과가 나옵니다. 따라서 메모리제이션을 통해 한번 탐색한 길은 또 탐색하지 않도록 하는 방법으로 풀이했습니다. 범위를 나가서 한번 검증된 길은 1을 저장하고, 잘못된 길은 0을 리턴해서 굳이 끝까지 가지 않더라도 길의 종착지가 어떤지를 확인 가능합니다. 3. 코드 import java.util.*; import java.io.*; public class Main { static int N,M, dp[][]; public static void main(String[] args) throws IOException { Buffe..
프로그래머스 위클리 챌린지 5주차 - 모음 사전
https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 1. 유형 완전 탐색 2. 문제 접근 총경우의 수가 5^5 + 5^4 + 5^3 + 5^2 + 5입니다. 그래서 완전 탐색을 돌릴 수 있다고 판단 모든 경우의 수를 List에 넣고 word와 같은 값을 찾아줬습니다. 다른 풀이를 보니 규칙을 찾아서 간단하게 풀 수도 있는거 같습니다. 3. 코드 import java.u..
백준 1747 - 소수&팰린드롬
https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 1. 유형 브루트 포스 2. 문제 접근 2-1. 설계 에라토스테네스의 체로 소수 판단 투 포인터를 사용하여 팰린드롬 확인 2-2. 주의할 점 입력값이 N이고 조건을 만족하는 정답은 N보다 더 커질 수 있습니다. 따라서 에라토스테네스의 체를 구할 때, 전체 크기를 100000보다 큰 소수를 구해서 정해줘야 합니다. 3. 코드 import java.util.*; ..
백준 13459 - (Java) 구슬 탈출
https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 1. 유형 구현, dfs 2. 문제 접근 2-1. 설계 2-2. 설명 먼저 dfs를 사용했습니다. 제한 조건에 구슬 이동을 총 10번만 한다고 했으므로, 모든 경우의 수를 따져보면 4^10입니다. 백만 정도밖에 되지 않기 때문에 모든 경우의 수를 따져봤습니다. 위에 설계도처럼 이동하다가 주의할 점은 red와 blue가 겹치는 경우입니다. 그럼 위의 경..
백준 14923 - (Java) 미로 탈출
https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 1. 유형 BFS 2. 문제 접근 BFS 유형 중에서 3차원 배열을 사용하는 문제입니다. 위의 예시를 들어봅시다. 만약 3차원 방문배열이 아닌, 2차원 방문 배열을 한다고 가정합시다. 초록색 루트로 (1,1)을 탐색해버리고 방문체크를 합니다. 그러고 나서 빨간색 루트로 (1,1)을 탐색할 때는 이미 방문 체크가 되어있으니, (1,1)에 접근할 수 없습니다. 그러면 결국 (2,1)..
백준 18113 - (Java)그르다 김가놈
https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 1. 유형 이분탐색 2. 문제 접근 이 문제는 이분탐색 문제입니다. 저는 맨 처음 문제를 잘못이해서 계속 틀렸습니다. "김밥 길이가 K cm이거나 그보다 짧으면 그 김밥은 폐기한다." 이 부분에 조심해야 됩니다. 만약 첫번째 테스트 케이스에서 김밥길이 13이 들어올 경우, K=6일때 양쪽을 자르고 남은 길이는 1입니다. 이 길이는 위의 조건 때문에 폐기 ..
백준 15659 - (Java) 연산자 끼워넣기(3)
https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 1. 유형 조합 2. 문제 분석 기호들의 갯수가 인풋값으로 주어집니다. 이것들은 조합을 구해주면 됩니다. 아무래도 이 문제가 까다로운건 우선순위 계산 때문인거 같습니다. 예시) 1+2*3+4 라는 예시를 들면, 곱하기가 먼저 계산되어 11이 정답입니다. 아래는 시뮬레이션을 돌린것입니다. 더하기, 빼기가 나오면 리스트에 저장하고, 곱하기..
백준 2422 - (Java) 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 1. 유형 조합, 브루트포스 2. 문제 접근 조합을 두 가지 방법으로 구현했습니다. 선택을 하고, 안 하는 것을 나타내는 함수 2번 호출 중복 선택을 for문을 통해서 막는 방법 i를 선택했을 경우 그 전 보다 1크게 for문을 시작하기 때문에 중복이 될 수 없음. 3. 코드 import java.util.*; import java.io.*; public cl..