백준11 [알고리즘] 순열과 조합 알고리즘을 풀이할 때 가장 처음으로 해보아야 하는 것은 브루트 포스(Brute Force), 즉 완전 탐색이다. 이러한 완전 탐색을 하기 위해서 필요한 지식 중 한 가지는 바로 순열과 조합이며 이번 게시물에서는 순열과 조합을 다룬다. n가지 물건이 있다고 가정한다면, 순열은 n가지 물건에서 r개를 순서를 고려하여 선정하는 것이다. nPr의 기호로 표현하며 가지 수를 계산한다면 nPr = n(n-1)(n-2)....(n-r+1) 이 된다. 조합은 n가지 물건에서 r개를 순서를 고려하지 않고 선정하는 것이며 nCr의 기호로 표현하며 가지수를 계산한다면 nCr = nPr / r! = n! / r!(n-r)! 이다. 이를 코드로 구현하면 다음과 같다. public class Main { static ArrayL.. 2021. 2. 15. 백준 7562 나이트의 이동 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 백준 7562번 나이트의 이동 가볍게 BFS를 통해 해결할 수 있는 문제입니다! 기존의 BFS 문제를 해결할때 사용하던 Delta X, Delta Y 배열에 상하 좌우가 아닌 나이트의 이동이 가능한 방향인 8방향을 넣고 BFS를 진행하니 간단하게 시작점에서 도착점까지의 최소 구간을 구해낼 수 있었습니다. 아래는 코드입니다! import java.io.BufferedReader; import java.io.IOEx.. 2021. 2. 9. 백준 15683번 감시 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 브루트포스를 통해 해결하는 문제입니다! 이전에 도전을 했었다가 실패한 문제인데 이번엔 해결하였습니다ㅎㅎ 구현한 부분은 다음과 같습니다. 브루트포스를 통해 CCTV의 방향 정해주기 현재 CCTV 위치와 빛을 쏠 방향을 입력해 빛을 쏘기 각 CCTV 유형마다 상태에 따른 빛을 쏘는 방향 구현 코드가 무지하게 길게 나오네요... 더 짧게 줄이는 방법이 있을지 고민해보아야겠습니다. import java.aw.. 2021. 1. 20. 백준 2309번 일곱 난쟁이 www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브루트포스 문제입니다! 순열과 조합의 nCr에서 n이 9, r이 7인 경우를 구하는 것으로 9명의 난쟁이 중 7명을 골라 키의 합이 100인지 확인하는 문제였네요! 저는 재귀를 통해 해결하였습니다. import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Seve.. 2021. 1. 20. 이전 1 2 3 다음
