mondegreen

[Part1-Chapter04-Clip05] - 백준 3085 사탕게임 시간이 많이 걸린 문제였다. 처음에 시간 복잡도를 최대한 줄여보겠다고 한 행과 열에 등장하는 색을 체크하고 수가 적은 행열만 반복하려다가 행과 열을 구분해서 작성하게 되고 오히려 코드가 길어져서 포기했다. 다시 고민해보니 차라리 사방탐색을 하며 경계 체크하고 다르면 바꾸고 해당 요소가 속한 행렬에서 최대 연속 수를 구하는 방식으로 구현했다. 오히려 코드가 명료해졌고 인접한 사탕이 다른 경우에만 바꾸고 시간 복잡도를 고려해 그 사탕이 속한 행렬만 체크하도록 구현했기 때문에 추가로 원래 배열인 경우에도 최대 연속의 수를 구하도록 했다. 이 글을 작성하다 보니 이렇게 풀면 안되었나.. 바꾸고 모든 행렬을 보아야했을까? 라는 생각이 든다. ..

[Part1-Chapter04-Clip02] -백준 10448 유레카 이론 아무리 생각해도 재귀가 아니라면 반복문을 3중으로 돌리는 수밖에 없다고 생각해서 아래와 같이 3중 반복문을 구현하여 돌렸다. 불필요한 순회를 줄이기 위해 찾으면 바로 반복문을 빠져나오도록 처리했다. package BaekJoon.bruteforce; import java.util.Arrays; import java.util.Scanner; public class BJ10448 { public static void main(String[] args) { solve(); } private static void solve() { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); S..

[Part1-Chapter03-Clip04] -백준 10989 수 정렬하기 3 위 문제는 시간 제한과 메모리 제한이 비교적 있는 편이라 단순히 삽입 정렬을 할 수는 없었다. 최악의 경우 모든 숫자를 배열에넣고 단순히 sort 매서드를 쓰기에는 메모리 제한에 걸리기 때문에 그렇게 풀 수 는 문제는 아니었고. 정수배열의 경우 인덱스 하나당 4바이트 인데 모든 수를 배열에 넣는다면 4천만 바이트로 메모리 제한에 걸리기 때문에 불가. 주어지는 수의 갯수는 천개 이지만 수의 종류가 최대 10000이기 때문에 카운팅 배열을 활용하고자 했다. 입력을 받으며 해당하는 인덱스에 갯수를 늘려주고 입력되는 수의 최대값을 구해 놓으면 반복문을 돌 때 그 수를 줄일 수 있을 거라고 생각했다. 카운팅 배열에 오름차순으로 값을 넣..

완전 검색이란 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법으로서 상대적으로 빠른 시간 내에 알고리즘 설계가 가능하다. 경우의 수가 적을 때 유용하며, 모든 경우의 수를 생성한 후 테스트하기 때문에 수행속도는 느리지만 해답을 찾지 못할 가능성이 현저히 낮다. ** 완전 검색을 이용한 Baby-gin 1) 6개의 숫자로 만들 수 있는 모든 경우의 수를 나열한다 => 중복을 포함한 순열 2) 앞 3개의 숫자, 뒤 3개의 숫자를 구분하여 run(연속된 수) 또는 triplet(동일한 수) 여부를 판단한다. 완전 검색은 전형적으로 순열, 조합, 부분집합과 같은 조합적 문제와 연관되어 있다. ** 검색 기법 https://rileylee.tistory.com/5 검색 검색이란 저장된 ..