mondegreen

[Part2-Chapter05-Clip04]- 백준 1759 암호 만들기사용했을 법한 문자 종류 배열을 오름차순으로 정렬하고 서로 다른 문자를 뽑아야 하기 때문에 방문배열을 활용하고, 문자를 선택할 때 이전에 선택된 문자가 현재 문자보다 알파벳 순 기준으로 앞서도록 처리하면 된다. 또한 자음과 모음 갯수 제한이 있기 때문에 해시 셋으로 모음을 담고 셋을 통해 해당 여부에 따라 갯수를 카운트해주면 된다. package BaekJoon.recursion;import java.io.*;import java.util.Arrays;import java.util.HashMap;import java.util.HashSet;import java.util.StringTokenizer;public class BJ1759 ..

[Part2-Chapter05-Clip01]- 백준 1182 부분수열의 합재귀를 명확히 이해하고 있지 않다고 생각하게 된 문제였다. 일단 수열과 부분 수열의 정의에 대해서 알아야 하는데 수열은 일정한 규칙에 따라 순서대로 나열한 수의 집합이고 부분수열은 원 수열의 항의 일부분만을 딴 수열을 의미한다. 단, 이 때 수열은 원래의 순서를 유지해야 한다. 예를 들어, {𝑎𝑛}=1,2,3,⋯ 라는 수열이 있다고 가정하자. 그럼, {𝑎𝑛𝑘}=1,3,6,8,⋯은 부분수열이지만, {𝑎𝑛𝑘}=1,3,2,6,7,⋯ 은 부분수열이 아니다.  기본적으로 문제의 지시사항이 불친절하다고 생각한다. 주어지는 n개의 수의 나열이 수열의 형태로 주어지는지 아닌지를 말하지 않았는데 이게 중요한 이유는 아래 정렬 코드가 ..

[Part2-Chapter04-Clip04] - 백준 14267 회사 문화 1상사가 칭찬을 받으면 직속 부하를 연쇄적으로 칭찬하기 때문에 방향이 없는 그래프인 트리 구조를 활용하면 된다. 직속으로 타고 내려가다가 가장 말단 사원까지 점수를 더해줘야 하기 때문에 DFS 방식으로 점수를 더해주는 방식으로 구현한다. 먼저 입력값을 받아주는데 각 직원의 직속 상사를 입력할 때, 입력받는 순서인 인덱스가 '부하'이고 입력 받는 값이 '상사'이다. ArrayList를 원소로 가지는 배열을 생성해서 배열의 인덱스는 상사, 그 원소인 리스트는 연결된 부하로 값을 입력하면 트리 탐색이 가능한 형태가 된다. 이렇게 입력 받고 나면 칭찬을 순서대로 받아주면서 직속 부하들에게까지 점수를 입력하는데 이 때, 칭찬을 받을 때마다..

[Part2-Chapter04-Clip02]- 백준 11725 트리의 부모 찾기트리도 그래프의 일종이다. 단, 순환이 없는 그래프이다. 그래프 문제를 풀 때와 마찬가지로 인접 리스트를 선언하고 간선의 양 끝 정점을 리스트에 담아줬다. 부모를 찾는 함수를 구현하는 데 약간 어려움을 겪었다. 정점들을 연결된 순서대로 타고 가는데 루트 노드인 1부터 시작해서 따라가다 보면 직전의 정점이 즉, 나를 호출한 정점이 부모가 되는 로직이다. 이미 방문한 경우는 제외하고 자식 노드를 계속 찾아나가면서 자식 노드를 찾을 때마다 정답 배열에 부모인 직전 정점을 넣어주면 문제를 해결할 수 있다.package BaekJoon.tree;import java.util.ArrayList;import java.util.Scanner..

1부터 n까지의 수를 오름차순 및 내림차순으로 출력하도록 재귀를 구현하자. - 백준 2747 피보나치 수 위 문제는 중복 연산이 많기 때문에 메모이제이션을 활용해야만 시간 초과가 발생하지 않는다. package BaekJoon.recursion; import java.util.Scanner; public class BJ2747 { public static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); arr = new int[n + 2]; arr[0] = 0; arr[1] = 1; pibo(2, n); System.out.println(arr[n]); }..

커서가 이동하기 위해서는 스택을 두개 사용하는 것이 필요할 것 같았다. 커서를 기준으로 왼쪽과 오른쪽 스택을 별도로 구현하고 커서를 기준으로 양쪽으로 이동시켜주면 된다. 커서 이동과 삭제 시마다 스택이 비어있는지 확인하는 것은 필수이고 커서가 중간에 위치한채로 입력이 끝날 수 있기 때문에 오른쪽 스택에 존재하는 값을 왼쪽으로 모두 옮겨준 후에 stringbuilder로 문자열화해주고 역순으로 처리해주면 된다. package BaekJoon.stack; import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class BJ5397 { public static void main(String[] args) { S..

[Part2-Chapter02-Clip04] -백준 2504 괄호의 값 짝이 되는 괄호를 if 문으로 복잡하게 쓰지 않기 위해 map에 담아서 짝을 맞추도록 했고 소괄호와 대괄호를 2와 3으로 매칭시키는 것도 map을 활용했다. 값을 넣을 때마다 최근 넣은 값을 저장한다. 괄호가 열릴 때마다 곱을 해주고 닫힐 때마다 다시 해당하는 수로 나누어서 결과값을 갱신시키는 방식으로 풀이했다. 가장 먼저 예외처리할 부분은 괄호가 짝이 맞도록 닫히지 않는다면 0을 반환해야 한다. 따라서 일단 입력값의 길이가 홀수라면 바로 0을 반환하고, stack을 활용해 괄호가 잘 닫히고 있는지도 확인하여 스택에 남은 값이 있다면 0을 반환하도록 구현했다. 여는괄호인 경우 스택에 담아주고 해당하는 숫자를 곱해준다. 닫는 괄호인 경..

[Part2-Chapter02-Clip01] -백준 10828 스택 자바 공식문서에 따르면 스택 같은 경우 아주 예전 자료구조인 Vector를 상속해 만든 Stack 보다 Deque를 이용해 stack을 구현하는 것을 권장하고 있다. deque은 양방향에서 삽입 삭제가 가능하기 때문에 스택과 큐로 모두 구현 가능하기 때문이다. 그럼 이 Deque을 활용해서 stack 문제를 풀어보자. package BaekJoon.stack; import java.util.*; import java.io.*; public class BJ10828 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

[Part2-Chapter01-Clip03] - 백준 2230 수 고르기 left가 되는 인덱스를 기준으로 반복문을 돌면서 그 안에서 while 문으로 right를 맨 마지막 인덱스로부터 줄여보려고 했다. 하지만 left가 바뀔 때마다 right를 새로이 맨 마지막 인덱스로 갱신했기 때문에 결국 n^2이 되어 시간 초과가 발생했다. 음 그러면 right는 이전 left가 옮겨 놓은 그 위치 그대로 탐색해보자고 했지만 값을 못 찾는 문제가 발생했다. 이번 left와 right를 각각 확인해봐야 하는데 이미 right를 당겨와 버려서 그 뒤의 값들와 left를 비교하지 못하는 문제였다. 다시 생각해보니 방향이 틀렸다는 것을 깨달았다. 마주보는 방향으로 이동하는 것이 아니라 한 방향에서 시작하면서 m보다 작으..

[Part1-Chapter08-Clip01] - 백준 2003 수들의 합2 투 포인터란 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘을 말한다. 포인터를 사용하는 방식은 다음과 같이 다양할 수 있다. 1) 같은 배열에서 동일한 방향으로 이동하는 투포인터 (이 경우 2003 문제이다.) 2) 같은 배열에서 마주보는 방향으로 이동하는 투포인터 3) 서로 다른 배열에서 이동하는 투포인터. 이때 두 포인터 중 경우에 따라 하나 또는 모두가 끝에 도달할 때까지 반복한다. 아래는 부분합 배열을 구현하여 풀이한 것이다. l과 r을 시작 원소와 끝 원소의 인덱스로 지정하고 해당 구간의 부분합이 m과 비교하여 큰지 작은지 같은지에 따라 포인터를 움직임으로써 경..