AngelPlayer`s Diary

[Baekjoon] 백준 15683 감시 (G4^ / DFS) - Java

링크 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해석 - 문제 분석 CCTV는 총 5가지가 존재함 1번 : 1방향 2번 : 대칭적인 2방향 3번 : 수직인 2방향 4번 : 3방향 5번 : 4방향 CCTV는 90도 각도로 회전이 가능함 CCTV는 벽을 뚫을 수 없음 CCTV가 CCTV를 뚫고 감시는 가능 CCTV로 볼 수 없는 사각지대가 최소가 되도록 CCTV를 회전시키기 - 입력 첫 번째 줄 : N M # N=세로, M=가..
개인 공부/코딩 테스트^ 2023. 4. 14. 11:42

[SWEA] 2382. 미생물 격리 (D0^ / 시뮬레이션) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 문제 분석 미생물이 크기와 방향을 가진 채 존재 미생물은 매초마다 한 칸씩 이동 미생물이 이동하는 구역의 외곽에는 약품으로 처리되어 있어 미생물 크기를 반감시킴 (소수점이 나오면 내림 처리) 미생물이 한 칸에 모이는 경우 미생물이 합쳐지며, 이 때 가장 큰 미생물의 방향을 적용시킴 - 입력 첫 번째 줄 : N M K # N=맵크기 | M=시간 | K=미생물개수 나머지 줄 : a ..
개인 공부/코딩 테스트^ 2023. 4. 12. 12:29

[Baekjoon] 백준 14889 스타트와 링크 (D2 / 조합) - Java

링크 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 문제 해석 - 문제 해석 N명의 사람을 두 팀으로 나눠야 함 주어지는 값은 i와j가 팀이 되었을 때 시너지를 나타냄 ij와 ji는 서로 다를 수 있음 두 팀의 능력치 차이가 최소가 되도록 만들기 - 입력 첫 번째 줄 : N # 사람 수 나머지 줄 : 능력치 - 출력 두 팀의 능력치 정도가 최소가 되었을 때 차이 풀이 & 코드 해석 기본적인 완전탐색 문제입니다. 정해진 사람 수로 팀을 나눠야 하므로 조합을 이용하였..
개인 공부/코딩 테스트^ 2023. 4. 11. 11:42

[Baekjoon] 백준 3055 탈출 (G4 / BFS, 던전) - Java

링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해석 맵 크기 : R * C 비어있는 곳 : . 물이 차있는 곳 : * 돌 : X 비버 : D 고슴도치 : S 고슴도치가 비버에게로 도착해야 함 매턴 물은 인접한 빈칸을 채움 고슴도치는 물이 있는 곳을 건널 수 없음 물은 돌이나 비버의 집을 채울 수 없음 - 입력 첫 번째 줄 : R C # 세로 가로 나머지 줄 : 던전 정보 - 출력 건널 수 있다면 숫자 건널 수 없다면 KAKTUS 풀이 & 코드 ..
개인 공부/코딩 테스트^ 2023. 4. 10. 17:36

[Baekjoon] 백준 16919 봄버맨 2 (G4 / 구현) - Java

링크 https://www.acmicpc.net/problem/16919 16919번: 봄버맨 2 첫째 줄에 R, C, N (1 ≤ R, C ≤ 200, 1 ≤ N ≤ 109)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 봄버맨1은 실버 문제로 동일한 문제이지만 시간, 메모리 등의 조건이 다릅니다. 봄버맨2가 어렵다..
개인 공부/코딩 테스트 2023. 4. 9. 10:46

[SWEA] 1486. 장훈이의 높은 선반 (D4 / 순조부) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 점원이 한 명일 때 : 점원의 키 점원이 두 명 이상일 떄 : 탑을 만든 점원의 키의 합 만들 수 있는 높이가 B 이상이면서 가장 낮은 탑의 높이 구하기 - 입력 첫 번째 줄 : N B # N = 점원 수 | B = 탑의 높이 두 번째 줄 : 점원의 키 - 출력 B를 넘는 가장 낮은 탑 - B 풀이 & 코드 해석 문제가 길지만 쉽게 정리하면 점원들의 키를 더하는 경우의 수를 구해서 ..
개인 공부/코딩 테스트 2023. 4. 8. 09:55

[알고리즘] 이항 계수, 파스칼의 삼각형

문제를 풀기 위한 개념 정리 이항 정리 각 항의 계수 값을 구하는 정리를 의미 이항 계수 다항식을 전개했을 때 각 항의 계수를 의미 $(a+b)^{n}$를 전개 했을 때 나오는 임의의 항 $Sx^{n-a}y^{n-b}$ 에서 $S$가 계수 이항 계수 구하기 이항 계수를 구하는 방법은 1) 경우의 수(조합)을 이용한 방법 2) 파스칼의 정리(삼각형)을 이용한 방법 등이 있음 조합을 이용한 풀이 조합을 이용한 풀이 $_{n}C_{r}$는 $_{n-1}C_{r-1} + _{n-1}C_{r}$로 분해할 수 있음 -> 중복이 발생함 -> 12!을 넘어가면 오버플로우가 일어날 수 있음 - 연산 횟수 10! == 360만 11! == 4000만 12! == 1억 이상 - 조합 개념 https://angelplayer..
개인 공부/알고리즘 2023. 4. 7. 16:36

[SWEA] 활주로건설 (D0 / 구현, 완전탐색) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 N * N 크기의 활주로 건설 셀의 숫자는 지형의 높이를 의미 가로 또는 세로로 활주로 건설이 가능한지를 확인하는 문제 활주로는 높이가 같은 경우에만 건설이 가능하며, 높이 다른 경우 경사로를 설치하여 건설이 가능함 경사로는 높이가 1이고 길이가 X임 경사로는 겹쳐서 만들 수 없고, 눕힐 수 없음 - 입력 첫 번째 줄 : N X # N=활주로 크기, X=경사로 길이 나머지 줄 : 지..
개인 공부/코딩 테스트 2023. 4. 6. 10:37

[SWEA] 5643 키 순서 (D4 / 플로이드 워셜) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 키 정보는 A라는 학생과 B라는 학생의 키가 크고 작음을 나타냄 키를 비교할 N명이 존재하고, M개의 키 정보가 주어졌을 때, 자신의 키 순서가 몇 번째인지 알 수 있는 학생의 수를 구하라 - 설명 키 순서가 몇 번째 인지를 확인한다는 것은 바꿔 말하자면, 나보다 키가 큰 사람이 몇 명인지, 그리고 나보다 키가 작은 사람이 몇 명인지를 알 수 있으면 확인 가능합니다. - 입력 첫 번..
개인 공부/코딩 테스트^ 2023. 4. 5. 11:00

[SWEA] 1263 사람 네트워크2 (D6 / 플로이드 워셜) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN&categoryId=AV18P2B6Iu8CFAZN&categoryType=CODE&problemTitle=%EC%82%AC%EB%9E%8C+%EB%84%A4%ED%8A%B8&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 여러 사람들 중 영향력이 가장 큰 사람 구하기 영향력이 큰 사람 ==..
개인 공부/코딩 테스트^ 2023. 4. 4. 11:48

[Baekjoon] 백준 1520 내리막길 (G3 / DP) - Java

링크 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 해석 왼쪽 위 (0, 0)에서 시작하여, 오른쪽 아래(N-1, M-1)에 도착해야한다. 이때 이동하는 경로는 현재 있는 위치보다 낮은(숫자가 작은) 곳만 가능하다. 갈 수 있는 경로의 개수를 구하시오. 아이디어 갈 수 있는 모든 길을 찾아야하므로 dfs를 사용해야 합니다. 단 map의 크기가 500*500이므로 단순 dfs를 사용해서 탐색하기에는 시간초과가 날 가능성이 높습니다. 따라..
개인 공부/코딩 테스트^ 2023. 3. 30. 14:33

[Baekjoon] 백준 1920 수 찾기 (S4 / 이분탐색) - Java

링크 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해석 백준 1920 수 찾기 - 문제 해석 N개의 정수가 주어졌을 때, M개의 정수가 각각 N개의 정수에 포함되는지 여부를 구하라 - 입력 첫 번째 줄 : N # 포함 여부를 확인할 자연수 개수 두 번째 줄 : N개의 자연수 세 번째 줄 : M # 찾으려는 수 개수 네 번째 줄 : M개의 자연수 코드 import java.io.*; imp..
개인 공부/코딩 테스트^ 2023. 3. 13. 10:08

[알고리즘] 이분(이진)탐색

이분 탐색 배열 등 자료를 두 부분으로 쪼개어 탐색하는 방법 특정 값 또는 자료가 존재하는지를 탐색할 때 사용함 이분 탐색을 위한 배열은 정렬되어 있어야 함 - 로직 1) 탐색 배열의 내 중간 인덱스( (시작 인덱스 + 끝 인덱스) / 2 )를 구함 2) 배열[중간 인덱스]에 위치한 값과 찾으려는 값 비교 3) 비교 결과를 통해 반복 여부 결정 3-1) 배열 값과 같으면 중간 인덱스 반환 3-2) 배열 값이 작으면 "중간 인덱스 + 1"를 시작 인덱스로 지정 3-3) 배열 값이 크면 "중간 인덱스 - 1"를 끝 인덱스로 지정 4) 인덱스 범위가 하나가 될 때까지 1) 2) 3)을 반복 -> 만약 인덱스 범위가 1인데 값이 다르다면 해당 값은 존재하지 않는 값 코드 public class 이분탐색_기본 {..
개인 공부/알고리즘 2023. 3. 11. 09:00

[Baekjoon] 1074 Z (S1, 분할정복) - Java

링크 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 해석 - 문제 해석 $2^N * 2^N $크기의 배열을 z모양으로 탐색 이때 r행 c열은 몇 번째 순서에 탐색하는가? - 입력 첫 번째 줄 : N r c # N : 한 변의 길이/2, r : 찾고자 하는 행, c: 찾고자 하는 열 코드 package algo.bj.s1_1074; import java.io.*; import java.util.*; public class Main..
개인 공부/코딩 테스트^ 2023. 3. 10. 16:00

[Baekjoon] 백준 10775 공항 (G2^ / 서로소) - Java

링크 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 문제 해석 - 문제 해석 첫 번째 줄 : N # 게이트의 수 두 번째 줄 : M # 비행기수 세 번째 줄 : a # 1~a까지 비행기가 들어올 수 있음 네 번째 줄 : b # 1~b까지 비행기가 들어올 수 있음 한 대라도 들어올 수 없다면 폐쇄 - 입력 4 # 4개의 게이트 6 # 6대의 비행기 2 # 2번 게이트에 넣음 2 # 1번 게이트에 넣음 3 # 3..
개인 공부/코딩 테스트^ 2023. 3. 8. 10:20

[SWEA] 7465 창용마을무리의개수 (D4 / 서로소) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 각 테스트 케이스 별 입력 첫 번째 줄 : N M # 사람 수, 관계 수 나머지 줄 : 사람1 사람2의 관계 표현 서로 관계..
개인 공부/코딩 테스트 2023. 3. 7. 11:01

[SWEA] 3289 서로소집합 (D4 / 서로소) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 문제 해석 서로소 테스트 결과로 1연산을 띄워쓰기 없이 출력 - 각 테스트 케이스 별 입력 첫 번째 줄 : N M # N : 자연수의 최대 값 / M : 연산의 개수 나머지 줄 : M번의 연산 연산이 0로 시작하면 합집합 연산이 1로 시작하면 확인 연산 코드 import java.io.*; import java.util.*; public class Solution { static..
개인 공부/코딩 테스트 2023. 3. 7. 09:09

[Baekjoon] 백준 13023 ABCDE (G5^ / DFS, 그래프) - Java

링크 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 해석 A -> B -> C -> D -> E 관계를 가지는 친구가 있는지를 구하시오. 코드 package algo.bj.g5_13023; import java.io.*; import java.util.*; public class Main { static ArrayList[] list; static boolean[] v; static int answer; public static void main(String[] args) throws Exception { BufferedReader br = ..
개인 공부/코딩 테스트^ 2023. 3. 6. 09:49

[Baekjoon] 백준 2023 신기한 소수 (G5^ / DFS, 소수) - Java

링크 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 해석 N자릿수를 가지는 숫자 중 신비한 소수(자릿수가 N, N-1, N-2, N-3... 이 모두 소수가 되는 소수)를 출력하라 코드 package algo.bj.g5_2023; import java.io.*; import java.util.*; public class Main2 { static StringBuilder sb; static int N; public static..
개인 공부/코딩 테스트^ 2023. 3. 5. 23:36

[Baekjoon] 백준 11724 연결 요소의 개수 (S2^ / DFS, 그래프) - Java

링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해석 노드 N개, 간선 M개가 주어질 때 연결 요소 구하기 연결 요소 : 연결된 간선으로 연결된 노드들을 하나의 덩어리로 보았을 때, 전체 그래프의 덩어리 개수 코드 import java.io.*; import java.util.*; public class Main { static ArrayList[] list; static..
개인 공부/코딩 테스트^ 2023. 3. 4. 11:06

[SWEA] 5644 무선 충전 (D0 / 시뮬) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=%EB%AC%B4%EC%84%A0+%EC%B6%A9%EC%A0%84&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 문제 해석 사용자가 BC(무선 충전 공간)에 들어오면 충전이 됨 ..
개인 공부/코딩 테스트^ 2023. 3. 3. 11:51

[Baekjoon] 백준 9663 N-Queen (G4^, 백트래킹) - Java

링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 N*N의 체스판에 N 개의 서로 공격을 할 수 없는 Queen을 놓을 수 있는 경우의 수를 구하시오. 코드 import java.io.*; import java.util.*; public class Main { static int[][] map; static int N; static int count; public static void main(String[] args) throws Excepti..
개인 공부/코딩 테스트^ 2023. 3. 2. 11:35

[알고리즘] 최소 신장 트리 (크루스칼, 프림 알고리즘)

최소 신장 트리 (MST) ※ 일반적으로 그래프의 모든 정점이 연결되어 있다고 가정 - 신장 트리 : 모든 정점이 연결되는 트리 - 최소 신장 트리 : 신장 트리 중 사용된 간선들의 가중치가 가장 작은 간선으로만 연결된 트리 - V : 정점 - E : 간선 - 최소 신장 트리의 조건 무방향 가중치 합이 최소 간선의 개수는 $V-1$개 사이클이 없어야 함 - 활용 도시간 비용을 최소화 하는 문제 등에서 사용함 최소 신장 트리를 만드는 방법은 크루스칼과 프림 알고리즘이 있음 크루스칼 알고리즘 (Kruskal Algorithm) - 특징 간선 리스트를 사용 간선을 가중치 기준으로 정렬이 먼저 이뤄저야 함 (간선이 적으면 유리) 순환 여부는 서로소를 통하여 검사함 (매 간선 선택마다 정점의 대표를 확인) 그리디..
개인 공부/알고리즘 2023. 3. 1. 15:00

[Baekjoon] 1992 쿼드트리 (S1, 분할정복) - Java

링크 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해석 배열 전체를 바라봤을 때 모두 0이거나 1일 때 해당 값을 출력함 만약 배열 전체가 0또는 1로 이뤄져 있지 않을 때, 해당 배열을 4개로 쪼개서 다시 배열을 확인함, 단 쪼개지는 경우 괄호로 묶어서 표시함 코드 package algo.bj.s1_1992; import java.io.*; import java.util.*; public class Main { stati..
개인 공부/코딩 테스트 2023. 2. 28. 18:48

[알고리즘] 서로소 집합

서로소 서로소 집합 서로 중복된 원소가 없는 집합을 의미 == 교집합이 없는 집합 집합에 속한 특정 멤버(대표자)를 통해 집합을 구분 대표자는 어떤 데이터가 되든 상관이 없음 하나의 집합에는 오로지 하나의 대표자만 가질 수 있음 서로소 집합 연산 1) init : 초기화 2) union : 두 개의 집합을 하나의 집합으로 결합 3) find : 집합 내의 대표자를 찾음 서로소의 최적화 - Rank 사용 기본 서로소 함수에서는 부모를 찾을 때 find의 재귀가 여러 번 발생함 -> 두 서로소를 결합할 때 더 낮은 트리를 더 높은 트리의 자식으로 결합하면 효율성을 높일 수 있음 (데이터에 따라서 사용하지 않을 때 더 빠른 경우가 있음) - Path 사용 find함수의 재귀가 발생하여 부모의 결과를 찾으면, ..
개인 공부/알고리즘 2023. 2. 28. 08:11

[Baekjoon] 백준 7576 토마토 (G5^ / BFS) - Java

링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 해석 1 : 익은 토마토 0 : 익지 않은 토마토 -1 : 빈 칸 (벽) 익은 토마토는 인접한 토마토에 영향을 미침 토마토들이 모두 익는데 걸리는 시간을 구하기 단, 익지 못하는 토마토가 있다면 -1을 결과로 출력 코드 import java.io.*; import java.util.*; public class Main { static int[][] map; static ..
개인 공부/코딩 테스트^ 2023. 2. 27. 12:48

[SWEA] 1868 파핑파핑 지뢰찾기 (D4^ / BFS) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE&problemTitle=1868&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 문제 해석 지뢰 : * 지뢰가 없는 칸 : . 주변 8방에 지뢰가 있으면 숫자를 출력함 주변 8방에 지뢰가 없으면 나머지 8..
개인 공부/코딩 테스트^ 2023. 2. 26. 10:43

[SWEA] 9229 한빈이 Spot Mart (D3, 조합) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 과자를 두 봉지 사야 함 무게 제한을 벗어나면 살 수 없음 무게합 최대를 찾아라 - 각 테스트케이스 별 입력 첫 번째 줄 : N M # 과자 개수, 최대 무게 두 번째 줄 : N개의 무게 정보 코드 import java.io.*; import java.util.*; public class Solution { static int maxWeight; static int M; public..
개인 공부/코딩 테스트 2023. 2. 25. 10:08

[알고리즘] DFS

DFS 개념 DFS : 깊이 우선 탐색 (==장자 우선 탐색) BFS : 너비 우선 탐색 완전 탐색 기법 중 하나 스택(재귀)를 사용함 재귀는 부를 때마다 함수를 시스템 스택에 쌓기 때문에 결국 스택을 사용한 것과 동일한 효과를 가져옴 시작지점에서부터 끝점까지 이동하면서 모든 경우의 수를 탐색 -> 저렴한 비용을 뽑는 문제에서 사용함 앞선 BFS 정리 자료에서 보셨겠지만, DFS는 BFS와 서로 상반되는 개념입니다. DFS는 탐색 시 같은 level에 위치한 노드들을 먼저 탐색하는 BFS와 달리, 한쪽 방향으로 깊이 탐색한 후, 거슬러 올라가면서 나머지를 탐색하는 알고리즘입니다. 그래서 이를 첫번째 자식을 가장 먼저 생각하는 장자 우선 탐색이라고 생각하셔도 좋을 것 같습니다. BFS : 2 -> 7 ->..
개인 공부/알고리즘 2023. 2. 24. 15:07

[Baekjoon] 백준 15686 치킨 배달 (G5 / 조합) - Java

링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해석 - 입력 첫 번째 줄 : N M # 도시크기, 살아남을 치킨집 개수 나머지 줄 : N줄을 통해 도시의 거리 정보 전달 0 : 빈칸 1 : 집 2 : 치킨집 치킨 거리 계산 방법 : |R1 - R2| + |R1 - R2| 전체 치킨집 중 M개의 치킨집만을 유지한다고 했을 때, 모든 집의 치킨거리가 최소가 되는 값을 구하라. 코드 import java.io.*; ..
개인 공부/코딩 테스트^ 2023. 2. 23. 10:05
◀ 1 2 3 4 5 6 ▶

티스토리툴바