본문 바로가기

브루트포스12

[알고리즘] 영화감독 숌 (백준 1436번) 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 브루트 포스 문제다. 시간복잡도를 생각해봤을 때, 정말 최대로 가정해봐도 1천만번 정도기에 단순히 1씩 증가시키는 연산으로도 충분히 풀만하다. Solution 666, 1666, 2666 이런식으로 1000단위로 증가하다가 6660, 6661과 같은 구간이 생길 것이다. 처음에는 이걸 일일이 구할까 하다가 브루트 포스 문제이니 좀 더 단순하게 생각해보자 해서 그냥 1씩 증가시켜서 나오는 수마다 세상의 종말 수인지를 검사해서 count를 증가시키는 방식으로 구했.. 2020. 9. 27.
[알고리즘] 암호 만들기 (백준 1759번) 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 브루트 포스 문제이며 상당히 자주 볼 수 있는 문제의 유형이다. (물론 난이도가 낮아서 코딩 테스트에선 자주 안 나올 것 같다) 만들 수 있는 조합의 문자열을 DFS를 통한 완전탐색으로 찾아내는 케이스이다. 조합으로 계산해봤을 때 C가 맥스인 15가 되더라도 문자 하나가 정해지면 그 뒤에 올 수 있는 문자들의 범위는 계속해서 줄어들게 되기 때문에 시간복잡도가 크게 증가하지 않는다. Solution 입력받은 알파벳들을 사전식으로 오름차순 정렬한다. L글자를 구성가능한 .. 2020. 9. 27.
[알고리즘] 감시 (백준 15683번) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 브루트 포스 + 시뮬레이션 문제다. 감시 카메라의 유형과 유형마다 감시할 수 있는 방향의 경우의 수가 많기 때문에 모듈화를 잘 해야한다. Solution 위의 경우에서 1번에서 5번 카메라까지 각각 4, 2, 4, 4, 1가지의 경우의 수가 나온다. 이 경우의 수를 배열에 저장해놓는다. static int cases[] = {0, 4, 2, 4, 4, 1}; 또한 각 카메라의 위치를 ArrayList에 보관한다. for(int i = 0;i < N;.. 2020. 9. 19.
[알고리즘] 수식 최대화 (2020 카카오 인턴십) 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr 상반기 카카오 인턴십 때 나온 문제이다. 해당 코딩 테스트에 참가했었기에 기억이 난다. (통과는 못했다.) 이 문제도 결국 못 풀었던 걸로 기억한다. 지금와서 다시 찬찬히 살펴보니 결국 문자열 처리 문제이다. 정확히 말하자면 '브루트 포스 + 문자열 처리' 문제라고 할 수 있겠다. 브루트 포스 문제인만큼 재귀 함수 사용은 필수적이다. 모듈은 크게 2개로 나누었는데 첫 번째는 '연산자 우선순위 결정' 메서드이고 나머지 하나는 '수식 계산' 메서드이다. 연산자.. 2020. 8. 29.

티스토리툴바