전체 글
백준 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..