본문 바로가기

Algorithm/완전탐색12

[백준] 1090번 체커 사용 언어 - Python3 문제 - 1090번 체커 1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 정답 경우의 수 줄이는 완전 탐색 (정답 맞춘 여부 X) 아이디어 생각하기 1. 2차원 => 1차원으로 계산 가능 2차원 = 1차원 계산 + 1차원 계산 이동 횟수 = (만나려는 곳의 x좌표 - 각 체커의 x좌표) + (만나려는 곳의 y좌표 - 각 체커의 y좌표) 2. 우리의 집 중 한 곳에서 모이기 이동 횟수를 최소화하기 위해선, 가장 가운데 있는 좌표위치가 가장 덜 움직인다. => x의 범위 :.. 2023. 9. 10.
[백준] 2503번 숫자 야구 (완전탐색) 사용 언어 - Python3 문제 - 2503번 숫자 야구 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 정답 단순구현 (정답 맞춘 여부 X) 1. abc 세 숫자를 모두 만들어준다. abc는 겹치지 말아야하며, 1부터 시작한다 2. 스트라이크와 볼 수 확인해준다. abc와 입력받은 숫자의 위치가 같다면 스트라이크 += 1 위치는 다르지만, abc 안에 있다면 볼 += 1 3. 볼과 스트라이크 수가 입력받은 수와 같다면 counter +=1 하나 성공! 4. counter가 n과 같아지면, 모든 조건을 충족.. 2023. 9. 10.
[백준] 19532번 수학은 비대면강의입니다 사용 언어 - Python3 문제 - 수학은 비대면강의입니다. 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 정답 완전탐색 (정답 맞춘 여부 O) 1. 소거법 a,b,c,d,e,f = map(int,input().split()) x = (c*e-f*b)//(a*e-d*b) y = (c*d-f*a)//(b*d-e*a) print(x,y) 2. 완전 탐색 끝판왕 해답 각 정ㅅ들이 -99에서 999까지로 범위제.. 2023. 9. 10.
[백준] 14568번 2017 연세대학교 프로그래밍 경시대회 사용 언어 - Python3 문제 - 2017 연세대학교 프로그래밍 경시대회 14568번: 2017 연세대학교 프로그래밍 경시대회 규칙에 맞게 사탕을 분배하는 경우의 수를 출력한다. 택희, 영훈이, 남규가 받은 사탕의 수를 각각 A, B, C개라고 할 때, 서로 다른 (A, B, C) 순서쌍의 수를 세면 된다. 만일 규칙에 맞게 사탕을 분 www.acmicpc.net 정답 완전탐색 - 각 조건 생각하기 (정답 맞춘 여부 O) 1. range 범위 지정하기 영훈이는 1부터 N-3까지 가능 남규는 영훈보다 2이상이어야 하므로 영훈+2부터 N-1까지 가능 택희는 N에서 영훈과 남규를 뺀 나머지이고, 1보다 크며 짝수조건을 만족 => cnt += 1 N = int(input()) # 사탕 N개 cnt = 0 f.. 2023. 9. 10.
[백준] 1816번 암호 키 사용 언어 - Python3 문제 - 암호 키 1816번: 암호 키 현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다. 현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 www.acmicpc.net 정답 모든 소인수가 1000,000보다 작은지 확인 1. 소인수 = 1을 제외한 약수 2. 2부터 1000000까지 수로 나누고 나누어떨어진다면, 100만 이하의 약수가 존재한다는 의미 NO를 출력하고 break => 모든 경우의 수를 생각하는 완전탐색 방법 3. 100만까지 갔다면, 100만 이하의 약수가 존재하지 않는다는 뜻이므로 YES를 출력 N = int(input()) for _ in range(N): S = int.. 2023. 9. 10.
[프로그래머스 lv1] 대충 만든 자판 사용 언어 - Python3 문제 - 대충 만든 자판 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 새 def 함수를 만들어 활용하기 (정답 맞춘 여부 X) 1. 인덱스 반환 함수 ,check(keylist,character) keylist에서 character의 인덱스를 찾아 값을 반환해주는 함수 1부터 시작하기 때문에 +1을 해준다. 2. 각 target의 글자들에 대해 character로 저장한후, 각 key 값에 포함되어 있는 지 확인한다. if character in set(keylist): cur = min(cur, check(keylis.. 2023. 4. 24.
[프로그래머스 lv 2] 모음사전 사용 언어 - Python3 문제 - 모음사전 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 순열조합 완전탐색 or 규칙 찾는 문제 (정답 맞춘 여부 X) 정답 풀이 1. product(리스트, repeat=반복횟수) 중복순열 이용하기 product는 처음 알게되었다. product(리스트, repeat=반복횟수) : 중복 순열. 1부터 5까지 반복해야하기 때문에 for문으로 구현한다. words 빈리스트에 list(중복순열)을 append해서 모든 가능한 조합을 저장한다. 그 뒤 words리스트를 sort 정렬을 하고, index를 찾는다. ind.. 2023. 2. 15.
[프로그래머스 lv2] 피로도 사용 언어 - Python3 문제 - 피로도 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 순열을 활용한 완전 탐색 문제 (정답 맞춘 여부 X) 정답 풀이 from itertools import permutations permutations(list명, 원소개수) = 원소개수만큼 순열 만들기!!! 현재 피로도 k dungeons = [최소 필요 피로도,탐험후 소모 피로도] 방법1. answer = [] 빈 리스트를 만들어서 cnt 값 저장해주고, max값을 출력. 방법2. answer = -1 cnt값과 answer 값 비교해서 max값 출력. an.. 2023. 2. 10.
[프로그래머스 lv 2] 카펫 사용 언어 - Python3 문제 - 카펫 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 규칙 찾는 완전 탐색 문제 (정답 맞춘 여부 X) 정답 풀이 규칙 찾기 (가로 축 a, 세로 축 b) (a-2)*(b-2) = yellow 2*a + 2*b - 4 = brown => yellow + brown = ab total = yellow + brown 이라고 했을 때, total / b = a # 정답 def solution(brown, yellow): answer = [] total = yellow + brown for b in range(1,tota.. 2023. 2. 7.
[프로그래머스 lv 2] 소수 찾기 사용 언어 - Python3 문제 - 소수찾기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 순열조합 생성 후 소수 판별하는 완전 탐색 문제 (정답 맞춘 여부 X) 정답 풀이 1. numbers를 하나씩 자르기 nums = [n for n in numbers] 2. 순열조합 생성 list(permutations(nums,i)) 3. 소수 판별 check True/False 4. set으로 중복 제거 후 개수 return # 정답 from itertools import permutations def solution(numbers): answer = [.. 2023. 2. 7.

티스토리툴바