본문 바로가기

알고리즘

💜 백준 10250 ACM 호텔 1. 문제 설명 [ACM호텔 문제링크](https://www.acmicpc.net/problem/10250) 2. 푸는 원리 그냥 반복문 돌리면 된다. 자신감을 되찾기 위해서 풀었다. 3. 코드 분석 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /* * 10250 ACM 호텔 * */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRe.. 더보기
💜 백준 11729번 하노이 탑 이동순서 1. 문제 설명 11729번 하노이 탑 이동 순서 링크 이동 순서를 Log로 찍어야 한다. 2. 푸는 원리 재귀를 이용한다. (0) 재귀함수에는 출발지, 경유지, 도착지, 도착지까지 옮겨야 하는 원판의 번호가 있다. (원판의 번호가 큰 것이 크기가 큰 것이다. 따라서 제일 작은 원판은 번호가 1이다.) (1) 실제로 원판을 옮기는 것이 아니라, 그 이동 순서에 대한 로그만 찍는다. [기저조건] (1)옮겨야하는 원판의 번호가 0이 되면 그냥 return 한다. [계산] (1) 현재 옮겨야할 원판보다 작은 모든 원판을 경유지로 옮기는 Log를 찍는다. (재귀 이용) (2) start와 end를 StringBuilder에 담아서 현재 원판의 이동을 Log로 찍는다. (StringBuilder에 담는 행위 자체.. 더보기
💜 백준 1874번 스택 수열 1. 문제 설명 1874 스택수열 문제 설명 1~N까지 오름차순으로 스택에 하나씩 집어넣는다. 스택에 하나씩 들어올 때, 적절히 POP하여, 문제에서 원하는 수열을 만들 수 있는지 구하라 만들 수 있다면 PUSH = + , POP = - 로 그간 해왔던 명령어를 출력하고, 만들 수 없다면 NO를 출력하라 2. 문제 푸는 방법 A. 첫 번째 방법 (STACK 자료 구조 이용) (1) 답이 되는 수열(이하 ans)과 스택에 입력하는 순서인 오름차순 수열(이하 arr)을 배열에 저장했다. (2) 둘 다 지시자를 가지고 있다. ans의 지시자를 ansIndicator, arr의 지시자를 arrIndicator라고 할 때, ​ a. arrIndicator가 가르키고 있는 것이 ansIndicator보다 작거나 같.. 더보기
💜 백준 7490. 0 만들기 JAVA 1. 문제 설명 0 만들기 문제 링크 3~9까지 수가 주어지는데, 그 사이 사이에 + 혹은 - 혹은 두 수 붙이기를 사용하여, 총 합을 0으로 만들어라. 2. 푸는 원리 이런 문제는 일일히 char로 분할하여 가지고 있는 것보다, String으로 한번에 가지고 있다가 StringTokenizer로 푸는 것이 좋다는 것을 알았다. (1) DFS를 돌린다. (-> String에 다음 depth의 값을 추가하는 식) (2) 한번은 두 수 사이에 +를 넣고, 한번은 두 수 사이에 -를 넣고 한번은 두 수 사이에 공백을 넣고 경우를 진행한다. (3) 마지막 수까지 String 문자열에 쌓이면, cal이란 이름의 함수에 넣어서 계산한다. (4) cal의 역할은 다음과 같다. ​ a. 공백인 부분을 합쳐서 하나의 수.. 더보기
💜 백준 3109 뱀 JAVA 1. 문제 분석 [3190 뱀 문제 링크](https://www.acmicpc.net/problem/3190) 지렁이 게임의 원리대로 움직이는 문제 빈 공간은 0, 사과는 1, 뱀이 존재하는 자리는 2로 표시한다. 뱀이 2차원 배열 내를 움직임 -> 움직이니까, 지나간 장소는 2가 아니라 다시 0으로 와야함. 사과를 먹으면 뱀의 몸집이 1 커짐 뱀이 벽에 부딪히면 게임오버 뱀이 자신의 몸에 부딪히면 게임오버 뱀은 방향 전환이 가능 -> 몇 초에 반시계, 시계 방향 중 어디로 움직일지는 주어진다. 게임이 몇 초간 걸리는지 구하기 (뱀은 한 번 움직일 떄, 2차원 배열에서 한 칸 움직이고, 이떄 시간이 1 든다.) 2. 푸는 원리 저기 나오는 1~5를 함수로 작성해서, 함수가 돌아가도록 하면 된다. 처음에는.. 더보기
💜 백준 2085 사탕게임 JAVA 1. 문제 설명 (사탕게임 링크)[https://www.acmicpc.net/problem/3085] 캔디 크러쉬 처럼, 서로 다른 종류의 캔디가 보이면 자리를 바꾼다. 그 후, 한 행, 혹은 한 열에서 같은 종류의 캔디끼리 나열되어 있으면 그건 터져서 사라짐. 주어진 2차원 배열에서 한 번 자리를 바꿨을 때 터질 수 있는 최대한의 캔디의 개수를 구하시오 2. 푸는 원리 서로 다른 종류의 캔디를 만나면 자리를 바꾼다. 모든 행을 검사하며, 일련의 연속성을 가진 캔디의 개수를 센다. -> 최고 길이 갱신 모든 열을 검사하며, 일련의 연속성을 가진 캔디의 개수를 센다. -> 최고 길이 갱신 최고 길이를 출력한다. 3. 코드 분석 import java.io.BufferedReader; import java.i.. 더보기
💜 백준 1038 감소하는 수 1. 문제 분석 감소하는 수 문제 링크 321, 952 등 제일 큰 자릿수부터 작은 자릿수로 올수록, 자릿수의 값이 작아지는 경우, 감소하는 수라고 한다. 반면 322, 235 등은 위의 정의에서 벗어나기에 감소하는 수가 아니다. 0을 0번째 감소하는 수, 1을 1번째 감소하는 수, 9를 9번째 감소하는 수 라고 했을 때, 주어진 N에 관하여, N번째 감소하는 수의 값을 구하여라 2. 푸는 원리 조합이다. 하지만 원래의 조합처럼 오름차순으로는 풀 수 없다. (1) 첫번째 자릿수를 고정하고, 그 자릿수를 limit으로 정한다. (2) 조합을 돌며, 두 번째 자릿수는 limit보다 작은 수 중에서 하나를 택한다. (3) 재귀를 돈다. (4) 세 번째 자릿수를 고를 때는 두 번째 자릿수가 넘어설 수 없는 li.. 더보기
💔 백준 14500 테트로미노 1. 문제 분석 백준 테트로미노 링크 2차원 배열에서 면 대 면으로 붙는 원소끼리 총 4개를 이었을 때, 원소간의 합이 최대값이 되는 경우를 구하여라. 2. 푸는 원리 테트로미노로 나올 수 있는 값들이 미리 나와 있다. 왼쪽 상단부터 1번이라고 하자. 그리고 왼쪽 -> 오른쪽으로 번호를 붙이겠다. 1번부터 4번에 해당하는 블럭은 DFS로 값을 구할 수 있다. 예를 들어보면, 다음과 같다. 하지만 5번의 경우 단순 dfs로 안 풀린다 왜냐하면 두번째 depth 부터 갈 수 있는 길이 2 갈래로 갈라지기 때문이다. 따라서 DFS로는 풀지 못하고, 중앙에서 시작하여 4방 탐색 중 3방을 고르는 조합으로 문제를 풀었다. 3. 코드 분석 import java.io.BufferedReader; import java.. 더보기

티스토리툴바