본문 바로가기

BOJ

[BOJ][JAVA] 9012 - 괄호 문제 출처 : https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 설명 괄호 짝 판별 문제는 대표적인 스택문제이기 때문에, 스택 사용하신다면 큰 문제 없이 풀 수 있으실 것입니다. 여기서 키 포인트 두 가지는 다음과 같습니다. 1. VSP이려면 "(" 와 ")" 의 갯수가 동일해야 합니다. 2. 갯수와 상관없이 왼쪽에서 오른쪽 방향으로 진행하는 도중에 "(" 의 갯수보다 ")" 의 갯수가 더 많이 나온다면 그 뒤.. 더보기
[BOJ][JAVA] 1120 - 문자열 문제 출처 : https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 문제 설명 조금 어렵게 느껴질 수도 있는 문제인데, 차근차근히 원리를 생각해보면 생각보다 쉬운 문제입니다. 제 아이디어는 다음과 같습니다. B와 같아질 때까지 A의 앞뒤로 아무 문자나 붙일 수 있기 때문에 A가 B의 위를 왼쪽부터 오른쪽으로 돌아다니며 서로 다른 알파벳의 차이가 최소인 위치를 찾습니다. 그 위치를 찾았다면, 그 차이만큼 B와 똑.. 더보기
[BOJ][JAVA] 2920 - 음계 문제 출처 : https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 문제 설명 비교적 간단한 문제인데, 처음에 필요 이상으로 복잡하게 생각을 해서 좀 길게 코드를 짰습니다. 처음 버전과 간단히 리팩토링한 버전을 차례로 올립니다. 그리고 이 둘보다 더 간단하게도 풀 수 있습니다. 너무 간단해서 그냥 말로만 설명드리자면, 그냥 입력값 8개를 배열에 차례로 저장한 다음에 그 배열이 1, 2, 3, 4, 5, 6, .. 더보기
[BOJ][JAVA] 3109 - 빵집 문제 출처 :https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 설명 DFS 유형의 문제입니다. 이 문제의 첫번째 포인트는 최대한 많은 파이프의 수를 구해야 하므로, "오른쪽 위 - 오른쪽 - 오른쪽 아래" 의 우선순위 순으로 탐색해야 한다는 것입니다. 그래서 x의 델타 배열(dx)도 그 순서로 구성하였습니다. 두 번째 포인트는, 만약 하나의 루트가 성공했다면 그 루트 선상에 있는 다른 방향은 더 이상 탐색 및 카운트되면 안 되므로, 재귀를 종료시켜야 한다는.. 더보기
[BOJ][JAVA] 2630 - 색종이 만들기 문제 출처 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 설명 백준의 Z, 쿼드 트리와 굉장히 유사한 유형의 이분탐색 문제입니다. 사각형 안의 수가 다 동일하다면 white 또는 blue에 대한 수를 증가시켜 주고 재귀를 끝냅니다. 만약 동일하지 않다면, 재귀적으로 4등분하여 동일한 방법으로 살펴보는 것을 반복하는 식으로 구현했습니다. 맨 끝에 Z와 쿼드트리 코드 게시물도 링크 걸어 둘 테니, 필요하시다면 .. 더보기
[BOJ][JAVA] 1987 - 알파벳 문제 출처 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 설명 문제의 길이는 짧고 간단하지만, 꽤나 어려운 DFS문제였습니다. 여기서 포인트는 A, B, C, D..의 알파벳을 0, 1, 2, 3...순서대로 숫자로 반환하는 것인데, 이를 char형에 'A'를 각각 빼 주는 것으로 구현했습니다(아스키 코드 값 사용) 또한, cnt를 케이스 별로 따로 관리해야 하기 때문에 static변수로 두는 것이 아니라 매개변수로 태워 보냈.. 더보기
[BOJ][JAVA] 1992 - 쿼드 트리 문제 출처 : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 설명 전형적인 이분탐색 유형의 문제로, 백준의 Z문제와 상당히 유사한 문제입니다. 코드블럭 밑에 Z 풀이 링크 걸어두니, 필요하시면 참고해 주세요! :) 맨 처음에 구역을 하나의 숫자로 압축할 수 있다면 바로 리턴해서 끝내고, 그렇지 못하다면,전체를 1, 2, 3, 4분면으로 각각 나눠 들어가서 다시 작업을 반복하는 식으로 코드를 짰습니다. 이때, 출력될 괄호의 위.. 더보기
[BOJ][JAVA] 17135 - 캐슬 디펜스 문제 출처 : https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 설명 꽤나 복잡한 시뮬레이션 문제였지만, 로직 자체는 크게 어렵지 않아서 조건에 따라 차근차근 코드를 짜 나가다 보면 해결할 수 있는 문제였습니다. 여기서 주의할 점은 각 케이스에 대해서 시뮬레이션을 돌릴 때, 원본이 변하면 안 되기에 복사본을 만든 후 그 복사본에서 시뮬레이션을 해야 한다는 것입니다. 한꺼번에 구현하려 하지 않고, 적절한 단위로 끊어서 함수로 구성해 나갔기 때문에 조금이.. 더보기

티스토리툴바