문제 적절하게 가지치기를 해줘야 시간제한 안에 AC를 받을 수 있는 문제. 가지치기를 하는 경우 1. \(MAP[i][j]\)가 1일 경우 2. 현재 써야하는 색종이의 수가 지금까지 구한 최솟값보다 더 커질 경우 1번의 경우, 어차피 모든 1을 색종이로 덮어야 하므로, \(MAP[1][1]\)부터 시작하여 1을 발견하면 바로 덮고 넘어간다. 더보기 #define imp -1 #include using namespace std; int map[10][10] = { 0 }; int field[10][10] = { 0 }; int ans = 999999999; int cnt = 0; int zero(int a, int b, int n) { if (a + n > 10 || b + n > 10) return -1..
문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net \(C\) 개의 알파벳이 주어졌을 때, 모음이 1개 이상, 자음이 2개 이상 포함된 크기 \(L\)의 가능한 모든 조합을 구하는 문제. 모든 경우의 수를 출력해야 하기 때문에, 백트래킹으로 풀 수 있으며 시간제한은 넉넉하다. 더보기 l,c = map(int,input().split()) c = sorted(input().split()) def f(flag,n,m,ls): if len(ls) == l: if flag == 0 or m < 2: return 0 re..
얻어 갈 것들 1. 프로그램은 내가 원하는 순서로 연산을 해주지 않을때가 있다. 괄호를 습관적으로 붙여주자 2. 종이와 펜으로 문제에 대해 추상화, 알고리즘을 제대로 세운 후 코딩을 한다 dp[i][j][k] = (i에서 시작해서 k번 이동해 j에 도착했을때 최소 비용) 점화식은 여기에 쓰기가 어려워서 생략. 문제를 빨리 푸는 연습을 좀 해야겠다. #define imp -1 #include #include #include #include using namespace std; int n = 0; int w[16][16] = {0}; int dp[16][16][1
https://blog.naver.com/kks227/220785731077 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver.com 이 글을 보면서 풀은 문제. 보통 dfs를 스택으로 구현하면 top을 얻은 동시에 pop을 하는데, 이 문제에서는 정점이 싸이클을 돌고 있는지 확인 하기 위해 바로 pop하지 않고 싸이클이 다 끝나면 스택이 빌때까지 계속 pop해서 finished[st.pop()] = 1로 만들었다. 이미 방문한 정점은 다시 방문할 필요가 없고, 싸이클을 도는 중인(visited[i] == 1 , finished[i] == ..
벡터를 20개 만들어서 글자수에 맞게 번호를 넣는다. 20개의 벡터를 하나씩 돌면서 벡터 안에서 좋은 친구의 수를 계산한다. 여기서 처음엔 벡터 대신 큐를 써서 q[i]에서 하나씩 pop하여 새로운 큐에 넣고 새로운 큐에 있던 요소와 pop한 요소를 비교하여 좋은 친구의 수를 1씩 늘려가는 완전탐색을 사용했다. 나름대로 시간복잡도를 줄이기 위해 새로운 큐에 있는 요소와 q[i]에서 pop되는 요소의 차이가 k 초과면 새로운 큐에 있는 그 요소를 삭제하는 방법을 썼으나 시간초과가 발생했다. 알고리즘 분류를 봤더니 '슬라이딩 윈도우'라는게 있길래 찾아봤다. 덕분에 투포인터 알고리즘에 대해 배울 수 있었고 투포인터 알고리즘으로 q[i]에서의 좋은 친구의 수 계산을 해결했다. 내가 푼 방식은 배열,투포인터를 이..
기둥이 되는 것을 구하는건 되게 쉬웠다 하지만 기둥을 가지고 넓이를 구하는걸 2시간 걸려서 풀었다.. 그래도 득은 있었다고 생각함 소스코드 n = int(input()) ls = [] for i in range(n): ls.append(list(map(int,input().split()))) ls.sort(key=lambda x : x[0]) stack = [] for i in range(n): if len(stack) == 0: stack.append(ls[i]) elif stack[-1][1] saveA[1]: s+= saveA[1] * (saveA[0]-stack1[i][0]) saveA = stack1[i] elif stack1[i][1] == saveA[1]: pass else: pass bh ..
발상을 배웠다고 생각해야겠다 소스코드 n = int(input()) ls = [] for i in range(n): ls.append(int(input())) ls.append(0) maxS = 0 stack = [] for i in range(n+1): if len(stack) == 0 or ls[stack[-1]] = ls[i]: a = stack.pop() maxS = max(maxS, ls[a]*(i if len(stack) == 0 else i-stack[-1]-1)) stack.append(i) print(maxS)
후위표기식은 계산하기 매우 쉽다. 식을 앞에서부터 읽으면서 수가 나오면 push, 기호가 나오면 스택의 가장 위에있는 두 수를 pop해서 계산 소스코드 import string AtoZ = string.ascii_uppercase dict1 = {} n = int(input()) st = input() stack = [] for i in range(n): dict1.update({AtoZ[i]:int(input())}) for i in range(len(st)): if st[i].isalpha(): stack.append(dict1[st[i]]) else: b = stack.pop() a = stack.pop() if st[i] == '+': stack.append(a+b) elif st[i] == '-..
문제에 후위표기식으로 바꾸는 방법이 아주 잘 나와있다. 식에 나오는 문자는 원래의 중위표기식에서 나오는 순서와 후위표기식에서 나오는 순서가 똑같다. ex) a+(b+c)*d => abc+d*+ 여러 후위표기식으로 바뀌는 케이스를 직접 써보면서 스택으로 풀수있는 규칙을 찾을 수 있다 나중에 다시 한번 풀어볼 생각 소스코드 stack = [] st = input() for i in range(len(st)): if st[i] == '*' or st[i] == '/' or st[i] == '+' or st[i] == '-': if len(stack) == 0: stack.append(st[i]) elif stack[-1] == '(': stack.append(st[i]) elif (st[i] == '*' or..
보자마자 풀이가 바로 떠오름 이분탐색 문제는 답이 left인지, left-1인지,mid인지 직접 시도해봐야 알수있는듯 하다 소스코드 #define issnit() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL) #include #include #include #include using namespace std; vector homes; int main() { issnit(); int n,c; int midd; cin >> n >> c; for (int i = 0; i > x; homes.push_back(x); } sort(homes.begin(), homes.end()); int left = 1..