khakha's dev log

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 python으로 푼다면 set(집합) 자료구조를 잘 이용할 수 있어야한다. 먼저 유일성이고 뭐고 가능한 키 조합을 모두 구해준다. (시간될 때 itertools에서 제공하는 함수 말고 직접 구현해보기) 그 뒤에 아래 조건을 만족하도록 구현해준다. [유일성 : 릴레이션에 있는 모든 튜플에 유일하게 식별되어야 한다. ] 위에서 구한 인덱스로 구성된 키 조합을 각 속성값으로 대입하여 튜플로 ..

문제 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 접근 재귀로 모든 경우의 수를 구한 후, 0이 되는 경우만 출력해준다. 주의할 점은, 연산기호를 ' '(공백)으로 둘 때는 sum에 숫자를 더하지 않고, 숫자*10 + (i+1) (=> 앞의숫자에 다음숫자를 붙인것) 을 넘겨줘야한다. 마지막 턴일때 마지막으로 sum을 구해준 후, 0이되면 출력해준다. 코드 t = int(input()) def dfs(i, sum, sign, num, s): if i == n: sum += sign*num if ..

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 접근 완전탐색 풀이 1. 주어진 블록의 층들 중, 최소와 최대층을 구해준다. 2. 최소~최대 사이에서 특정 i층으로 블록의 층들을 모두 같게 만들어준다. 현재 i층보다 블록의 층이 클 때 1번 작업을 실행해서 블록을 제거한 후, inventory에 담고, 초를 계산해준다. 반대로, 현재 i층보다 블록의 층이 작을 때 2번 작업을 실행해서, inventory에서 해당 블록만큼 빼고, 초를 계..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 완전탐색 문자열을 자를 수 있는 단위의 갯수는 1 ~ 문자열 길이 반 까지 가능하므로 이 모든 갯수를 확인해봐야한다. 예를 들어, 갯수가 3개라면 (s = abcabcdede ) turn 1) s1 = abc s2 = abc s1 == s2 이므로, count = 2 turn 2) s1 = abc s2 = ded s1 != s2 이므로, temp_s = 2abc turn 3) s1 = ..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근 select_chicken() : 백트래킹으로 주어진 M 갯수만큼의 치킨 조합 구성 calc_dist() : 조합이 완성되면 각 집별로 가까운 치킨 거리를 구해서 도시의 치킨 거리 최솟값을 구해준다. 코드 # 백트래킹 풀이 N,M = map(int, input().split(' ')) city = [] home = [] chick = [] visit = [[0 fo..

문제 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 접근 백트래킹 + 브루트포스 중요한 부분은 dfs 내에서 cnt == n / 2 일 때 두 개의 팀으로 나눠서 각각의 능력치를 구해주는 것인데. 여기서 visited 배열을 활용해서 방문한 것과 방문하지 않은 것들 두개로 팀을 나눠서 능력치 계산 후 차이를 구해준다. 코드 n = int(input()) perform = [[] for _ in range(n)] for i in range(n): perform[i]..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근 브루트포스 (백트래킹) 주어진 +,-,*,/ 갯수를 하나씩 빼가면서 dfs 탐색 + 백트래킹을 통해 모든 경우의 수를 탐색한다. 코드 N = int(input()) num = list(map(int, input().split())) add, sub, mul, div = map(int, input().split()) min_value..