목록Algorithms/DFS (10)
혼종 꼬지마루
삼성전자 상시테스트 문제와 상당히 유사하다고 해서 풀어보았는데..... 돌리는게 귀찮은 문제라고 결론을 내려본다 단순히 dfs로 돌리는 순서를 정해주면서, 최소값을 찾는 배열을 만들어 주느냐가 관건이다 항상 말하지만 나는 stl을 안쓰고 짜는 것을 선호하지만, 이 문제는 색종이 붙이기와 같이 dfs함수가 return되었을 때 map이 그 depth에서 만든 map으로 원복되는 것을 원하기 때문에 vector를 선언해서 사용했다 1. map을 선언하고, map을 rotation시키는 좌표를 입력받는다 2. dfs로 전체 탐색 하면서, 순서를 저장하는 것이 아닌, 그때마다 돌려준다.- 저장했다 한번에 돌려줘도 되지만, 비효율적이라고 생각이 들었기 때문 3. depth가 K에 이르면, 문제의 조건에 따른 각 ..
왜 됬지?라는 생각과 함께 풀었다......죽자고 예외잡고....hard coding하기 싫어서 이것저것 했는데 자꾸 안되니까 짜증나서 혹시나 하고 제대로 되는거도 hard coding으로 바꿔서 코드가 뭔가 길어졌지만....결론은 되는걸 올림....ㅂㄷㅂㄷ안되길래 에이씨.....하고 roll back시켰더니 통과된 희한한 문제였다 1. 간편하게 만들기 위해 1~9까지 적힌 map을 생성 2. L의 크기에 따라 pattern 순서를 입력 받으면서, 중복된 숫자가 있으면 바로 NO를 출력하고 종료 3. arr[0]의 좌표를 시작으로 dfs 탐색을 시작한다 4. 탐색 중, map[y][x]가 순서에 맞지는 않지만, 방문 했던 점이라면 그 진행방향으로 한번 더 이동시키고 dfs를 다시 던져준다. 방문하지 않았..
BFS로 풀려다가 메모리초과랑 런타임이 오지게 난 문제 원래 아이디어는 BFS로 탐색 후 도착하면 그 경로를 역추적하여 마킹하는 과정을 전부 돌아봐주는 방법 map과 큐, check와 경로를 저장하는 배열까지 만들었으니 메모리가 초과날만 한듯 DFS로 풀기 두려웠던 것은 시간초과가 날 것 같다는 생각에 BFS로 했던 것인데 메모리라니... 결국 DFS로 풀었다 1. 시작점을 돌면서 DFS 탐색 시작 2. 갈 수 있는 위치면 체크하고 들어간다 3. 도착했다면 리턴하며 1을 반환 12345678910111213141516171819202122232425262728293031323334#include #include #define MX 10005using namespace std; char map[MX][50..
문제를 잘못 이해해서 한번 틀린 문제... 무작위가 아닌, '한줄로 이어 붙였을 때 사전 순서'라는 점에 초점을 맞추면 그다음 부터는 쉬워진다 입력을 받으며 x인 부분은 구조체 배열로 그 위치를 담아주고, A~L인 부분은 check해준다. 그다음 부터는 한 위치씩, 모든 경우의 수를 넣어주고 끝까지 넣고 난 후 조건에 맞으면 flag를 달아주고 출력하면 끝 조건을 검사하는 부분에서 따로 머리써서 단순화 시키기 보다는 그냥 무식하게 인덱스로 다 찾아서 더해줬다...ㅎ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #define MX 60using name..
https://www.swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKpmwua-VoDFAUV(이 글이 문제가 될 시 삭제하도록 하겠습니다.) 과거 삼성전자 SW Test A형을 딸 때 1시간 만에 풀었는데 복원문제라는 소문 듣고 풀어봤다 아주 살짝 더 쉬운 문제인데... 더 오래걸린... 이제 코딩아이디어가 빠르게 안되나보다... 1. SAMSUNG 문자열을 target배열에 각 문자의 갯수를 저장한다. 2. 그리고 나서 L, 면접관 이름, 점수 P를 입력받는다. 3. 조합으로 dfs탐색 이때 중요한 것은 check배열에 면접관의 이름에 있는 문자의 갯수를 더하고 빼주며 검사한다 4. 매번 검사하며, targ..
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..
예전 삼성전자 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..
이 문제는 저도 참고하고 풀었습니다 처음 접근은 크기가 40밖에 되지 않아서 정렬하고 구간으로 나누어 S가 되는 것을 카운팅 했으나 -10 3 10의 경우 S가 0일때 답은 1, 하지만 제가 푼 방법으로는 0이 나왔기에 잘못됬다는 것을 알았습니다. 이 문제를 해결하기 위해서 먼저 배열을 양쪽으로 나누어 나올 수 있는 모든 합의 경우의 수를 L, R로 나누어 저장 그리고 나서 L에서의 하나의 값과 R에서 나오는 값이 합이 S가 되는 갯수를 세어주면 됬습니다. 하지만 N = 40일 경우 각각 경우의 수가 1048575개 씩 나오기 때문에 모두 비교하기 보다는, 두개의 합이 S가 되는 시작점, S보다 커지는 시작점을 R에서 찾아서 그 위치의 차를 더해주었습니다. 12345678910111213141516171..
테트로미노를 두개 놓고 최대값을 구하는 문제 이 문제 그냥 8개까지 놓고 생각하면 19*500*500*19*500*500의 시간이 걸린다...결론은 말도 안되는 범위 그렇기 때문에 먼저 한개를 놓았을 때 최대가 되는 걸 찾고, 그다음에 놓는 걸 생각하기로 했다 하지만 이렇게 하면, 문제가 되는게 max값이 같은것이 여러개일 경우 모두 따져 주지 못한다 그렇기 때문에 max값이 갱신될때 마다 그 위치를 구조체 배열을 선언해서 후보값들을 넣어준다 이렇게 되면 19*500*500 + 19*500*500*a까지 줄어들면서 문제를 해결할 수 있다 이렇게 해도 어마무시하게 시간이 걸릴 줄 알았는데 464ms로 생각보다 빠르게 구할 수 있었다 12345678910111213141516171819202122232425..
이 문제 역시 삼성기출로 나왔다는 문제 문제에서 주어진 테트로미노를 검사하고, 그 영역안에 값을 모두 더했을 때 최대값을 구하는 문제 인접한 4개를 고르는 것이기 때문에 dfs로 4개를 골라 검사해주면 끝 하지만, 주어진 테트로미노 중 ㅏ모양과 이를 회전시킨 ㅗ ㅓ ㅜ 까지 총 4개는 따로 검사해야 한다 1. dfs로 4개를 골라 최대값을 찾는다 2. 그 지점에서 ㅏ ㅗ ㅓ ㅜ 4개의 모양을 검사하여 최대값을 찾는다 1번 같은 경우는 사실 너무 정형화된 형태라 세부 코딩만 다르고 왠만하면 모두 똑같이 풀 수 있다 하지만 2번같은 경우는 사람마다 더 효율적인 코딩이 되도록 짤수도 있고, 그냥 나처럼 방향 모두 구하고 범위검사하고 해도 시간은 충분하다 1234567891011121314151617181920..