문제https://www.acmicpc.net/problem/15686브루트 포스 문제...시간복잡도 때메 가져왔다. 풀이1. 백트래킹으로 모든 치킨집 경우의 수를 조합으로 구하기2. 구한 조합과 집 사이 거리를 모두계산해서 최소값 구하기  시간복잡도 : 최대 경우의수 : 17C7 = 1716 대충 2000최대 집수 : 100비교수 : 100 * 7 = 700700 * 2000 = 1400000통과는하지만 그렇게 빠르진 않다. #include using namespace std;#define X first#define Y second#define INF 1e9;int N,M;int answer = INF;vector > chicken;vector > chicken_temp;vector > house;vo..

문제https://www.acmicpc.net/problem/1463이전 포스트인 동전1,2를 풀며 비슷했던? 문제를 가져왔다.이것도 특정 값이 되는 최소의 경로를 찾는 문제이다.동전과 다른점은 배수가 된다는 점? 이다.  풀이1 DP이전 포스트 였던 동전2에서는 DP배열에 동전을 하나 하나 해봤다.그이유는 어떤 경로이든 상관없기때문, 하지만 이번엔 배수와 덧셈으로 전진하므로 그렇겐안된다.예를들어1 에서 (+1) (*2)1 에서 (*2) (+1) 은 그 결과값이 다르기때문이다. 경로가 달라지면 값도 바뀐다.따라서 한번의 값마다 3가지 방법을 통해 최단 경로를 갱신해준다.for(int i = 2 ; i   소스코드1 DP#include int n;int dp[1000005];using namespace s..

문제https://www.acmicpc.net/problem/2294 이전 포스트의 동전1과 같은 DP 문제, 이번엔 주어진 목표 금액과, 주어진 동전의 개수를 최소로했을때 몇갠지 세는 것이다.   풀이동전1과 달리 0원일때는 DP[0] = 0으로 초기화, 그리고 각 동전마다 DP배열에 1씩 추가하는 형태로 나아간다. 이때 DP배열이 추가하는 것보다 작으면 냅둬서 최소 개수를 구해나간다.이때 DP배열은 미리 최댓값INF을 대입해놔서, 만들어질 수 없는 값임을 초기화 시킨다.  #include using namespace std;const int INF = 10001;int n, k;vector coin;int dp[10001];int main(){ cin >> n >> k; int num; ..

문제https://www.acmicpc.net/problem/2293 동전1, 2로 두개 문제가 있는데 오랜만에 다시볼라니까 좀 헷갈려서 정리한다.참고로 9084번 동전 문제도 똑같은 문제이다. 풀이동전1의 경우 주어진 금액에 맞게 주어진 동전들을 이용해 만들 수 있는 경우의 수를 세는 것이다. 여기서 생각해봐야할 점은 문제에도 나와있듯사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우에는 동일한 경우의 수이다.4원을 만들때, 1,3원짜리 화폐가 있으면 1+3이나 3+1이나 동일하다는 것이다.이 두 경우를 다르게 본다면 DFS나 BFS를 이용할 수 있을 것이다. 여기선 동일한 경우로 따지기때문에, 1이 먼저오는 경우를 미리 판단한다고 생각한다. 그렇게한다면 DP배열의 1로가는 경우의 수를 먼저 대..

문제https://www.acmicpc.net/problem/1916 좀 까먹은 다익스트라를 다시해봤는데 헷갈리는 부분이 있어 정리한다.  풀이제목부터 다익스트라를 사용하는 문제.. 알고리즘을 모르면 풀 수 없으니 모르는 사람은 찾아보자.정리해놓은걸 보면서 풀었는데, 질문게시판에도 나랑 비슷한 사람이 있고, 나도 헷갈리는 부분이 있어 정리해보았다. while(!pq.empty()){ auto cur = pq.top(); pq.pop(); if(cur.X != board[cur.Y]) continue; for(auto nxt : edge[cur.Y]){ if(nxt.X + board[cur.Y] >= board[nxt.Y]) continue; pq.push({..

문제https://www.acmicpc.net/problem/14502오랜만에 알고리즘문제를 올려본다.다음주에 HSAT가 있어서 재활훈련중에, 저번 HSAT 모의고사에서 고생했던 느낌의 문제가 있어서 정리하려고 올려본다.  풀이시뮬레이션유형의 문제였는데, 보드 크기도 최대 8 * 8로 작았기 때문에 모든 벽의 경우의 수를 구하는 브루트 포스 방법이 생각났다.시간 복잡도에서는64칸의 보드에서 3개의 벽을 뽑는 방법 64 C 3 = 41664가 되고,해당 벽을 뽑았을때의 BFS시간 복잡도는잡도는 O((정점의 개수) + (간선의 개수) = 4 + 8 * 8이 된다. 64로 계산가능하다.그럼 41664 * 64로 2,666,496로 널널하게 된다.  처음 계산할때 BFS시간복잡도를 잘못계산해서 거의 딱 된다고 ..

[문제]https://www.codetree.ai/training-field/frequent-problems/problems/pacman/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai [설명]시간초과가 조금 무서웠던 문제... 벡터로 몬스터 구조체를 관리했는데, 죽은 몬스터들도 모두 넣었기에 순차탐색 * board크기시 시간초과 날 가능성이 있어보였다. 턴이 진행되는 동안 살아있는 몬스터의 수가 100만개가 넘는 입력은 주어지지 않는다고 가정해도 좋습니다. 지금 생각해도 위조건을 생각해도 죽은 몬스..

[문제] https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai [설명] 딱히 특이한점이 없는 문제...? - 한번에 나무가 번식함에 주의하여 빈배열을 따로 만들어서 해결 - for문 이내 while문으로 지정된 대각선 방향으로 계속 전진 - 제초제 기한 배열을 만들어 현재가 몇번째 년도인지 동기화시키고, 해당 년수때 제초제 제거 - 이전년도 문제로 갈수록 조금씩..

[문제] https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai [설명] 읽을때부터 좀 그랬는데 생각보다 까다로웠던 문제였다. 소용돌이로 가는건 해봤는데 돌아오는 건 또 안해봤구나...구현자체는 빨리했는데 예외처리할게 좀 많았다. 까다로웠던 것들은 - 0,0에 도착했을때 방향전환 후 처리과정 - 거꾸로 돌때는 두번째부터 이동거리 감소됨 (첫번째 아래로 갈때는 오른..

[문제] https://www.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai [설명] while문을 별로 쓸필요없이 조건마다 분기를 주면 되서 다른 문제보다 조금 쉬웠던것 같다. 문제를 풀며 잘못생각한점이 어차피 총을 버리고 가져갈때, 가장강한 총을 가져가기 때문에 board에 가장 강한 총만 표기하면 된다고 생각했는데, 그게 틀려서 조금 헤멨다. board에서 가장 강한총을..