본문 바로가기

Algorithm/etc111

[파이썬] 프로그래머스 : 타겟 넘버 (Lv.2) [파이썬] 프로그래머스 : 타겟 넘버 (Lv.2) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0.방향성 생각 리스트 길이가 20 이하이다. 2**20 = 10만이라 잡으면 완탐으로도 충분히 가능 1. 중복 순열 from itertools import product as P def solution(numbers,target): answer = 0 leng = len(numbers) for i in P([1, -1], repeat=leng): if sum(map(lambda x,y: x*y, numbers,i)) == target: answer +=.. 2023. 11. 10.
[파이썬] 백준 1405 : 미친로봇 (골드4) [파이썬] 백준 1405 : 미친로봇 (골드4) 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 문제 풀이 0. 방향성 생각 백트래킹 기본 4**14 = 2*28 = 250만 탐색 경우의수 많다 -> 백트래킹 가지치기 1. 입력 temp = list(map(int, input().split())) n,prob = temp[0],list(map(lambda x: x/100, temp[1:])) visit = [[False]*29 for _ in range(29)] visit[14][14] = True ste.. 2023. 11. 5.
[파이썬] 백준 1234 : 크리스마스 트리 (골드2) [파이썬] 백준 1234 : 크리스마스 트리 (골드2) 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 풀이 방향성 생각 트리 높이가 10이고 각 높이에 같은 개수로 채우는 방식이 매우 제한적이다. 하드코딩으로 높이마다 처리해주기 처음에 개수를 많이 소모해야 가지치기로 불필요한 케이스를 많이 잘라낼 수 있다. 낮은 높이부터 채워서 꼭대기로 올라간다. 만약 쌓다가 공이 부족하면 탈출. 끝까지 올라갈 수 있으면 리스트에 저장한 가짓수를 모두 곱해서 answer에 더한다. 전체코드 n,red,green,blue .. 2023. 11. 5.
[파이썬] 백준 17825 : 주사위 윷놀이 (골드2) [파이썬] 백준 17825 : 주사위 윷놀이 (골드2) 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 문제 풀이 0. 방향성 생각 완탐 4^10 == 10**6 -> 중간에 조건에 부합하지 않는 경우 탐색x -> 백트래킹 맵 구현은 그냥 인덱스 짜서 구현했음... 1. 입력 dice = list(map(int,input().split())) info = {i:[0,i+1,i+2,i+3,i+4,i+5] for i in range(33)} info[16] = [0,17,18,19,20,21] info[17] = [0,18,19,20,21,21] info[18] = [0,19,20,21,21,21] info[19] = [0,20,21,21,.. 2023. 10. 22.

티스토리툴바