알고리즘41

• 

  [백준 java] 2166 다각형의 면적 백준 boj 2166 다각형의 면적 골드 5 🔗 문제링크 🔗 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 🌟 생각 흐름 🌟 문제를 읽고 다각형의 면적을 구하는 방법이 있을 것 같아 구글링을 했다 아래 페이지를 참조하여 구현하였다. 다각형 넓이 구하기: 15 단계 (이미지 포함) - wikiHow 다각형의 넓이를 계산하는 일은 정삼각형 넓이를 구하는 것처럼 간단하기도 하지만 각 변의 길이가 다른 11각형의 넓이를 구하는 것처럼 복잡하기도 합니다. 다양한 다각형의 넓이를 구하는 방 ko.wikihow.com 위에 페이지에서 참조한 부분.. 알고리즘 2022. 10. 25.

• 

  [백준 java] 2225번 합분해 DP https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [문제 풀이] arr[a][b] -> a개의 숫자를 이용해서 b를 만들수 있는 경우의 수 1개의 숫자를 이용해서 b를 만들수 있는 경우는 무조건 1개 임으로 1로 초기화 한다. arr[a][b]=arr[a-1][b]+arr[a][b-1] arr[3][2] = 002,020,200,110,101,011 (6) arr[4][1] = 0001,0010,0100,1000 (4) arr[4][2] = 0002,0020,0200, 0110,0101,0011,1001,1010,1100, 2000 (10) arr[3][2]의 앞에 0을 .. 알고리즘 2022. 10. 23.

• 

  [백준 Java] 2638 치즈 [문제 링크] boj 2638 치즈 골드 3 자바 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [생각 흐름] init 함수에서 배열에서 바깥쪽을 모두 -1로 초기화하고 안쪽에 있는 것과 다르게 표기한다. 이때 만약 치즈가 있는 칸이 하나도 없다면 true를 리턴하여 더 이상 진행하지 않도록 해준다. 이후에 remove 함수에서 치즈가 있는 칸이라면 4면 중 2면이 -1로 노출되어 있는 치즈 인지 확인하고 노출되어있다면 본 배열의.. 알고리즘 2022. 10. 17.

• 

  [백준 JAVA] 1644 소수의 연속합 [문제 링크] 자바 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [생각 흐름] 먼저 에라토스테네스의 체를 이용하여 목표하는 값 이하까지의 소수 배열을 구한다. 이후에 투 포인터를 활용하여 만약 goal 값보다 현재값이 커지면 left를 오른쪽으로 옮기고 , goal 보다 작아지면 right를 오른쪽으로 옮겨 가면서 계산한다.(현재 sum에는 left~right까지의 배열의 합이 들어있다) 만약 목표값과 같으면 cnt를 하나 증가시키고 오른쪽을 증가시키도록 한다 종료시점은 right가 끝에 닿을 때까지 진행하도록 하였다. left를 확인하.. 알고리즘 2022. 10. 14.

• 

  [백준 java] 2473 세 용액 [문제링크] 자바 2473 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투 포인터를 이용하여 해결하였다. 3가지를 선택하는 경우를 전체 포문을 이용하여 0~n 까지를 기준으로 두고 정렬이 된 배열에서 left(왼쪽 포인트), right(오른쪽 포인트)를 이동하여 가장 작은 값을계산 하였다.(두 용액에서 했던방식과 같음) 만약 temp < 0 이면 left 를 증가시켜서 덜 감소되도록 하고 0 < temp 이면 .. 카테고리 없음 2022. 10. 12.

• 

  [백준 JAVA]13172 시그마 Σ [문제링크] Σ 13172 백준 자바 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net [코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final long mod =1000000007; private static long solution(long n, .. 카테고리 없음 2022. 10. 7.

• 

  [백준 JAVA]1806 부분합 [문제 링크] 백준 자바 1806 부분합 투포인터 누적합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net [생각 흐름] 투 포인터를 활용하여 문제를 해결했다. 먼저 만약 입력 값이 이미 원하는 값 이상이면 최소 길이가 1 임으로 브레이크하고 반환하였다. 그 이후에는 먼저 원하는 목푯값보다 클 때까지 right를 오른쪽으로 이동하면 더해간다. 만약 현재 값을 더했을 때 목푯값보다 커진다면 길이를 right-left+1과 ans 중 .. 알고리즘 2022. 10. 7.

• 

  [백준 JAVA] 2239 스도쿠 풀이 [문제 링크] 자바 2239 스도쿠 java 풀이 백트랙킹, 구현 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net [생각 흐름] 여러가지가 있다면 사전식 출력을 원하고 있어서 1~9까지 모든 숫자를 가능하면 넣어 보는 식으로 해결했다. 먼저 칸이 빈칸이라면 arraylist에 넣어두고 DFS를 첫 빈칸부터 시작하도록 하였다. 현재 채울 칸의 가로와 세로, 정사각형 칸을 비교하고 가능하면 넣었다. 그리고 다음 빈칸 을 진행할 수 있도록 하였.. 알고리즘 2022. 10. 5.

• 

  [백준 Java] 11053 가장 긴 증가하는 부분 수열 (DP) [문제 링크] boj 11053 가장 긴 증가하는 부분 수열 자바 풀이 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [생각 흐름] dp(다이나믹 프로그래밍)을 이용하여 문제를 해결했다. 앞에서부터 arr[i]를 포함한다는 전제로(일종의 기준점) arr[i]보다 작고(arr[i]보다 작아야 arr[i]가 커서 증가하는 부분 수열 이므로) sum[j]( 0~j까지의 .. 알고리즘 2022. 10. 2.

• 

  [백준 JAVA]14502_연구소 [문제 링크] 14502 boj 연구소 자바 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [생각 흐름] 문제는 연구실에 바이러스가 최대한 안 퍼지게 할 수 있는 벽을 3개 세우는 문제이다. 처음에는 모든 경우에 3개 벽을 세우는 것을 계산하여 문제를 푸는 것인지 고민했다 (설마 완탐..? ) 예제를 보다가 내가 계산하는 것도 어렵게 느껴져서 그냥 완탐으로 풀이하였다. 일단 백 트랙킹을 이용하여 벽을 3개 어떻게 세울 건지 고려하고, 각각의 경우에 대해서.. 알고리즘 2022. 9. 29.

• [백준] 14938_서강그라운드_플로이드 워셜 [문제 링크] boj 14983 서강 그라운드 플로이드워셜 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [생각 흐름] 처음에는 예시에서 한 지점을 두고 설명하길래 다익스트라로 해결하는 문제인 줄 알았는데 input값을 보고 플로이드 워셜로 해결해야겠다고 생각했다. 플로이드 워셜로 위치에서의 가장 짧은 distance를 구한후에, 각 지점에서 탐색 가능한 범위인 경우 stock[city]를 더하여 저장하고 값들 중 최대값을 계산하여 출력하였다. [.. 알고리즘 2022. 9. 28.

• [백준]12851_숨바꼭질 2 [문제 링크] boj 12851 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [생각 흐름] 이전에 숨바꼭질 문제 3번과 동일한 문제 유형이었다. 추가적인 문제 조건으로 몇 가지의 방법으로 최단시간에 도착할 수 있는지가 포인트였다. 먼저 동생보다 수빈이가 앞에 있다면 n-m을 리턴해준다, 만약 같은 자리에 있어도 바로 리턴해준다 여기서 가는 방법의 수는 한 가지이므로 한가지 이고, 이를 생각하.. 알고리즘 2022. 9. 28.