브루트 포스 알고리즘으로 문제풀기 (스테픈 2km완료)
어제 알고리즘과 시간복잡도에 대해서 공부를 해보고
백준 코딩테스트 문제를 풀어봤다.
예전에 풀어보던 프로그래머스와는 다르게 상당히 불편하다.
일단 프로그래머스는 기본적으로 스크립트만 잘 작성하면 되서
나머지는 신경을 안써도 되는데
백준 같은경우에는 아무것도 쓰여있지 않아서
데이터 입력 받는 부분에서 익숙해지는데 시간이 조금 필요했다.
--
아무튼 시간복잡도를 공부하고 백준 문제를 풀어보던중에 브루트 포스 알고리즘 문제를 접하게 되었다.
브루트 포스 알고리즘은 뭘까?
완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.
모든 경우의 수를 다 탐색하니 예외 없이 100%의 확률로 정답만을 출력한다.
완전탐색의 예시를 보자면
잃어버린 비밀번호 찾기와 같다.
비밀번호를 까먹은 여행가방을 열기 위해서는
우리는 0000부터 9999까지 모든 경우의 수를 다 찾아가며 가방을 열기위해 도전할것이다.
브루트 포스 알고리즘도 이것과 비슷하다.
복잡한 알고리즘을 굳이 생각하지않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 다 살펴보는 것이다.
브루트 포스 알고리즘에는 종류가 있을까?
답을 구하기위해 모든 경우의 수를 구하는 것이기에 따로 알고리즘이라고 붙이는건 좀 거창한것 같지만..
완전탐색에는 종류가 있다.
- 선형구조 : 순차탐색
- 비선형구조 : 깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, breadth first search)
정도가 가장 기본적인 방식이다.
그렇다면 이러한 브루트 포스 알고리즘으로 문제를 어떻게 해결해야할까?
① 주어진 문제를 선형 구조로 구조화한다.
② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
③ 구성된 해를 정리한다.
그럼 백준의 문제 2개를 이용해서 완전 탐색을 정리해보자
일단 문제를 풀때 독해력이 중요한것 같다.
코딩 하는건 어렵지 않은데.. 어떤식으로 이 문제를 접근해서 풀어야하는지가 떠오르지 않아서
코딩 자체를 못하는 경우가 있다.
아무튼
이 문제를 풀어보려고 한다.
이 문제에서는 완전탐색을 위해서 가장 중요한 힌트가 나와있다.
바로 유일한 값이 존재한다는것
그리고 범위
두가지가 나와있으니 완전탐색을 돌릴 조건이 된느것 같다.
이제 X값을 구하고 y값을 구해주면 된다.
별다른 로직을 고민하지 않고 그냥 문제가 적혀있는대로 구현했다.
저 연립방정식의 값인 C와 F 가 이미 정해져있기 때문에
X, Y만 -999 ~999 사이로 넣어주면서 무한 반복시키면 결국 답이 나오게 되어있다.
별다른 고민이 없이 풀려서 생각보다 허탈하다.;
다른 문제도 하나 더 풀어보자
일단 제목부터 쉬워보여서 풀어봤다.
일단 문제를 읽어보면
이사람이 영화를 만들때 영화제목에 666을 연속으로 붙여서 만들고 싶다한다.
예제 입력과 출력을 읽어보면
영화 1편은 아마 666 이 제목일거고
2편은 1666이 제목이라고 나와있다
3편은 2666
여기까지만 보면 그냥
이런식으로 뒤에 666만 붙여주면 될것같은 문제처럼 보인다.
하지만 문제를 자세히 보면 187번째 영화에서 출력값이
666666 이라고 나온다
위 함수처럼 만들게되면 186666 뭐 이런식으로 나와야 하는데
문제의 답은 666666을 가르킨다.
이말은 저런식으로 만드는게 아니라는 소리다.
내가볼때는 이번 문제는 666이 1편이니 665~부터 값을 계속 증가시켜서 숫자 6이 3번 연속으로 붙어있는 값이 나올때마다
input 값을 빼가면서 계산해서 맞추는 문제가 아닐까 싶다.
단순계산으로는 187번째에서 666666이 나올수가 없기 때문이다.
아마 6660 이상부터는 6661 6662 6663 6664 6665 여기에 전부 666이 연속으로 붙어있으니 카운트가 계속 빠지는 형식으로 구현이 되는게 아닐까 싶다.
그럼 어떻게 계산해야할까
반복문으로 666 숫자가 연속될때마다 카운트를 하나씩 빼서 이 카운트가 0이되면 중단시키면 될것같다.
666 숫자는 정규식으로 찾으면 될거같은데 일단 한번 코드를 짜보도록 하겠다.
문자로 형변환 이후 정규식으로 match 메서드를 사용하면 데이터가 있는경우 배열로 반환되지만 데이터가 없는경우
null값을 반환하니 null이 아닌경우에만 카운트를 낮춰지도록 구성하면 정상동작한다.
일단 indexof나 include를 사용해서도 처리가 가능한데
나에게 익숙한 정규식으로 처리했다. 생각보다 잘된다.
그렇게 어려운 문제는 아니었지만 문제의 의도가 정확하게 이해가 되지 않으면 코딩 자체가 엉뚱한 방향으로
작성하게되어 처음부터 잘못된 방향으로 구성하게된다.
생각보다 문제를 이해하는게 너무 중요하다.
이것도 제목은 쉬워보여서 선택했다.
음 일단 어떻게 접근하는게 좋을지 생각해봐야겠다.
N은 결국 3과 5로 만들수있는 모든 수를 찾아본뒤에
여기서 해당하지 않는 값은 -1을 주고
일단 최소한으로 하는경우는 N이 N%5 로 0이 나오는경우이고
가장 많은경우는 N%3인 경우이다.
조건을 3개를 걸었다.
while반복문으로 break문과 만나기 전까지 루프를 도는데
일단 모든 경우의 수를 받기위해
result 라는 배열을 만들어서
이 배열에 결과값을 밀어 넣는 방식으로 처리했다.
일단 루프가 돌때 한번에 처리가 안되는경우 -3을 빼주고 카운트를 한번 올려서 3을 뺐다는걸 표시했고
다음 루프가 돌때는 number에서 3이 빠진 값이 들어가니 5로 나뉘어진다면 브레이크를 걸어서 최소값을 받는 형식으로 구성했다.
이렇게 하면 최대값과 최소값을 다 구하는게 브루트 포스 알고리즘에 맞는게 아닌가 싶어서 ...
아무튼 정답인지 확인해봤다.
예시 문제는 통과되는데 다른 예제도 통과가 안되는지 테스트 해봐야겠다.
테스트 해보니 해당사항이 없을때 -1을 결과배열에 추가해야하는데
콘솔로만 찍고있었네요
이제 완성 되었습니다.
문제를 풀면서 느낀점은 코드 구현이 어렵다기보다는;; 문제 자체를 이해가 안되서 어떤식으로 접근해야할지
방향을 잡는게 가장 어려운것 같다.
이렇게 해서 하면 되겠다 하고 풀었는데 막상 결과를 보면 실패가 뜨는 경우가 많아서
문제를 천천히 읽고 어떤식으로 접근할지를 방향을 잘 잡기위해서는 더 많이 풀어봐야할것 같다.
스테픈 2km완료