본문 바로가기
728x90

알고리즘(w.KOTLIN)

 (97)
브루트 포스(Brute Force) 정의 brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 예제 1. 10의 약수의 합을 구하기 10의 약수가 될 수 있는 모든 자연수를 구조화 하자. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 자료를 선형으로 구성하였다. 구조화된 자료가 선형 구조이므로 순차 탐색을 활용하여 첫 번째 원소부터 마지막 원소까지 탐색한다. 탐색하면서 10의 약수가 되는 값만 남겨두고 10의 약수가 될 수 없는 값을 배제한다. 10의 약수는 10을 현재 우너소로 나누어떨어지면 그 원소는 1..
[백준][KOTLIN][15652] N과 M(4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 1. dfs 를 이용하여 주어진 입력 N, M 에 대해서 탐색한다. 2. 이때 숫자를 중복해서 사용해도 되기 때문에 visit 배열을 사용하지 않는다. 3. 비내림차순순열이어야 하기 때문에 현재 arr 의 마지막 값이 탐색하는 index 보다 작거나 같으면 arr 에 값을 넣고 dfs 를 수행하고 크면 dfs 를 수행하지 않고 다음 index 를 탐색한다. 4. M 과 depth 의 ..
[백준][2839] 설탕 배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 풀이 1. 주어진 입력 N을 5로 나눈다. 2. 나누어 떨어지면 몫을 결과로 출력한다. 3. 나누어 떨어지지 않으면 입력 -=3 을 하고 count 를 증가 시킨다. 3kg 봉지를 사용한 상황이 된다. 4. 1 ~ 3 과정을 입력이 0보다 크거나 같을 때 까지 반복한다. 입력이 0보다 작아지면 설탕 무게가 떨어지지 않으므로 -1을 출력 한다. 코드 import java.io.BufferedReader ..
[프로그래머스][Level1][178871] 달리기 경주 https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 주어진 callings, players 배열을 indexOf 를 이용하여 위치를 찾아 서로 swap 을 하게 되면 시간 초과 오류가 발생한다. 2. map 의 containsKey 를 이용하여 시간초과를 해결한다. 3. 이때 (Int, String) = (순위, 선수 이름) 을 가지는 map1과 (String, Int) = (선수 이름, 순위) 을 가지는 map2 를 선언한다. ..
[백준][코틀린][12904] A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 풀이 1. S 를 문자열을 바꾸는 조건을 이용하여 완전 탐색을 할 경우 시간 초과가 발생한다. 2. 타겟 문자인 T에 대해서 마지막 글자가 'A' 라면 이전의 글자에 'A' 만 더한 것이 된다. 3. 마찬가지로 T의 마지막 글자가 'B'라면 'B' 를 제외한 T를 뒤집는다. 4. S == T 일 경우 1을 출력하고 T의 길이가 1이 될때까지 탐색이 되었다..
[백준][코틀린][12970] AB https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 1. 문자열을 N의 길이만큼 Char 배열에 A로 채운다. 2. 문자열의 마지막 인덱스 부터 0번째 인덱스까지 현재 인덱스(i)의 문자를 'B'로 변환하면서 다음과 같이 탐색한다. 3. 0부터 N - 2 까지 j 인덱스를 가지는 for문과 j 부터 N - 1까지 k인덱스를 가지는 이중 for문을 이용하여 조건의 쌍을 이루는 개수를 구한다. 4. 개수의 합이 K보다 크면 i 인덱스의 문자를 'B'로 변환할 수 없으므로..
[백준][코틀린][1783] 병든 나이트 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 1. 병든 나이트의 이동 조건을 보면 오른쪽으로만 무조건 이동이 가능하고 이동 횟수가 아무리 많아도 4가지의 이동 조건을 만족 시키지 못하면 최대 횟수는 3이 된다. 2. 세로의 경우에 대해서 아래와 같이 최대 이동 회수를 확인 한다. - 세로가 1일 경우 : 위아래 이동이 불가능하므로 최대 이동 회수는 0이므로 방문 칸은 처음 위치만 포함된 1이 된다. O - 세로가 2일 경우 1. 가로가 3일 경우 1회 방문 가능하다. 2. 가로가 5일 경우 2회..
[백준][코틀린][10610] 30 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문제 풀이 1. 주어진 숫자를 30의 배수 중 가장 큰 수가 되게 하기 위해서 다음과 같은 조건을 찾는다. 2. 30의 배수는 3의 배수와 10의 배수의 최소 공배수이다. 3. 따라서 주어진 숫자는 10의 배수가 되면서 3의 배수도 되어야 한다. 4. 주어진 숫자를 내림 차순으로 정렬한다. 5. 10으로 나누어 떨어지지 않으면 -1을 출력한다. 6. 첫자리 부터 마지막 자리까지 더한 합을 3으로 나..

티스토리툴바