# 완전탐색
[level 3.1] 완전탐색 - car
컴퓨터를 제조하는 회사인 KOI 전자에서는 제조하는 컴퓨터마다 6자리의 고유번호를 매긴다. 고유번호의 처음 5자리에는 00000부터 99999까지의 수 중 하나가 주어지며 6번째 자리에는 검증수가 들어간다. 검증수는 고유번호의 처음 5자리에 들어가는 5개의 숫자를 각각
[level 3.1] 완전탐색 - car
서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 것이다. 예를 들어, 자동차 번호의 일의 자리 숫자가 7이면 7일, 17일,
재귀(Recursion)
가능한 방법을 전부 만들어 보는 알고리즘 들을 가리켜 '완전 탐색(exhaustive search)' 라고 부른다. 손으로 직접 풀기에는 경우의 수가 너무 많은 경우, 완전 탐색은 (컴퓨터의 처리속도를 이용하여)충분히 빠르면서도 구현하기 쉬운 대안이 된다.간단한 예로,
[프로그래머스] 단체사진 찍기 (Java)
프로그래머스 단체사진 찍기캐릭터들이 옆으로 나란히 서서 단체 사진을 찍을 때 각 캐릭터들이 요구하는 모든 조건을 만족하는 경우의 수를 구하는 문제다. 역시나 가장 먼저 완전탐색을 생각해봤다. 캐릭터들이 나란히 서는 모든 경우를 구하고 각 경우가 캐릭터들의 요구조건을 만
[프로그래머스] 문자열 압축 (Java)
프로그래머스 문자열 압축완전탐색 문제로 구현에 조금 신경을 쓰면 쉽게 풀 수 있는 문제였다. String 비교로 구현하면 시간초과가 나지 않을까 걱정하여 다른 방법을 열심히 생각해봤지만 모두 구현이 어렵거나 더 오래걸릴 것 같아서 String 비교로 구현을 했는데 다행
프로그래머스 level1. 모의고사
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges각각의 수포자 별로 정답을 찍는 패턴을 배열로 저장하여 정답 배열을 순회하면서 각각의 수포자의 정답을 체크하여 마지막에 배열에 답을 추가하는 방식
[BOJ 16638] 괄호 추가하기 2 (Java)
BOJ 16638 괄호 추가하기 2괄호 추가하기 1은 쉽게 풀었던 것 같은데 비슷한 아이디어가 다시 떠오르지 않아서 힘들었다. 이 문제의 핵심 아이디어는 다음과 같다.괄호는 연산자 기준으로 씌워진다.괄호를 어떻게 씌워줄까 굉장히 고민되는데 괄호는 연산자를 중심으로 씌워
[BOJ 16986] 인싸들의 가위바위보 (Java)
BOJ 16986 인싸들의 가위바위보첨부그림 때문에 문제를 풀 의욕이 없어지는 문제, 하지만 알고보면 평소에 풀던 완전탐색과 다를 바가 없다.지우가 낼 수 있는 N개의 손동작을 순열로 구한다.지우, 경희, 민호의 게임을 시뮬레이션 한다.승부가 발생할 경우 경기 진행 순
[BOJ 16985] Maaaaaaaaaze (Java)
BOJ 16985 Maaaaaaaaaze초보자 입장에서 정말 변태같은 문제였다... 사실 알고리즘은 어려운게 아니지만 할게 너무 많았다.. 또 맵을 계속해서 복사해서 사용해야 했기에 까다로웠던 문제판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다.5개의 판을 쌓는 방법
[BOJ 17779] 게리맨더링2 (Java)
BOJ 17779 게리맨더링2 문제풀이 이 문제의 가장 중요한 점은 겁먹지 않는 것 주어진 조건을 그대로 사용하기만하면 굉장히 쉽게 풀리는 문제인데 너무 많은 수식이 나와있어서 겁먹게된다. 쫄지말자. 주어진 조건을 바탕으로 x, y, d1, d2 를 4중 반복문으로 선택한다. (이게 쉬우니까) 주어진 조건을 바탕으로 경계선을 그린다. 주어진 조건을 바탕...
[SWEA 5658] 보물상자 비밀번호 (Java)
SWEA 5658 보물상자 비밀번호 첫 인상에 비해서 쉬운 문제였지만 놓친 것이 몇 가지 있었던 아쉬운 문제였다. 문제를 잘 읽자, 정리를 잘 하자 문제 풀이 자물쇠 각 변의 16진수를 10진수로 변환시켜 TreeSet에 삽입한다. 시계 방향으로 회전한다. N-1 번 회전하며 1~2를 반복한다. TreeSet 을 배열로 바꾸고 length - K 번째 ...
Brute force 문제3 - 시계 맞추기
image.png 문제 풀이 과정 > brute force를 통한 문제임을 알고 봤음에도 풀이 방법이 명확히 떠오르지 않았는데, 가장 큰 이유는 해결 가능한 문제로 바꿔주는 조건인 각 시계는 최대 세 번까지 밖에 조작하지 못한다는 조건을 깨닫지 못했기 때문이다. 시계는 세 시간씩 움직이므로 네 번 조작하게 되면 다시 처음의 시간으로 돌아가게 되고 이...
Brute force 문제2 - 게임판 덮기
image.png 2019-06-25 19:06 작성됨 문제 풀이 과정 문제 파악 > #과 .으로 이루어진 게임판에서 ㄱ자 모양의 블럭을 퍼즐처럼 채우는 경우의 수를 찾는 문제이다. 그래프와 기하 문제에 약해서 이런 문제는 보기보다 어렵게 느껴졌다. Brute force를 활용하는 문제이기 때문에 한 블록을 빈칸에 넣을 때마다 새로운 문제로 나뉘는건 명...
Brute force
재귀호출 > 단순히 중첩문을 반복하는 것에 비해 코드 수정이 용이해서 재활용 가능성이 높다. > 재귀 함수의 종료를 위해 기저 사례를 선택해야한다. 재귀 함수가 가장 깊숙한 곳으로 들어간 경우, 재귀 함수의 목적을 달성한 경우, 반드시 지켜야 하는 특정 조건을 위배한 경우 더 이상 함수가 호출될 필요가 없기 때문에 함수가 반환되도록 해주는 것이다. >...