본문 바로가기

PS

(77)
[BOJ] 1022번: 소용돌이 예쁘게 출력하기 https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 알고리즘 분류 구현 문제 파악 0,0 지점으로부터 우, 상, 좌, 하로 돌아가면서 숫자가 증가하는 소용돌이에서 (r1, c1) ~ (r2, c2)의 범위까지의 숫자를 출력한다. 처음에는 BFS로 해결 해볼까 라는 생각에 이리저리 시도해봤지만 r2-r1+1 , c2-c1+1 만큼의 크기를 만들어서 계산을 해볼까 하다가 너무 복잡할 것 같아서 생각을 바꿨다. (1,1), (2,2), (3,3) 순으로 이동해야 하는 거리가 늘어나며 정방향, 역방향을 설정해서 소용돌이처럼 x, y 좌표와 value를 설정해 나간다. 만약 ..
[Programmers] LV2- 프렌즈4블록 https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 문제 파악 문제의 의도는 아래의 사진과 같다. 애니팡 게임과 비슷하게 1. 2X2칸의 이모티콘이 모두 같으면 해당 칸을 지운다. 2. 지운 칸의 개수를 센다. 3. 지워진 이모티콘의 칸을 위에 있던 이모티콘이 내려와 빈자리를 채운다. 아마 비워진 칸으로 이모티콘을 이동시키는 부분을 깔끔하게 코딩 하고 싶어서 시간을 많이 쓴 거 같다 가독성..
[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; ..