Coding World

백트랙킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법. DFS와 백트랙킹의 차이? - DFS : DFS는 가능한 모든 경로(후보)를 탐색합니다. 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 해동이 없으므로 경우의 수를 줄이지 못한다. - 백트랙킹 : 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아 가는 것 . 코딩에서 쓸데없는 반복문의 횟수를 줄일 수 있으므로 효율적이다. 이러한 로직을 "가지치기"라고하며 불필요한 부분을 쳐내고 올바른 쪽으로 향한다는 의미이다. 만약 N!의 경우의 수를 가진 문제에서 최악의 경우 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 즉 백트랙킹은 모든 가능한 경우의..

www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net import heapq import sys mod=1000000007 for _ in range(int(sys.stdin.readline())): n=int(sys.stdin.readline()) e=list(map(int, sys.stdin.readline().split())) ans=1 if n==1: print(1) continue q=[] for i in e: h..

aisiunme.github.io/algorithm/2018/08/13/baekjoon-group-word-checker-1316.md/ 백준 온라인 저지 - 그룹 단어 체커(1316) Baekjoon Problem #1316 - 조건에 맞는 단어를 찾는 문제 aisiunme.github.io Jun Lee 님의 글을 참고하였습니다. 우선 제 코드는 틀렸습니다. cnt=0 for _ in range(int(input())): w={} idx="" word=input() if len(word)==word.count(word[0]) and len(word)>2: continue for i in word: if (i not in w)or idx==i: w[i]=True else: w[i]=False idx=i..

n=input() c=["c=","c-","dz=","d-","lj","nj","s=","z="] cnt=0 for i in c: if i in n: cnt+=n.count(i) n=n.replace(i," ") print(cnt+len(n.replace(" ",""))) 입력 크로아티아 알파벳 리스트 생성 알파벳 리스트를 돌며 입력한 문자열(n)검색 몇개 있는지 카운트(cnt+)하고 replace로 몽땅 빈 칸으로 변경-> 공백을 없애버리면 이전 문자와 다음 문자가 붙어서 크로아티아 알파벳으로 인식해버린다. cnt 값 + 빈 칸 제거한 n의 길이의 합을 구하면 된다. 내 풀이가 영 찝찝해서 다른 사람의 풀이를 찾아보았다. (실수로 아이디를 확인 못했습니다.) t=input() for i in ['c='..

www.acmicpc.net/workbook/view/2052 문제집: N과 M (시리즈) www.acmicpc.net itertools 사용 1) 순열 from itertools import permutations as p n,m=map(int,input().split()) for i in p(range(1,n+1),m): print(*i) 2) 조합 from itertools import combinations as p n,m=map(int,input().split()) for i in p(range(1,n+1),m): print(*i) 3) 중복 순열 from itertools import product as p n,m=map(int,input().split()) for i in p(range(1,..

import sys n=int(sys.stdin.readline()) arr1=list(map(int,sys.stdin.readline().split())) cnt=1 for i in range(n-1): arr2=list(map(int,sys.stdin.readline().split())) if arr1[1]= 0 이므로 조건문에 부합하면 arr1=arr2 해준다. 어디서 틀린 거지? --- 입력받은대로 횟수를 구하는게 아니라 모든 입력에 대해서 최대 사용 가능 횟수를 구하는 거다. 문제를 제대로 못 봤다. 이렇게 되면 끝나는 시간을 기준으로 우선 정렬을 한 뒤 시작 시간으로 정렬해준다. 왜냐하면 10 15 1 5 5 10 이렇게 있을 때 이대로 결과를 내면 회의가 1회 밖에 못하지만 정렬을 하면 1 ..

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 코드: n=int(input()) arr=list(map(int,input().split())) arr.sort() p=[] for i in range(1,n+1): p.append(sum(arr[:i])) print(sum(p)) 풀이: 테스트 케이스 , 시간을 입력받고 arr은 최소 시간을 구하기 위해서 정렬시킨다. 개인별로 소요되는 시간 Pi를 담을 빈 리스트 p 를 생성한다. arr에는 시간 순으로 나열되어 있으므로 for 문으로 하..

www.acmicpc.net/problem/10828 import sys n=int(sys.stdin.readline().rstrip());s=[] for _ in range(n): i=input() if i.__contains__("push"): v= list(map(str,i.split()))[1] s.append(v) elif i=='top': if s:print(s[-1]) else:print(-1) elif i=='size': print(len(s)) elif i=='empty': if not s:print(1) else:print(0) elif i=='pop': if s: s.pop() else:print(-1) 결과 : 시간초과 - 어째서지?..

* '박트리'님의 알고리즘 공부 포스트를 참조하였습니다. 알고리즘 공부, 어떻게 해야하나요? 오랜만에 정상적인 포스팅을 쓴다. 메일로 가장 많이 물어 보는 질문들이 [알고리즘 공부 어떻게 해야하나요? 어떻게 하셨어요? 뭘 공부해야 할 지 모르겠어요.] 와 같은 질문들이다. 위 질문에 baactree.tistory.com - PS 실력을 올리기 위해 갖춰야 할 기본 요소 1. 구현력 2. 문제해결능력 3. 배경지식 - PS 을 위해 요구되는 배경지식들 1. 코딩 문법 2. 시,공간 복잡도 분석 3. 배열 4. 트리 5. 그래프 6. BST(Binary Search Tree, 이진 탐색 트리) 7. DFS, BFS 8. 백트래킹 9. DP(Dynamic Programming) 10. 분할정복 11. 최단거리..