혼종 꼬지마루

dp문제 중에 무조건 풀어야하는 기초문제인 것 같습니다. 한 열에서 스티커를 선택하지 않을 경우, 첫번째 행의 스티커를 선택할 경우, 두번째 행의 스티커를 선택할 경우로 나누어 이전 열에서 가장 큰 값을 더해주는 식으로 dp를 풀어주면 N번 연산으로 끝낼 수 있습니다. 12345678910111213141516171819202122232425262728293031#include #define SIZE 100003#define MAX(X, Y) ((X) > (Y) ? (X):(Y))using namespace std; int map[3][SIZE], dp[3][SIZE];int T, N; int main(void){ cin >> T; while (T--) { cin >> N; for (int i = 1; ..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4(문제가 될 시 삭제하도록 하겠습니다.) D5이긴 한데 그렇게 어렵지는 않았던문제... 그냥 문제를 잘 못 이해해서 좀 뻘짓했음 게다가 BFS라기도 뭐하고...시뮬레이션에 BFS조금 섞은 느낌 1. 상원이의 친구를 일단 큐에 넣으며 초대장을 나눠주는 갯수를 센다. 2. 큐에서 하나씩 빼며 그 친구의 친구를 중복되지 않도록 초대장을 나눠준다. 이때 큐에 다시 집어넣지 않도록 조심! 3. 초대장을 나눠준 갯수를 리턴 12345678910111213141516171819202122232425262728293031323334353637383..

dfs의 기본문제라고 생각된 문제 1. N/2로 팀을 나눈다 2. 2중포문으로 start팀과 link 팀의 능력치를 구하고, 차이의 최소값을 구한다 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #define MX 22#define INF 987654321#define ABS(X) (X) > 0? (X): -(X)using namespace std; bool check[MX];int map[MX][MX];int N, dab = INF; void dfs(int d, int pos){ if (d == N / 2) { int start, link; start = link = 0; for (in..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS(이 포스팅이 문제가 될 경우 삭제하도록 하겠습니다) 삼성 SW Test B형을 준비하면서 건드렸다가 TRIE라는 새로운 알고리즘을 공부하게 해준 문제 그냥 말그대로 TRIE를 구현하고, 조건의 문자열로 시작하는 문자열이 몇개가 되는지 반환하는 문제 다만, 문자열의 갯수를 저장하는 cnt배열을 각 노드안에 만들어서 각 문자열이 각 노드에서 몇번이나 중복되는지 검사 ex) ippp, ippx, ip와 같이 입력되고, ipp로 시작되는 것을 찾으라 할때,첫번째 노드에서 i 는 3개, 두번째 노드에서 p는 3개, 세번째 노드에서 p 는 2..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN(이 문제 포스팅이 문제가 될 시 삭제하겠습니다) 이 문제의 핵심은 '이 일을 하고 다음에 해야할 일'과 '이 일을 하기 위해서 이전에 해야할 일'로 나눠줘야 합니다. 이 두가지를 핵심으로 나눈다면, 그다음엔 간단한 BFS로 해결 가능! 즉, BFS+ 그래프 문제 입력을 받음과 동시에 '이 일을 하고 다음에 해야할 일'과 '이 일을 하기 위해서 이전에 해야할 일'을 그래프로 만들어 구분 일의 시작점에서는 '이 일을 하기 위해서 이전에 해야할 일'이 없으므로 이 지점을 모두 큐에 담아줍니다. 그리고 나서 큐에서 빠져 나올때 '일을 했다..

예전 삼성전자 SW Test A형을 딸 때 풀었던 문제랑 비슷해보여서 같은 방법으로 접근했다가 시간초과 났던 문제... 그래서 갯수에 상관없이 비트마스킹 + DFS를 사용하면 되는문제 순서에 상관이 없다는 말이 순서가 바껴도 같은 걸 사용하면 답의 갯수에 추가되는줄 알고 순열로 넣었다가 25!, 아니 예시인 9개에서도 시간초과 그래서 그냥 한 단어를 넣고, 안넣고 두가지 DFS로 문제 해결 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std; int check[12], visit[12];char A[102];int N, com;;long long dab; void dfs(i..

그냥 문제에 조건에 맞게 BFS만 잘 구현해주면 될 것 같았던 문제 하지만 visit을 체크하는 과정에서 통나무의 방향을 따로 체크해줘야 하기 때문에 3차원 check배열이 필요했다 그 외에는 문제의 조건에 맞게만 구현해주고, 3개를 한꺼번에 움직이는 것이 귀찮을 뿐 그냥 저냥 할만했던 문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114..

BFS를 총 4번던져서 풀수 있는 문제 이 문제도 stl을 사용하면 풀 수 없다고 생각 그리고....다시 풀어보라하면 절대 풀지 않을 문제.... 문제는 되게 간단해보이게 짧게 나오지만, 개인적으로 구현이 제대로 안되서 한 20번은 넘게 틀린 것 같다 1. 먼저 A를 연결 시켜본다. BFS를 던져서 두 점이 연결되는 지점이 오면 역추적해서 그 경로에 마킹 이때 B의 양 끝점은 비켜가도록 조심해야한다(이것 때문에 한 10번은 틀림...) 2. A의 연결점이 마킹되어 있는 상태에서 B를 BFS로 연결시킨다. 이 두개가 연결이 된다면, A의 최단길이, B의 최단길이를 더한다. 3. 위의 방법을 B->A순으로 한 번 더 해준다. 이렇게 총 2번의 연결을 통해 나온 답 중 최단의 것을 사용 연결할 수 없다면 IM..

이 문제는 bfs + 비트마스킹을 이용한 문제 다만, 열쇠를 찾았을때, 지나온 곳에 그 문이 있을때 어떻게 처리해줘야 할지가 가장 중요합니다 제가 사용한 방법은, 열쇠가 없는 문을 만났을 때 다른 구조체 배열에 위치와 문의 알파벳을 저장 열쇠를 찾는다면, 찾은 열쇠로 열 수 있는 문(열쇠가 없는 문을 저장해 구조체배열)을 찾아서 다시 큐에 담아줍니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #define MX 110using namespa..

BFS + 그래프를 이용하여 해결 가능 다시 풀기 싫은 문제... 다른방법이 있을지는 모르겠지만 개인적으로는 stl을 사용하여 Queue를 사용하면 못풀 것 같다는 생각이 드는 문제 배열을 2칸을 묶어서 1칸으로 쓰는 것도 중요하다 1. 입력을 받고, 배열 2칸을 1칸으로 만들어 문제와 똑같은 형태로 각 칸에 번호를 매긴다 2. 각 정점에서 문제 조건에 맞는 갈 수 있는 방향을 그래프로 만들어 준다. 3. 이 그래프를 시작으로 BFS탐색 시작! 4. 문제의 조건 중 '도착할 수 없다면 가장 큰 위치로 이동한다'이 조건을 위해 번호가 크다면 계속 갱신을 시켜주고, 이 경로를 추적하기 위해 큐에 들어가는 정보 중 이전 큐의 위치, 즉 탐색을 하는 위치의 큐넘버를 함께 담아준다 5. 문제의 조건에 맞게 출력!..