본문 바로가기

알고리즘15

[Java] 백준 1644번 소수의 연속합 952hi의 접근방법 1. 문제접근 1)2이상 N이하 소수를 구해야 합을 구할 수 있겠다. 소수를 구하려면 에라토스테네스의 체를 사용해야겠다고 생각이 바로 들었다. 에라토스테네스의 체를 간단하게 설명하자면 2부터 N의 제곱근까지 범위에서 체크하지않은 수가 들어오면 소수로 판단하고 소수의 배수 전부를 체크배열에서 체크해 다음 소수판단에서 삭제하는 알고리즘이다 시간복잡도가 O(N/2)으로 굉장히 빠르다. 2)구한 소수를 연속으로 합쳐 주어진 N을 만들 수 있는지 판단해야겠다. 구한 소수 체크배열을 통해 체크안된 값은 소수이므로 리스트로 구현해 N이 굉장히 클때 탐색시간을 줄여야겠다고 생각했고 슬라이딩윈도우방식으로 매번 소수의 합을 구하고 N보다 작으면 윈도우 크기를 크게만들고 N보다 커지면 중지시켰다. 2. 느낀점 처음에 목표값.. 2022. 6. 13.
[Java] 백준 11505번 구간 곱 구하기 문제 952hi의 접근방법 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 1. 문제접근 구간 합이나 곱은 기존 for문 방식으로 더하거나 곱하면 만약 1~n까지의 합을 구해야 한다면 시간이 O(n) 소요된다. 하지만 이문제같은경우 100만개의 원소를 업데이트와 값갱신까지 계속 해서 한다면 더욱 많은 시간이 소요되기 때문에 세그먼트 트리 문제라고 확신을 가지고 문제를 풀게 되었습니다. 세그먼트 트리의 개념을 .. 2022. 5. 19.
[Java] 백준 2096번 내려가기 문제 952hi의 접근방법 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 접근방법 문제를 읽자마자 백준에서 RGB거리라는 문제가 생각이 났다. 크게 다를게 없어서 바로 dp 다이나믹 프로그래밍 알고리즘을 사용해서 문제를 풀었다. 간단하게 1번열은 직전 1,2 열 2번열은 직전 1,2,3열 3번열은 직전 2,3열의 영향이 다음으로 합쳐지는 방식이기 때문에 dp를 사용했고 3차원배열을 사용해 최소 최대를 구해줬다. 2. 느낀점 다 풀고 3차원배열안쓰면 더 빠를거 같은 느낌이 들긴했.. 2022. 5. 12.
[Java] 백준 1194번 달이 차오른다, 가자. 문제 952hi의 접근방법 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. 접근방법 길 찾기 문제는 bfs라는 공식을 매번 기억하고 있었는데 왠지 dfs로 재귀를 타고 싶었다. dfs나 bfs 문제 둘다 중복방문 처리가 핵심이라고 생각했다. 처음 문제를 읽고 알파벳 a~z 모두 등장한다고 생각해서 알파뱃 개수인 26개 배열과 키의 개수를 가지고 재귀를 돌리면서 매번 4방탐색을 해준다면 가뿐하다고 생각했다. 그런데 시간초과를 발생했다. .. 2022. 5. 12.
[Java] 백준 1414 불우이웃돕기 952hi의 접근방법 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 1. 접근방법 처음 설명을 읽을때 이해가안돼서 이해안된상태로 시작하는게 아닌 충분히 이해가 될때까지 문제만 읽었다. 문제를 읽으면서 가장 최소 랜선의 길이를 구하고 각 컴퓨터가 모두 연결을 시켜야 한다는 점에서 MST 최소신장트리 알고리즘이 생각이 났다. 결론적으로는 크루스칼과 프림 둘중 하나를 선택해서 구현해야했다. 나는 크루스칼을 선택해서 사용했는데 프림은 간선이 많을때 이득이라고 생각했.. 2022. 4. 21.
[Java] 백준 11054 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 문제바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 접근방법 1. dp기반의 LIS 알고리즘을 사용해야겠다 생각함 2. 처음에는 문제를 잘못이해해서 좌우로 같은 거리만큼 떨어진것이 바이토닉 수열인줄알아서 우측방향 LIS 왼쪽방향 LIS을 통해 각 인덱스별로 값이 같은거를 출력해주려고했음 3. 손으로 숫자 적어보면서 그냥 좌우로 길기만 하면된다고 판단해서 같은게 아닌 더해서 가장 큰값을 출력해주면 됐음 2. 실수 1. ->진행방향는 괜찮았지만 2022. 4. 11.
[Java] 백준 1613 역사 https://www.acmicpc.net/problem/1613 문제바로가기 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 1. 접근방법 1. dfs, bfs, 다익스트라, 플로이드워셜로 풀 수 있겠다고 생각이 들었음. 2. 플로이드워셜을 자주 사용안해서 사용하기로 했음. 2. 실수 값이 뭐가 큰지 헷갈렸다 그러니까 어떤게 더 먼저 일어났는지 헷갈려서 바꿔줬음. 3. 코드 import java.io.*; import java.util.*; public class boj1613 { public sta.. 2022. 4. 11.
[JAVA] 백준 1929 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 클래스2++도전기 나만의 문제접근방법 1. 소수는 약수가 1과 그수 자신인 숫자라고 알고 있었다. 2. 시작이 3 끝이 16이면 3부터 반복문을통해 일차원적으로 소수인지 아닌지 검토하는 방식 -> 시간초과 메모리간당간당 3. 뭔가 알고리즘이 있을것같아 찾아보니 에라토스테네스의 체라는 알고리즘을 사용하거나 더 뛰어난 알고리즘을 사용해야했었다. 4. 간단히 공부 후 코드를 작성해 제출했음 어려웠던 점 출력해줄때 0,1을 예외처리해주.. 2022. 3. 28.
[JAVA] 17404 RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 접근방법 1) 문제를 읽고 바로 dp라고 생각이 들었다 1행이 2행에 영향이 있고 ... N행까지 영향을 주니까 2) 첫번째집을 R G B 각각 선택했을때 N행에서 만약 첫행 선택한 색이 R을 선택했다면 마지막행 R은 최솟값 선택에서 제외 3) 아래 그림을 그리면서 아이디어 획득함 이전 행에서 현재 색을 제외하고 최소값을 구해준다. 예를 들면 현재 레드2행 이라면 1행.. 2022. 3. 27.
[Java] 백준 2164 카드2 https://www.acmicpc.net/problem/2164 문제바로가기 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 백준 스트릭 2++ 100% 도전기 문제접근방법 1) 카드를 세워서 처음 맨위카드는 버리고 그다음 카드는 맨뒤로 보낸다라는 글을 읽고 앞뒤 => 큐를 써야겠다 2) 반복문을 통해 뽑아 버리고 맨뒤로 보내고를 반복했다. 느낀점 크게 어렵지 않은데 다른사람들이 푼 숏코딩을 보니 더좋은 방법이 많아서 최적화를 더할수 있을것 같았다. import java.io.*; import java.ut.. 2022. 3. 27.
[JAVA] 백준 4153 직각삼각형 https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 2++ 클래스 도전기 접근방식 1. 문제설명과 그림을 통해 피타고라스 정리를 통해 직각삼각형을 유추한다고 판단 2. 0,0,0 들어오면 끝내주고 배열로 받아드려 정렬하고 가장큰수를 대각선으로 잡아서 피타고라스 정리 3. 값이 서로 같으면 직각삼각형 아니면 직각삼각형 아님으로 판단 느낀점 3만개의 입력이 들어오는데 이부분을 system.out.println으로 하면 시간을 많으 잡아 먹을것 같다 그래서 버퍼드라이터와.. 2022. 3. 24.
[JAVA] 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근방법 1. 기본적으로 최단거리 찾기 문제라 바로 BFS가 떠올랐다. 2. BFS 돌릴때 모든 맵의 벽을 모두 한번씩 지워보며 가면 정답이 나오겠네 시간초과 (맞왜틀?) 3. 그럼 가는길에 부술수있으면 부수고 아니면 그냥 갈길 가면서 BFS 타보자 시간초과,메모리 (맞왜틀?) 4. 갈때 부순경우 안부순경우 모두 체크해서 큐에 넣자 (이게맞네?) 느낀점 고정관념을 버려야 .. 2022. 3. 24.

티스토리툴바