본문 바로가기

코딩테스트32

[백준/Java] 1325: 효율적인 해킹 https://www.acmicpc.net/problem/1325 문제 설명컴퓨터 해킹할 거임컴퓨터A가 컴퓨터B를 신뢰 --> B를 해킹하면 A도 해킹할 수 있음한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하면 됨 입력첫째 줄에 N(N개의 컴퓨터M개의 신뢰 관계둘째 줄부터 M개 줄에 신뢰 관계 A, B가 주어짐컴퓨터 번호는 1~N5 43 13 24 35 3 출력한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 오름차순으로 출력 풀이간선을 B → A로 저장하면 어떤 컴퓨터를 시작점으로 할 때 감염 범위를 쉽게 계산할 수 있음각 컴퓨터를 시작점으로 BFS를 실행하여 감염 가능한 컴퓨터의 수를 셈BFS로 i번 컴퓨터와 연결된 모든 컴퓨터를 탐색하는 것 그래프에 컴퓨터 간 신뢰 관.. 2025. 6. 4.
[백준/Java] 12542: Building a House (Large) https://www.acmicpc.net/problem/12542 문제 설명새로 구매한 땅에 가능한 가장 큰 직사각형 모양으로 식물을 심을 것임땅에는 장애물이 존재하고, 제거할 수 있는 장애물과 제거할 수 없는 장애물로 나뉨 제거할 수 있는 장애물grass (G)shrubs (S)제거할 수 없는 장애물rock (R)water (W)trees (T) 땅의 크기와 장애물 정보가 주어졌을 때, 식물을 심을 수 있는 가장 큰 직사각형의 크기를 구하면 됨 입력첫 번째 줄에 N개의 테스트 케이스 수가 주어짐각 테스트 케이스에는 L(length)과 W(width)가 주어지고, 이후 L개의 문자로 구성된 W개의 라인이 나옴각 문자는 땅에 어떤 장애물이 존재하는지 보여줌5 8GGTGGTGGGGGSSGTGGGGTGWG.. 2025. 5. 28.
[백준/Java] 1904: 01타일 https://www.acmicpc.net/problem/1904 🚀 참고https://st-lab.tistory.com/125https://steady-coding.tistory.com/146 풀이나올 수 있는 경우의 수를 확인해보면 아래와 같음N만들 수 있는 타일가짓수111200, 1123001, 100, 111340000, 0011, 1001, 1100, 11115500001, 11001, 00111, 11111, 10011, 00100, 11100, 100008......... N 값이 커질수록 가짓수는 피보나치 수열 형태로 커짐 📍 피보나치 수열 형태로 커지는 이유N자리 2진 수열에서 나올 수 있는 경우의 수를 f(N)이라고 할 때,맨 마지막 타일이 1인 경우그 앞에는 N-1 길이의 .. 2025. 4. 30.
[백준/Java] 9184: 신나는 함수 실행 https://www.acmicpc.net/problem/9184  동적계획법의 특징은 대체로 재귀 + Memoization(메모이제이션) 📌 메모이제이션 Memoization동일한 계산을 반복해야 할 때 사용계산을 통해 얻은 값을 메모리에 저장(기록)하고,이 후 같은 입력이 반복될 경우 다시 계산하는 것이 아닌 저장된 값을 사용함 🚀 참고https://st-lab.tistory.com/190  풀이a, b, c 세 개의 값이 들어오므로 계산값을 저장할 3차원 int 배열 생성 (memo[][][])memo[a][b][c]에 접근했을 때 저장되어 있는 값이 있는 경우 해당 값 반환저장된 값이 없는 경우 새로 계산 코드import java.io.BufferedReader;import java.io.IO.. 2025. 3. 9.
[백준/Java] 2580: 스도쿠 https://www.acmicpc.net/problem/2580  백트래킹은 해도해도 어렵다아래 잘 정리돼있는 블로그 글 보면서도 한참 헷갈렸음 🚀 참고https://st-lab.tistory.com/119  풀이1 (참고한 블로그와 동일)더보기입력받은 값을 2차원 int 배열에 저장sudoku() 재귀함수 작성for문을 이용하여 스도쿠 차례대로 탐색빈 칸을 만날 때마다 숫자(1~9) 대입 시도해당 빈 칸이 위치하는 행, 열, 3X3 박스를 확인 (calculate 함수 호출)calculate() 작성빈 칸의 위치와 확인하려는 숫자값 매개변수로 받음 (row, col, value)행, 열, 박스 각각 확인하여 이중 중복되는 숫자가 있으면 바로 false 리턴박스를 확인할 땐 해당 빈칸이 포함되는 박스.. 2025. 3. 5.
[백준 2428/자바] 표절 https://www.acmicpc.net/problem/2428 처음엔 이중 for문으로 풀었는데 아니나 다를까 시간초과 ==> 시간복잡도가 O(N^2)이기 때문분류가 이분탐색으로 돼있길래 그렇게 풀어보려 했는데 도저히 풀이가 생각이 안 나서 구글링함.. 풀이솔루션 파일 크기를 받아 배열에 저장해당 배열 오름차순으로 정렬size(Fi) ≤ size(Fj) 만족이분탐색 함수 정의 - binarySearch(int[] arr, int i)size(Fi) ≥ 0.9 × size(Fj)를 만족하는 가장 큰 j값을 리턴배열(arr)과 i값이 주어졌을 때 i+1번째 원소부터 배열의 마지막 원소까지 검사이분탐색 위해 start, mid, last 구함start = i + 1last = arr.length - 1mi.. 2024. 12. 7.
[백준 9935/자바] 문자열 폭발 https://www.acmicpc.net/problem/9935  문자열의 최대길이가 100만이기 때문에 문자열 메소드 replaceAll을 사용하면 메모리초과가 발생한다고 한다... ✨ 참고https://loosie.tistory.com/317  풀이스택 사용 스택에 입력받은 문자열을 한 글자씩 집어넣음스택의 크기가 폭발 문자열의 길이와 같거나 길이보다 클 경우 폭발 문자열이 포함 돼있는지 확인스택의 최상단에서 폭발 문자열 길이까지만 get 함수를 이용해 앞에서부터 차례대로 확인한다만약 폭발 문자열이 포함 돼있으면 그 길이만큼 pop 수행 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader.. 2024. 7. 3.
[백준 2606/자바] 바이러스 https://www.acmicpc.net/problem/2606  BFS에 익숙해져보려고 계속 하는데 익숙해지지가 않음더 공부해야 할 듯 ✨ 참고인접 리스트 - https://ko.wikipedia.org/wiki/%EC%9D%B8%EC%A0%91_%EB%A6%AC%EC%8A%A4%ED%8A%B8풀이BFS 및 인접 리스트 사용  📌 인접 리스트그래프 이론에서 그래프를 표현하기 위한 방법 중 하나그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법인접 행렬에 비하여 변이 희소한 그래프에 효율적이다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import.. 2024. 7. 3.
[백준 1926/자바] 그림 https://www.acmicpc.net/problem/1926    BFS 공부✨ 참고https://velog.io/@minjoott_dev/%EB%B0%B1%EC%A4%80-1926%EB%B2%88-%EA%B7%B8%EB%A6%BC-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-java  풀이BFS를 이용하여 한 점에서 시작되는 그림의 넓이 파악그림의 경계선 마주할 때까지 함수는 끝나지 않음그림 정보 저장할 2차원 boolean 배열방문 여부를 체크할 2차원 boolean 배열BFS 실행 시 사용할 queue이중 for문을 이용하여 x, y값을 확인한 뒤,해당 좌표가 도화지에서 색칠된 부분이고 아직 방문하지 않은 위치인 경우 BFS 실행 BFS 함수좌표에 방문 표시를 한 뒤 qu.. 2024. 6. 27.

티스토리툴바