13458 Samsung sw test 알고리즘 1. 오직 1명은 무조건 1명 있어야한다는 말 2. 총감독관이 감시할 수 있는 응시자 수만큼 빼고, 감독관 수 1명 늘린다음에, 넣어야하는 부감독관 수를 더함. -> 이를 모든 시험장에 적용 3. 이때 총 필요한 감독관을 저장하는 변수는 long long으로 해야함(응시자 수 100만명, 시험장...

1339 단어 수학 알고리즘(브루트포스, 그리디) - 브루트포스 1. 어떤 알파벳이 나왔는지 기록하고, 거기에 맞춰 알파벳의 종류의 개수만큼 모든 가능한 수를 뽑아 검사한다. - 그리디 1. 들어오는 단어를 알파벳 단위로 분류하고 다음처럼 자릿수를 곱해준다. ABC -> 100A + 10B + C BCA -> 100B + 10...

12969 ABC 알고리즘(dp) 1. 현재 깊이 d, 이전에 나왔던 a의 개수, 이전에 나왔던 b의 개수, 이제까지의 k 수를 기준으로 dp를 만들어야함. k도 결과에 영향을 주기 때문. 2. 즉, dp[d][a][b][k] 를 선언하고, 이 상태가 검사되면 true로 지정하여 다시 검사하지않음. 3. 정답을 찾았을 때는 전역변수 got에 tru...

12849 본대산책 알고리즘(DP) 1. a라는 건물에 x분을 남기고 들어가는 것은, a에 연결된 모든 건물 b에 x+1분을 남기고 들어온 것과 같음 2. 즉, 정보과학관에 0분을 남기고 들어오는 것을 시작으로 모든 경우를 탐색하면 된다. 3. 쭉쭉 내려가다가 D분에 도달했을때, 장소가 정보과학관이면 1, 아니면 0을 리턴하여 바텀업으로 함 4. ...

1248 맞춰봐 알고리즘 (백트래킹) 1. 그냥 앞에서부터 가능한 수를 채워나가는 백트래킹 방식을 사용하면 된다. 2. 이때, 가능한 수는 ans를 채워간다는 얘기다. 즉, 가능한 경우만을 탐색하여 가서 정답만을 하나하나 채워가는 식으로 모든 경우를 탐색하면 됨. 코드 #include <bits/stdc++.h> using nam...

12100 Samsung sw test 알고리즘(DFS 재귀) 1. 위, 오른쪽, 아래, 왼쪽으로 차례로 보냄. 보낼때, 보내는 쪽에 가까운 곳부터 하나씩 검사. 2. 주의 사항 : 2 4 8 2 8 16 4 2 32 에서 위로 한번 보내면 맨 왼쪽 맨 위는 4가 되야하고 그 밑에 4가 와야함. 하지만 내가 처음 짠 코드에서는 한번 업데이...

1202 Jewelry thief 알고리즘 1. 보석을 가치순으로 내림차순으로 정렬 2. 가방을 multiset에 저장함 3. 가치가 큰 보석부터 차례대로 꺼내면서 적절한 가방을 선택하고, 집어넣음 -적절한 가방 : 무게가 같으면 가장 적절. 같지 않으면 남는 무게가 가장 적은 가방 -찾는 법 1. 같은 게 있는지 확인 2. 없으면, 현...

1197 MST 알고리즘(크루스칼 알고리즘 사용) 1. 가장 가중차가 작은 간선부터 검사 2. 사이클 검사 1. 간선의 양단이 전부 이미 안들어갔으면 양단을 같은 벡터에 집어넣고, set 벡터에 집어넣음 2. 한쪽만 들어갔다면, 들어가 있는 한쪽의 set벡터에 안들어간 쪽을 집어넣음 3. 두개 다 들어가 있고, 들어간 집합이 같다면, 사이클 ...

1167 트리의 지름 알고리즘 (dfs, dp) 1. 1번 노드를 최상위 노드라고 가정하고 품 2. 1번 노드부터 시작하여 트리를 밑으로 탐색함. 3. 끝까지 닿으면, 거리를 올리면서(bottom-top) 다시 위로 올라감(재귀로 탐색하면 됨) 4. 한 노드에서 재귀로 반환하는 건, 자신의 자식 노드에서 올라오는 것중 가장 큰 값(끝까지 갔을 때의...

11657 타임머신 알고리즘(밸만포드) 1. 밸만포드로 푼다. 2. 길이는 long long으로 저장한다. 코드 #include <bits/stdc++.h> using namespace std; struct Road { int to; int time; }; struct City { vector<Road> next...