고양멍멍이

[문제링크] 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 0. 소수 구하기 + 연속합 문제 1. 소수 구하기 : 에라토스테네스의 체로 구하면서, 투포인터 사용시 편리하도록 ArrayList에 저장하였다 2. 누적합 구하기 - N보다 같거나 커질때까지 더하며 진행 - N보다 같거나 작아질때까지 빼며 진행 - 원소가 하나만 남을 경우 2번 카운트되는 문제가 있어 prevFst를 두어 방지하였다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { public static void m..

[문제링크] SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 0. 한번의 클릭으로 하나 이상의 칸을 처리할 수 있는건 0인 칸 뿐이다 1. 미리 지뢰가 아닌 칸의 개수를 세둔다 (cnt) 2. 주변 지뢰의 갯수로 정답 배열을 미리 만들어놓고, 0이면서 처리되지 않은 칸에 대해서만 재귀로 주변 처리 - 한 칸 처리할때마다 cnt에서 1씩 뺀다 3. 모든 0에 대해 처리하고 나면, 나머지 칸들은 하나하나 직접 눌러줘야한다 (남은 cnt만큼) 4. 0을 누른 횟수 + 나머지를 누른 횟수 = 정답 import java.io.BufferedReader; import java.io.InputStreamReader; pub..

[문제링크] 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 0. 메모리제이션을 이용해 동일 지점에 대한 중복연산을 피한다 - 1-2-3-4-5 루트와 6-7-3-4-5 루트는 3-4-5가 겹치니 연산 결과를 저장, 결과가 존재하지 않을때만 사용 1. 주변에 진행할 방향이 없어도 1만큼은 살 수 있으므로, cache배열은 초깃값 0을 유지 2. 아직 거쳐가지 않은 장소마다 rec함수로 살 수 있는 최대 년수를 확인한다 - 검사한 모든 경로의 cache에 결과값을 저장함으로서, 재방문시 즉시 반환되도록..

[문제링크] SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 0. x,y지점에서 총 m칸, 최대 무게 c를 고려해 채취할 수 있는 꿀의 최대 가치는 항상 동일하다 - 미리 연산해서 저장 후 활용한다 1. 위에서 구한 가치들 중, 구간이 겹치지 않으면서 가치의 합이 최대가 되는 두 구역을 찾는다 2. 가치가 큰 순서로 정렬한다 - 최대 가치 구간을 한 구간으로 잡고 그리디하게 계산한 최댓값이 최댓값이 아니려면 - 최대 가치 구간과 영역이 겹치는 다른 구간에서 나온 값만이 가능하다 3. 영역이 겹치는 구간의 수는 2*m-1개로, 정렬된 구간을 그만큼만 살펴보면 - 그리디하게 구한 결과의 가능한 모든 반례를 고려한 ..

[문제링크] 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 0. 벨만-포드 알고리즘 1. 시작노드로부터, 모든 도로에 대해 n-1번 갱신하면 각 노드까지의 최소 거리 2. 한번 더 돌렸을때 변동되는 값이 존재한다면 음수 cycle이 존재하기 때문 3. 도달할 수 없는 노드도 갱신하도록 해 시작노드와 연결되지 않아도 음수 사이클은 탐지 가능 * 현재 코드는 a->b가 갱신됬을 때, 같은 단계에서 갱신된 b로 인해 b->c의 결과도 변할 수 있는 코드 - 음수 사이클이 있다면 n번째 단계의 결과값은..

[문제링크] 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 0. SWEA 보급로 문제의 열화판 (링크) 1. BFS를 이용해 1,1부터 N,M까지 탐색 * 1,1 노드부터 N,M노드까지 최소 거리를 구하는 다익스트라로 풀이 가능 - 노드의 값 = 노드까지의 cost import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import..

[문제링크] 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 0. 작은사람 -> 큰 사람 정보를 단방향 그래프로 표현 1. 플로이드 와샬 실행, 모든 노드에 대해 최솟값을 구한다 2. n번째 학생의 키 순서를 알기 위해선, 다른 모든 학생 k에 대해 - k가 n보다 크거나 : n->k로 가는 길이 존재 - n이 k보다 크거나 : k->n으로 가는 길이 존재 - 둘 중 하나를 만족해야한다 3. 인접행렬의 adj[k][n] 혹은 adj[n][k] 둘 중 하나의 길이 존재해야한다 - 두 값이 다 초깃값을 유지하고있다..

[문제링크] 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 0. CCTV의 종류에 따라 가능한 모든 경우의 수를 해보는 브루트-포스 문제 - 종류별로 가능한 탐색 방향을 미리 저장 1. 2/5번 CCTV는 회전 중 동일한 입력이 있으므로 제거해준다 - 하지 않아도 통과하는데는 문제 없음 2. 매 CCTV마다, 가능한 모든 방향으로 감시해보며 다음으로 진행 - 빈 공간(사각지대)의 개수를 유지, 최솟값 저장 import java.io.BufferedReader; import java.io.InputS..

[문제링크] 1081번: 합 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 0. 1019번, 책 페이지의 코드 재사용 (링크) 1. 두 페이지까지의 숫자를 구해 합을 구하고, 그 차이를 구한다 - L페이지는 포함되야 하므로, 따로 합해준다 * SWEA 5604번 구간합 문제와 거의 동일하다 (링크) - 출력 양식 수정 후 반복문만 돌리면 통과 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { public stati..

[문제링크] SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 0. state 클래스로 정보를 관리 (x좌표, y좌표, 이전이동, 이동횟수) 1. bfs처럼 진행하되, 항상 목표지점으로 다가가는 이동이 최적의 이동이다 - 현재 좌표와 목표좌표를 비교, 나아가야 할 방향을 결정한다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Solution{ static class s..