전체 글
BOJ 12100 2048 (Easy) [Java]
BOJ 12100 2048(Easy) 1. 문제 링크 https://www.acmicpc.net/problem/12100 2. 문제 해설 5번을 이동시키는데 각 이동마다 4개 방향으로 가지를 뻗쳐나갈 수 있는 백트래킹 문제이다. 문제를 읽어보면 구현해야할 기능은 크게 2가지다. 첫번째는 블록을 이동시키고 합치는 부분이고, 두번째는 백트래킹 과정을 통해 5번을 이동시키면서 모든 상황을 살펴 보는 부분이다. 두 기능을 어떻게 구현할지 생각해보자. 1. 블록을 이동시키고 합치는 기능 - move 메서드 백트래킹 과정에서 매 이동마다 4개의 방향을 선택할 수 있다. 즉, 매 이동마다 4개의 가지를 뻗는다. 그러므로 지금까지의 상황이 담긴 map 배열과, 이동시킬 방향을 인자로 받아야한다. 방향은 동, 서, 남,..
BOJ 1759 암호 만들기 [Java]
BOJ 1759 암호 만들기 1. 문제 링크 https://www.acmicpc.net/problem/1759 2. 문제 해설 백트래킹 문제이다. 다만 조건이 조금 추가되었다. 어떤 조건이 있는지 살펴보자. 1. 암호는 L개의 알파벳 소문자로 구성된다. 2. 최소 한 개의 모음과 두 개의 자음으로 구성된다. 3. 알파벳이 사전 순으로 배열된다. 일단 solve 메서드가 받아야할 인자는 현재 암호의 길이(length), 살펴보고 있는 인덱스(idx), 모음의 수(vowel), 자음의 수(consonant)이다. solve 메서드가 1, 2번 조건을 만족할 때 탈출하여 문제의 조건을 만족시켜준다. 3번째 조건인 암호의 경우의 수가 사전 순으로 배열되게 하기 위해서 입력 받은 arr 배열을 미리 사전 순으로 ..
BOJ 15649 N과 M (1) [Java]
BOJ 15649 N과 M (1) 1. 문제 링크 https://www.acmicpc.net/problem/15649 2. 문제 해설 백트래킹을 할 때는 문제에서 주어진 조건을 잘 살펴야한다. 이 문제에서는 중복 없이 숫자 선택, 사전 순으로 수열 출력 이 2가지 조건만 만족하면 된다. 중복 체크를 하기 위해 vis 배열을 만들어주고, m개의 선택된 숫자를 담을 arr 배열을 만들어준다. 이제 백트래킹 과정을 행할 solve 메서드에 대해 알아보자. 매개 변수로 cnt를 받는데 cnt가 의미하는 바는 선택된 숫자의 갯수이다. 탈출 조건은 cnt가 의미하는 바를 생각하면 자연스레 도출된다. cnt == m 이 되면 solve 메서드를 탈출하고 arr 배열에 저장된 숫자들을 StringBuilder에 담는다..
BOJ 5014 스타트링크 [Java]
BOJ 5014 스타트링크 1. 문제 링크 https://www.acmicpc.net/problem/5014 2. 문제 해설 bfs를 이용하여 최단 거리를 묻는 문제는 유명한 유형이다. 이 문제에서 버튼의 최솟값은 결국 최단 거리의 다른 표현이다. 한가지 내가 처음에 실수하였던 부분은 이동할 수 있는 칸 수를 나타내는 배열을 {u, -d}로 하지 않고 {u, d}로 하였던 것이다. 이 점 빼고는 무난한 bfs 구현이다. 3. 코드 보기 import java.io.*; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { st..
2021 카카오 채용연계형 인턴십 Lv3 표 편집 [Java]
2021 카카오 채용연계형 인턴십 Lv3 표 편집 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/81303 2. 문제 해설 배열의 경우 삽입, 삭제의 시간복잡도가 O(n), 연결리스트의 경우 O(1)이다. 삽입, 삭제가 빈번하게 이뤄지는 경우 연결리스트를 이용하는 것이 효율적이다. 이 문제의 경우 행의 최대 갯수도 100만이고 명령의 갯수도 최대 20만이기에 이므로 연결리스트를 이용하여 푸는 것이 좋다고 생각했다. 행들의 정보를 담기 위해 Node 클래스를 만들었다. Node 클래스에는 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next, 삭제 여부를 담는 removed가 있다. 각 행들은 Node 클래스를 이용하여 표현했고, 행들을..