본문 바로가기

완전탐색

[BOJ] 백준 [1062] 가르침 JAVA
알고리즘,PS/백준 2022. 6. 1. [BOJ] 백준 [1062] 가르침 JAVA https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 📝문제 📝풀이 단순히 문자열 완전탐색으로 풀 수 있었다. 우선, anta tica 부터 5개의 알파벳을 차지하고 시작하므로 k>5 인경우에만 진행해야 한다. pattern matching 함수를 사용하여 만약, 해당 패턴의 단어가 있으면 anta tica를 제외한 부분만 문자열 리스트에 추가한다. 알파벳 방문 체크 배열 visit 을 하나씩 체크하다가 k 개의 갯수가 되었다면 문자열 리스트..
[BOJ] 백준 [15686] 치킨배달 JAVA
알고리즘,PS/백준 2022. 3. 25. [BOJ] 백준 [15686] 치킨배달 JAVA https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [문제] [풀이] 치킨 집 - 가정 집 사이의 거리를 최소로 하는 치킨 집들을 구해서 거리 합을 구하는 문제이다. 주어진 map 상태를 보면 중간에 벽이 없이 거리는 (x2-x1)+(y2-y1) 으로 구하면 되기 때문에 그래프를 탐색 하지 않고 모든 치킨 집과 가정 집 사이의 거리를 다 구해서 최소를 찾는 완전탐색을 하면 된다. 탐색의 크기는 치킨 집 좌표의 갯수를 기준으로 ..
[BOJ] 백준 [14889] 스타트와 링크 JAVA
알고리즘,PS/백준 2021. 11. 29. [BOJ] 백준 [14889] 스타트와 링크 JAVA https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [문제] [풀이] 만약 , 1번과 2번이 같은 팀이 된다면 능력치의 합은 S12+S21 = 5이다. 만약 , 1, 2, 3번이 같은 팀이 된다면 능력치의 합은 S12+S21+S23+S32+S13+S31 이다. 즉 , 완전탐색으로 모든 조합을 맞춰보면서 , 진행한 깊이(depth)가 한 팀(n/2) 만큼 진행했을 때, visit=true 인 팀의 시너지 총합을 A팀 이라 하고 , 이때 visit=false 인 팀의 시너..
[BOJ] 백준 [6603] 로또 JAVA
알고리즘,PS/백준 2021. 11. 29. [BOJ] 백준 [6603] 로또 JAVA https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net [문제] [풀이] 완전탐색 기초문제이다. 주어진 K 개의 숫자 중 6개만 뽑아서 모든 경우의 수를 만들어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import java.util.*; import java.io.*; import..
[프로그래머스] [Level2] 순위 검색 JAVA
알고리즘,PS/프로그래머스 2021. 11. 16. [프로그래머스] [Level2] 순위 검색 JAVA https://programmers.co.kr/learn/courses/30/lessons/72412
[프로그래머스] [Level2] 메뉴 리뉴얼 JAVA
알고리즘,PS/프로그래머스 2021. 11. 15. [프로그래머스] [Level2] 메뉴 리뉴얼 JAVA https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr [문제] [풀이] 탐색+조합+정렬 문제이다 .. 주문마다 구할수 있는 모든 조합을 course의 개수에 맞춰서 뽑아낸다. 그런다음 제일 많이 뽑힌 조합을 카운트해서 리턴 하면된다. menuMap 로 나온 모든 조합을 다 집어 넣는다. resultMap 로 제일 많이 나온 메뉴의 카운트가 몇개 인지 카운팅해서 넣는다. 그런다음 me..
[BOJ] 백준 [1339] 단어 수학JAVA
알고리즘,PS/백준 2021. 10. 25. [BOJ] 백준 [1339] 단어 수학JAVA https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 수학적으로 더 쉽게 풀 순 있지만 , 완전탐색 그리디를 연습중이므로 완전탐색으로 접근하였다. 주어진 단어들의 알파벳들이 몇 가지인지 리스트에 저장. 알파벳에 0~9 까지의 숫자들을 완전탐색으로 매핑 탐색이 진행될때마다 depth 카운트를 하나씩 증가시키면서 주어진 단어의 길이와 depth가 같아질 때 탐색을 그만하고 계산해서 제일 높은 값이 나오면 끝 1 2 3 4 5 6 7 8 ..
[프로그래머스] [Level2] 소수찾기 JAVA
알고리즘,PS/프로그래머스 2021. 10. 20. [프로그래머스] [Level2] 소수찾기 JAVA https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 풀이 완전탐색 + 백트래킹 문제이다 주어진 numbers 로 모든 순열을 만들어서 소수인지아닌지 판별하여 카운트를 리턴하면된다. String -> int 형으로 바꿀 때 , "01234" 이런것도 1234 로 변환할 수 있는 메서드가 Integer 라이브러리에 있다. Integer.valueOf 라는 메서드로 변환을 한 다음, 중복을 허용하지..
LIST
Recent Posts
Popular Posts
Archives
Visits
Today
Yesterday

티스토리툴바