For Programmer

이 문제 너무 까다로웠다.. 특히 지문 해석하기가 너무 힘들었다. 지문을 한 5번 읽은 후에야 문제를 제대로 이해할 수 있었다. 또한 dfs를 짜면서 반례찾기가 너무 힘들었다. 특히, 주위에 칠 계란이 없으면 바로 다음 dfs로 넘어가도록 처리해야하는 조건을 설정하는 것이 너무 어려웠다. (이 부분 때문에 80%에서 오답이 나와서 결국 답을 참고하였다. ㅠㅠ) def dfs(depth): global max_ if depth == N: # 만약 길이 N개를 뽑았다면 count = 0 for j in egg: if j[0]

이 문제 역시 간단한 dfs + 백트래킹 문제이다. 단, 리스트에 연산자 N - 1 개를 집어놓고 백트래킹 조건에서 리스트에 있는 연산자를 꺼내면서 계산하는 방식은 python3 에서는 시간초과가 발생한다. 따라서 계산한 즉시 num 이라는 인자로 전달하는 방식을 사용하니 시간초과가 발생하지 않았다. 1. 인자로 계속해서 계산 결과를 전달하는 방식(시간초과x) def dfs(depth, num): global max_ global min_ if depth == N - 1: if min_ > num: min_ = num if max_ < num: max_ = num return for i in range(len(oper)): if not visited[i]: visited[i] = True dfs(dept..

이 문제를 해결하는데 있어서 백트래킹 조건을 검사할 때 인자로 바로 숫자들을 문자로 바꿔 문자열로 더해서 인자로 넘기는 방식과 리스트에 담아서 sum으로 구하는 방식 2가지로 구현해보았다. 2가지 모두 코드를 제시해놓겠다. 1. 리스트 이용 def dfs(depth): global count global check if check: # 만약 check 변수가 true라면 전체 재귀 종료 return if len(arr) > n: # 만약 뽑은 수의 개수가 n보다 크다면 종료 return if depth > 0: # 1개 이상 뽑았다면 if sum(arr) == n: # 그 합이 n가 같다면 count += 1 # 개수 1개 증가 if count == k: # 만약 그 개수가 k랑 같다면 print('+'..

간단한 dfs 문제이다. 백트래킹 조건만 잘 걸어주면 된다. 백트래킹 조건은 주석으로 달아 놨다. def dfs(depth, start, password): if depth == L: vowel_count = 0 # 모음 개수 저장 for i in password: # 만들어진 password를 돈다 if i in 'aeiou': # 만약 해당 문자열에 모음이 있다면 vowel_count += 1 # 모음 개수 +1 if vowel_count = L - 1: # 만약 모음개수가 0이거나, 길이-1개 이상이라면 return # 자음이 최소 2개 이상 있거나, 모음이 최소 1개 이상 없으므로 재귀 종료 print(password) # 그 외경우 password 출력하고 return # 재귀 종료 for i ..

이 문제 쉬운 문제 치고 굉장히 고생했다. 또한 나의 dfs의 재귀개념에 대해서 다시 공부할 수 있는 좋은 계기가 되었다. 우선 음수가 끼여있으면 입력 받은 숫자들을 오름차순 정렬해서 만약 문제에서 요구하는 합보다 현재 합이 크다면 굳이 뒤의 원소들을 추가적으로 검사하지 않고 return하는 백트래킹 조건을 걸면 안된다. 왜냐하면 음수 끼리의 합은 더작아지기 때문이다. (예를들어 1 2 3 4 5 에서는 합이 5가 되는 경우를 찾을 경우 1 2 3 을 골랐다고 하였을때 이미 6이기 때문에 굳이 뒤에 원소들(4 , 5)을 검사할 필요 없이 바로 return 하고 2 부터 다시 검사를 하면 된다. 그러나 -7 -3 -1 5 8 에서 합이 -4가 되는 부분수열을 찾아야 하는데 -3은 이미 -4보다 크기 때문에..

간단한 구현 문제이다. count = [0] * (1000 + 1) # 개수를 셀 0 ~ 1000까지의 리스트를 0으로 초기화 sum_ = 0 #합을 계산할 변수 for _ in range(10): num = int(input()) sum_ += num # 합을 계속 더해준다. count[num] += 1 # 해당 num의 개수를 +1 씩 해준다. print(sum_ // 10) # 최대값 print(count.index(max(count))) # 최빈값

이 문제는 dfs로 숫자를 문자열로 생각하여 최대 1개부터 N개까지 뽑고나서 소수 판별 함수를 O(logN)의 시간 복잡도로 구현할 수 있으면 쉽게 문제를 해결할 수 있다. (코드를 다 구현해놓고나서 1일때 출력을 고려하지 않아서 오래 걸렸다. 참고하길 바란다.. )전체 코드와 주석을 달아놨으니 참고하면 된다! import math # 소수판별 함수 def check_not_prime(num): temp_num = '' # 각 자리마다 소수를 계산할 변수 for i in range(len(num)): count = 0 # 나눠 떨어지는 횟수를 셀 변수 temp_num += num[i] # 1의 자리부터 10의자리 100의 자리.. 계속 문자열로 더해준다. for j in range(1, int(math...

간단한 BFS 구현이다. Visited 리스트를 따로 만들어 해당 위치에서 도착지까지 얼마나 걸리는지 계속해서 확인해면서 가도록 구현했다. 단 DFS의 다양한 방법으로도 구현해 보았다. 모든 코드를 제시 하겠다. 1.BFS import sys from collections import deque sys.stdin = open('input.txt', 'r') def bfs(start): queue = deque([start]) visited = [[0] * N for _ in range(N)] visited[start[0]][start[1]] = 1 dr = [-1, 0, 1, 0] # 상우하좌 dc = [0, 1, 0, -1] # 상우하좌 while queue: r, c = queue.popleft() ..