알고리즘/백준
백준 2609 - 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609 1. 유형 수학 2. 풀이 유클리드 호제법으로 최대공약수 구한다. 최대공약수를 구했으면, 최소 공배수도 구하는게 가능 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 a=stoi(st.nextToken()); int b=stoi(s..
백준 22857 - 가장 긴 짝수 연속한 부분 수열(small)
https://www.acmicpc.net/problem/22857 1. 유형 - 투포인터 2. 풀이 - 투포인터 변수 R, L을 잡는다. 시작 인덱스는 0번 - R, L의 사이에 홀수의 갯수가 K개 초과면 L증가, 반대는 R증가 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 N =stoi(st..
[백준 18311] 왕복
https://www.acmicpc.net/problem/18311 18311번: 왕복 첫째 줄에 정수 N, K가 공백을 기준으로 구분되어 주어진다. (1≤N≤100,000) 단, K는 항상 왕복 거리보다 작은 양의 정수 혹은 0으로 주어진다. 둘째 줄에 1번부터 N번까지 각 코스의 길이가 공백을 www.acmicpc.net 1. 유형 구현 2. 풀이 반복문을 돌면서 K에서 입력값을 뺴준다. 가는 경우, 오는 경우를 나눠서 생각. 0미만인 경우 index+1을 출력 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..
[백준] 1446 지름길
https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 1. 유형 완전탐색, 다익스트라 2. 풀이 첫번째 풀이, 완전탐색 총 12개의 값만 주어지기 때문에 완전탐색으로 충분히 구할 수 있다. 1. 시작, 도착지 기준으로 정렬 2. 선택을 하는 경우, 안 하는 경우로 나누어 모든 경우 탐색 import java.io.*; import java.util.*; public class Main { static List list; static int..
[백준 1251] 단어 나누기
https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 1. 유형 브루트포스 2. 풀이 문자열 최대 길이가 50이고, 자를 두 곳을 선택해야한다 그럼 문제를 50개 중에서 2개를 선택으로 바꿔서 풀면 쉽다. 1. 전역 탐색으로 숫자 2개를 선택 2. 뒤집고 전부 합친다 3. 정렬한다 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[]..
[백준 9996] 한국이 그리울 땐 서버에 접속하지
https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 1. 유형 문자열 2. 풀이 1. 별표 기준으로 좌우 나누기 2-1 좌우길이가 비교문자열의 초과인 경우 NE 2-2. 이하인 경우 앞뒤 비교 3-1. 좌우가 비교 문자열과 일치하면 DA 3-2. 불일치하면 NE 3. 코드 import java.io.*; import java.util.*; public class Main { public static void mai..
백준 16439 - 치킨치킨치킨
[문제 바로가기] 1. 유형 브루트포스 2. 풀이 1. M까지의 수 중에서 3개를 조합을 선택 2. 각 경우의 수 마다 최대값 구함 3. 코드 import java.io.*; import java.util.*; public class BOJ_16439_치킨치킨치킨 { static int N, M, ans; static int arr[][]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N=stoi(st.nextT..
백준 16439 - 치킨치킨치킨
[문제 바로가기] 1. 유형 이분탐색 2. 풀이 문제를 파악하고 이분탐색을 생각할 수 있어야하는 문제였습니다. 구현 난이도는 기본적인 이분탐색만 할 수 있으면 가능한 문제였습니다. 1. 왼쪽 오른쪽 값 초기화 2. 이분탐색 진행 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 N = stoi(st..
백준 15970 - 화살표 그리기
[문제 바로가기] 1. 유형 정렬, 브루트포스 2. 풀이 점의 범위가 100000이기 때문에 O(N^2)이면 시간초과입니다. 따라서 동적프로그래밍을 썼습니다. 설계 1) 위치 순서대로 입력값 정렬 2) 색깔별로 큐 배열 만들고, 같은 색 끼리 큐에 삽입(굳이 큐를 사용안하고 배열 사용해도 됨) 3) 같은 색 끼리의 위치를 빼서 DP에 최소값 저장 예제1을 기준으로 설명하면, 색깔1의 위치는 0, 3, 5 순서로 입력됩니다. 0과 3의 차이는 3이고, DP[0]=3, DP[3]=3 을 입력. 3과 5의 차이는 2이고, DP[3]=2 (기존 값이 3이었는데, 2가 더 작으므로 초기화), DP[5]=2 위 과정을 색깔별로 해주면 됩니다. 3. 코드 import java.io.*; import java.util..
백준 16987 - 계란으로 계란치기
[문제 바로가기] 1. 유형 브루트포스 DFS 백트래킹 2. 풀이 DFS를 쓰는 문제였습니다. 처음에 한글 이해하는게 조금 힘들었습니다. 2-1. 설계 2-2. 코드 풀이 3. 코드 import java.io.*; import java.util.*; public class Main { static int N, answer; static int arr[][]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = s..
백준 16953 - A -> B
[문제 바로가기] 1. 유형 BFS 2. 풀이 뒤에 1이 붙는 경우, 2를 곱하는 경우를 모두 탐색해 줍니다. 2차원 배열 BFS에서 4방향을 완전 탐색을 하는 경우와 비슷합니다. 여기서 주의할 점은 인풋값이 십억이므로, 뒤에 1을 붙이는 경우는 int타입을 초과할 가능성이 있습니다. 그래서 long타입을 사용합니다. 3. 코드 import java.io.*; import java.util.*; public class Main{ static int N, M; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Strin..
백준 5883 - 아이폰 9S
[문제 바로가기] 1. 유형 구현 2. 풀이 N이 1000이어서, O(N^2)으로 충분히 풀이 가능. 예제1을 보면 지울 수 있는 숫자 후보는 2,3,5,7 입니다. 위 숫자를 지운 상태에서 N번 탐색하는 식으로 구해주면 됩니다. 중복 체크를 해주기 위해 HashSet에 입력값을 넣어요. 이전값과 비교해가면서 가장 긴 숫자를 찾아요. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..
백준 17393 - 다이나믹롤러
[문제 바로가기] 1. 유형 이분탐색 2. 풀이 3. 풀이 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); int N = Integer.valueOf(st.nextToken()); long arr[] = new long[N]; long arr2[] = new long[N]; st = new StringTokeniz..
백준 - 좋은 단어
1. 유형 스택 2. 풀이 간단한 스택문제입니다. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); int N = stoi(st.nextToken()); int cnt= 0 ; while(N-->0) { st = new StringTokenizer(bf.readLine()); char[] c = st.ne..
백준 21608 - 상어 초등학교
[문제 바로가기] 1. 유형 구현 2. 문제 분석 21년 상반기 문제입니다. SDI를 지원했을 때 오전 타임 1번으로 나온 문제라서 반갑네요. 유형은 우선순위 큐를 사용해야 하고, 기준을 잘 설정해야 해요. 주변에 친구가 많은 칸을 선택, 주변에 빈칸이 많은곳선택 -> 행번호오름차순->열번호 오름차순 저 같은 경우엔 람다식+배열을 많이 써요. 코테 칠 때 클래스를 만들고 Comparable을 구현한 후 컬렉션에 넣으면 시간이 많이 소요됩니다. 나머지 조건 쉽습니다. 4방향을 탐색해주면서 주변에 친구가 있으면 카운트를 증가시켜요. 친구 여부는 Set으로 판단해줬습니다. 4방향 탐색하면서 빈칸이 있으면 빈칸 수 를 증가시켜주고 우선순위 큐에 삽입하면 됩니다. 설계 총 N^2을 탐색 -> 빈칸중에서 -> 친구..
백준 1780 - 종이의 개수
[문제 바로가기] 1. 유형 분할 정복 2. 접근법 2-1. 해설 분할 정복으로 푸는 문제 입니다. 전체 사각형을 기준으로 잡고, 세부 사각형이 모두 같은지 판단해 줍니다. [그림1]과 같은 사각형이 있다고 가정하겠습니다. 길이가 3일 때, 모두 같은지를 판단 합니다. 0과 1이 같이 있으니 분할 정복을 시도합니다. 위의 코드를 따르면 [그림2] 처럼 나올겁니다. 이제 위의 코드를 계속 반복하면 끝! 2-2. 설계 전체가 같은 값 일 수 있으니 체크 -> DFS(큰변, 작은변, 좌표)를 호출 -> 작은 사각형이 동일 한지 여부에 따라 종이의 수 증가. 3. 코드 import java.io.*; import java.util.*; public class Main { static int N, grid[][]..
백준 2665 - 미로만들기
[문제 바로가기] 1. 유형 BFS 2. 문제 풀이 2-1. 해설 BFS에서 파생된 문제 중 하나인 벽 뚫기 문제입니다. 만약 이 문제를 DFS 그냥 정말 탐색하게 된다면 시간 초과가 날 것입니다. 따라서 이 문제는 우선순위 큐를 사용한 BFS로 풀어야 합니다. 벽을 몇 번 뚫을지 딱 정해주지 않았습니다. 그래서 만나는 벽을 모두 큐에 넣어주면서 탐색해 줘야 합니다. 우선순위 큐의 정렬 기준은 적게 벽을 통과한 횟수입니다. 벽을 뚫지 않은 길을 먼저 탐색하는 거죠. 마지막 좌표에 도달했으면 벽을 파괴한 횟수 출력. 끝! 핵심코드. Queue pq = new PriorityQueue((a,b) ->{return a[2]-b[2];}); 3. 코드 import java.io.*; import java.uti..
백준 1005 - ACM Craft
[문제 바로가기] 1. 유형 위상 정렬, 동적 프로그래밍 2. 문제 접근 2-1. 설계 기본적인 위상 정렬 템플릿을 사용하고, 거기다가 DP를 추가한 문제입니다. 2-2. 풀이법 1. 가장 처음에 차수(해당 노드에 들어 노는 선분 수)를 초기화합니다. 2. 차수가 0인 것만 큐에 넣습니다 3. 큐에서 하나씩 꺼내면서 연결된 노드를 탐색합니다. 그리고 차수를 하나씩 감소시키고, 해당 노드까지의 누적 가중치를 갱신합니다. 3-1. 만약 차수가 0이 되면 큐에 집어넣습니다. 4. 3번을 큐가 빌 때까지 반복합니다. 끝. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) thro..
백준 17265 - 나의 인생에는 수학과
[문제 바로가기] 1. 유형 DFS 2. 문제 설명 N이 5이기 때문에 총 경우의 수 N*N*2로 충분히 시간내에 들어오는 것이 가능합니다. 일반적인 현재 좌표가 숫자인지 기호인지에 따라 조건문으로 분기합니다. 그리고 일반적인 DFS템플릿을 사용하면 됩니다. 3. 코드 import java.io.*; import java.util.*; //나의 인생에는 수학과 함계 public class Main { static char[][] mat; static int D[][] = { { 0, 1 }, { 1, 0 } }, N, MAXVAL = -Integer.MAX_VALUE, MINVAL = Integer.MAX_VALUE; public static void main(String[] args) throws IO..
백준 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개 이상일 수 있습니다. 따라서 둘 중에 최댓값이..