본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘 PS] 백준 15650번 N과 M (2) 자바 문제풀이 문제 해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 지난 N과 M (1) 풀이와 마찬가지로 백트래킹 문제의 대표적인 문제라고 할 수 있다. 이전 시간까지 우리는 브루트 포스 알고리즘 문제들을 풀었는데, 브루트 포스 알고리즘은 가능한 모든 경우를 대입해 정답을 찾는 방.. 2021. 2. 18.

[알고리즘 PS] 백준 15649번 N과 M (1) 자바 문제풀이 문제 해당 포스팅은 백준의 N과 M (1) 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 백트래킹 문제의 대표적인 문제라고 할 수 있다. 이전 시간까지 우리는 브루트 포스 알고리즘 문제들을 풀었는데, 브루트 포스 알고리즘은 가능한 모든 경우를 대입해 정답을 찾는 방식이다. 하지만 이번 문제에서 브루트 포스 알고리즘이 아닌 백 트래킹 알고리즘이 더욱 잘 어울려 보인다. Back-Tracking 알고리즘 백트래킹은 노드의 유망성을 판단한다. 여기서 노드의 유망성이라고 함은 쉽게 가지치기라고도 불리며 흔한 예로 dfs에서 방문 했는지를 확인하는 .. 2021. 2. 18.

[알고리즘 PS] 백준 1018번 체스판 다시 칠하기 자바 문제풀이 문제 해당 포스팅은 백준의 체스판 다시 칠하기 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 Brute Force 알고리즘을 이용해서 해결할 수 있는 문제이다. 체스판은 2가지의 종류가 존재한다. B가 먼저 오는 경우 W가 먼저 오는 경우 이 두 경우에서 새롭게 칠해야 하는 판의 최소값을 출력하면 정답이 된다. 해결법 나는 이 문제를 해결하기 위해서 W로 시작하는 경우와 B로 시작하는 경우의 배열을 만들었다. 체스판 전체를 만들어주고 하나씩 비교해가며 다른 경우 count 를 증가시키면 된다. String[][] bw = { { "BWBWB.. 2021. 2. 17.

[알고리즘 PS] 백준 2309번 일곱 난쟁이 자바 문제풀이 문제 해당 포스팅은 백준의 2309번 일곱 난쟁이 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 아주 대표적인 완전 탐색 알고리즘의 문제라고 할 수 있다. 완전 탐색 알고리즘은 입력의 범위가 충분히 작은 경우 혹은 입력에 대한 경우의 수가 시간 복잡도 범위를 만족할 때 사용할 수 있는 알고리즘이다. 이 완전 탐색에서도 여러 기법이 존재하지만 이번 문제는 브루트 포스 알고리즘을 통해서 해결해보자. 브루트포스 알고리즘은 가능한 모든 경우를 다 해봄으로 답을 찾는 알고리즘이다. 우선 일곱 난쟁이들의 키 합이 100이라고 했으니 7번의 조건과 fo.. 2021. 2. 15.

[알고리즘 PS] 백준 14500번 테트로미노 자바 문제풀이 문제 해당 포스팅은 백준의 14500번 테트로미노 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제도 완전 탐색으로 해결할 수 있는 문제이다. 어떻게 나는 완전 탐색으로 풀 수 있는 문제라고 생각했을까?? 우선 주어진 문제에서 원하는 답을 찾기 위해서는 테트로미노 하나를 놓아서 최대의 합을 구해야 한다. 그럼 당장 생각나는 것은 n by m 크기의 배열을 하나씩 검사하면서 최대 합을 구하면 될 것 같다는 생각이 든다. 이제 여기서 이 문제를 완전 탐색으로 풀 것인가, 이분 탐색으로 풀 것인가를 정할 수 있다. 완탐이나 이분 탐색(혹은 다른 탐색 .. 2021. 2. 15.

[알고리즘 PS] 백준 3085번 사탕 게임 자바 문제풀이 문제 해당 포스팅은 백준의 3085번 사탕 게임 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 문제를 보고 우리가 먼저 해야할 일은 무엇일까? 바로 경우의 수에 따른 시간 복잡도 계산이다. 이 시간복잡도가 어떻게 나오고 통과를 하냐 마냐에 따라서 사용할 수 있는 알고리즘의 폭이 다양해진다. 이번 문제에서는 2개의 조건을 생각해서 보면 된다. 인접한 칸의 두 원소를 교환한다. 가장 긴 연속 부분 행,열을 고른 다음 먹는다. 인접한 칸의 두 원소를 교환한다. n x n 행렬에서 모든 원소가 인접한 칸을 고를 경우의 수는 얼마나 될까? 아마 4 * n^2이 .. 2021. 2. 14.

이전 1 ··· 5 6 7 8 9 10 11 ··· 25 다음

티스토리툴바