khakha's dev log

문제 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..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 백트래킹 + dfs 벽을 세울 수 있는 자리에 3개 벽을 세우는 모든 경우를 찾고 모든 경우 마다 안전 영역을 dfs를 통해 구한 후, 가장 큰 값을 구해준다. 코드 from collections import deque # import copy import sys input = sys.stdin.readline def bfs(): # copy_area = copy.deepcopy(area) -> 속..

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근 백트래킹으로 모든 경우의 수의 합을 구해준다. 합이 s와 같으면 answer ++ 해서 부분수열의 갯수를 구해주먄된당 코드 n, s = map(int ,input().split()) number = list(map(int ,input().split())) answer = 0 def dfs(i,total,number,visited): global ans..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 백트래킹으로 모든 경우의 수를 계산해서 최소 경우를 구했다. dfs 함수 내에서 begin == answer의 경우 단어를 몇번 변경했는지 횟수를 가장 작은 걸로 갱신해준다. words 배열을 하나씩 가져와서 begin 단어와 다른 알파벳이 1개인 단어를 찾는다. 다른 알파벳이 1개이며, 그 단어로 변경을 진행하지 않았으면 횟수 + 1 해서 재귀를 돌린다. 빠져나왔으면 모든 경우의 수를..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 [DFS/BFS 차이점] DFS 최대한 멀리 있는 노드를 우선으로 탐색 ex) 덩어리 몇개인지 개수 세기 스택 이용 -> 재귀함수로 구현하면 간결하게 구현 가능하지만, 시간복잡도 고려 필요함 BFS 무조건 가까이 있는 노드부터 탐색 ex) 시작점부터 도착점까지 이동하는 최소 칸의 개수 큐 자료구조 이용 queue에 시작점 넣어준다. while 조건으로 queue가 비어있을 때까지 반복돌린..