본문 바로가기

전체 글

 (93)
[BOJ]2638번 : 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 깊이 우선 탐색 문제 파악 1. 문제의 핵심 부분은 치즈가 외부 공기와 닿는 면적이 2 이상이면 산화가 되어 사라진다. 2. 치즈가 모두 다 산화 되는데까지 걸리는 시간은 얼마인가 더보기 import java.io.*; import java.util.*; public class Main { static int N,M,..
[BOJ]9328번 : 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 비트 마스킹 문제 파악 상근이가 빌딩에 침입해 문서를 훔치려 한다. 이때 빌딩은 '.' , '*', '$', 알파벳 대, 소문자로 이루어져 있다. 대문자(문)에 해당되는 소문자(열쇠)를 상근이가 가지고 있을 경우 문을 따고 이동 가능하다. 진입 가능한 모든 경로를 통해 훔칠 수 있는 문서의 최대 개수를 구한다. 이 문제를 처음 통과했을 때는 Hash..
[BOJ]14719번 : 빗물 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 풀이 분류가 구현, 시뮬레이션으로 되어 있어서 탐색 관련인가.. 하는 생각이 들었는데 다른 방법으로도 풀린다. 1. 가장 좌측과 우측은 물이 고이지 못한다. (물이 고일 수 있는 범위는 1
[Programmers] LV2 - 메뉴 리뉴얼 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제 파악 1. 손님이 주문한 단품 메뉴 조합을 분해하여 각 손님에 대한 단품 메뉴의 조합을 만든다. 예를 들면 1번 손님은 A,B,C,F,G를 시켰는데 이 정보를 가지고 만들 수 있는 조합은 (A, B), (A, C), (A, F), (A, G), (B, C)... 등등으로 나눌 수 있다. 2. 조합의 경우 순서와 상관이 없어야 하므로 문자를 우선순위 큐로 분해..
[BOJ]2636번 : 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 파악 치즈의 모양이 0과 1로 주어지고 0은 공기층, 1은 치즈로 공기층과 맞닿아 있는 치즈는 1시간마다 녹아서 사라진다. (단, 치즈 내부의 있는 공기층은 해당 되지 않음) 그렇다면 치즈가 모두 녹아지는 시간과 다 녹기 직전의 치즈 칸은 몇 칸인가? 문제 풀이 1. (0,0)으로 부터 너비 우선 탐색으로 외부 공기층을 모두 Ou..
[BOJ]14889번: 스타트와 링크 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. 주어진 N/2의 인원으로 A와 B팀으로 인원을 나눈다. (조합) // MakeTeam 메서드 2. 각 팀에 속한 인원끼리의 시너지를 더하는 과정을 반복하여 최소 값을 찾아낸다. // Calculate 메서드 더보기 import java.util.*; public class Main { static int N,answer = Integer.MAX_VALUE; ..
[BOJ]14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 브루트 포스 알고리즘 너비 우선 탐색 내가 정리한 문제의 프로세스는 아래와 같다. 1. 세균의 위치를 찾는다. 2. 빈칸에 벽을 설치한다. 3. 벽을 설치 후 세균을 확산시킨다. 4. 안전지대를 Count 한다. 1. 초기 세팅 때 Virus라는 ArrayList에 넣어준다. 2. WallSet 메서드를 DFS 형식으로 빈칸에 벽을 설치하며 벽의 위치를 Stack에 쌓아..
[BOJ]16234번: 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 설명 내가 파악한 문제의 요지는 다음과 같다 1. 각 칸이 하나의 국가이고 인접한 국가끼리의 인구수 차이가 L과 R 범위 내라면 국경을 열어 인구 이동을 시작한다. 2. 인구 이동 후 각 칸의 인구수는 (연합의 인구수) / (같은 연합의 수)이다. (여기서 같은 연합의 수 라고 표현한 것은 다수의 연합이 발..

티스토리툴바