본문 바로가기

장원익 기술블로그

💻 Computer Science191

[알고리즘 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.

[알고리즘 PS] 백준 1476번 날짜 계산 자바 문제풀이 문제 해당 포스팅은 백준의 1476번 날짜 계산 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 완전 탐색의 가장 기초적인 문제로 볼 수 있다. 완전 탐색 알고리즘 기법 중 브루트 포스 접근으로 해결할 수 있다. 브루트 포스 알고리즘은 시간 면에서 가장 비효율적인 알고리즘이지만, 가장 확실한 방법으로 알려져 있다. 해결법 이 문제를 해결하기 위해서는 E, S, M 이 1년이 증가할 때 마다 1씩 증가하는 특성을 이용한다. 우선 입력받을 E, S, M과 똑같은 e, s, m 변수를 하나 더 만들어 준다. 우리의 e, s, m을 각각 1씩 계속 .. 2021. 2. 14.

이전 1 ··· 7 8 9 10 11 12 13 ··· 32 다음

티스토리툴바