백준44

• [백준 JAVA] 7562 나이트의 이동, BFS(너비 우선 탐색) https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net https://www.acmicpc.net/problem/2178 미로탐색 문제와 아주 유사하다. 너비우선 탐색을 이용하여 이동위치의 값을 갱신해가면서 이동하여 값을 출력한다 큐에는 이동한 거리가 작은 순으로 들어있으므로 최소값을 만족한다. import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.. 알고리즘 2022. 11. 6.

• 

  이진탐색(binary search) 먼저 이진 탐색을 위해서는 내부의 데이터가 정렬되어 있어야 한다. 이진 탐색을 위해서는 시작점 start, end, mid 를 이용하여 탐색한다 찾으려는 데이터와 중간점 위치의 데이터를 비교하며 반복하면서 데이터를 찾는다. 와 같은 과정으로 탐색해 나간다. - python 코드 def binary_search(arr,goal,start,end): if start>end: return None mid = (start+end)//2 if arr[mid]==goal: return mid elif arr[mid]>goal: return binary_search(arr,goal,start,mid-1) else: return binary_search(arr,goal,mid+1,end) def binary_searc.. 알고리즘 2022. 11. 5.

• 

  [백준 JAVA] 16724 피리부는 사나이 백준 자바 16724 피리 부는 사나이 BFS 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net [문제 풀이 방법] 사이클을 따라서 방문 처리되지 않은 원소(0인 원소들) 들을 방문 처리하면서 길을 따라가다가 만약 이전에 방문했던 곳이면 사이클을 따라 safezone이 하나 있어야 하므로 safezone을 하나 증가시켜야 한다 하지만 만약 사이클을 따라가다가 이전에(이번 턴이 아닌) 방문처리가 된 원소라면 이미 이전 턴의 사이클에 safezone이 존재하므로 safezone을 .. 알고리즘 2022. 10. 25.

• 

  [백준 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] 14889 스타트와 링크, 합 이용 [문제링크] 스타트와 링크 실버2 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 팀원이 되는경우 계산하는 부분을 두 가지로 나누어 코딩하였다. [1번 풀이] vistied 되었다면 A팀으로 생각하여 백트랙킹후 이중포문으로 계산 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public .. 알고리즘 2022. 10. 19.

• 

  [백준 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] 10942 팰린드롬? 자바 10942 팰린드롬 dp https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 시간제한이 0.5초이고 메모리 제한이 커서 dp를 이용해서 저장해 두고 테스트 케이스에 대해서 계산된 값을 출력해야겠다고 생각했다. dp 테이블에는 팰린드롬이라면 1을 저장하고 아니면 0을 저장하였다. 포인트라고 생각한 아이디어는 i ~ j 까지가 팰린드롬인지를 확인하기 위해서 input[ i ]와 input[ j ]를 비교하고 i+1과 j-1까지가 팰린드롬 인지를 확인하면 된다. 예를 들어 만약 테스트 .. 알고리즘 2022. 10. 13.

• 

  [백준 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.