목록Algorithms (59)
혼종 꼬지마루
테트로미노를 두개 놓고 최대값을 구하는 문제 이 문제 그냥 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..
삼성 기출문제 퇴사랑 같은 문제지만, 범위가 넓어서 DP로 푸는게 맞음 그냥 퇴사문제는 범위가 좁아서 DFS로도 풀 수 있지만 이 문제는 범위가 1500000이나 되기 때문에 DFS로는 절대 풀 수 없다 DP를 처음 공부하고 퇴사, 퇴사2를 풀면서 마스터했다 1. 일을 하고 다음 날 돈을 받는 걸로 생각한다 ex. 3일 일하고 4일째 돈을 받는다. 따라서 N일까지 일을 한다고 가정할 때, N+1일날 돈을 받는다. 2. 오늘 부터 일을 할 때, map[i].day 이후, 즉 i + map[i].day 가 >N + 1일때는 일을 할 수 없으므로 continue; 3. i+map[i].day 되는 날 최대 값을 dp에 저장하고, 갱신하며 N + 1일까지 일을 한다. 123456789101112131415161..
최근 다녀온 삼성전자 DS SW직군 채용상담회에서 TREE와 Linked List문제 트랜트로 바뀌고 있다해서 많이 풀어보는 중 이 문제도 tree문제를 찾아서 풀던 중 기본부터 다지기 위해 시작하는 문제 일단 전위 순회로 입력되는 것을 EOF까지 입력받고, 이 데이터를 바탕으로 Tree를 역추적 그리고 후위 순회로 출력하며 동적할당된 노드를 삭제해주기만 하면 끝 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #include using namespace std; typedef ..
이 문제는 BFS에 넣어두긴 했지만 트리 구조를 인접행렬로 만드는게 더 중요한 문제 1. 입력되는 간선의 정보와 가중치를 map과 w배열을 만들어 저장 2. 트리의 마지막 노드에서 출발하는 것이 가장 큰 값을 나타내게 되기 때문에 map에서 갈 수 있는 정점의 수가 1개인 곳만 찾아서 bfs 탐색 결과적으로는 맞았지만 1832ms나 걸렸기 때문에 효율적이라고는 생각되지 않는코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #define MX 10002using namespace std; int map[MX][1000], w[MX][1000], q[MX];int N, dab; void bfs(i..
1. 구조체 배열로 입력을 받아서 부모노드를 기준으로 오름차순 정렬 2. 왼쪽, 오른쪽으로 구분하여 재귀호출로 트리 생성 3. pre, in, pos 순으로 순회하며 출력 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #include using namespace std; typedef struct NODE { char c; int end; NODE *L; NODE *R;}node; struct MAP { char c1, l, r;}map[30]; int N; bool co..
처음에 버릴 수 있는 부분이 있는걸 모르고 헤맸습니다... 말그대로 브루트 포스!! 1. 1~10000길이만큼 잘라서 얻을 수 있는 각각의 나무의 값을 tmp배열에 저장 2. 내림차순 정렬 3. 앞에서 부터 더하며 이전까지 더한 것이 지금값과 더했을때 보다 크다면 break 4. 최대값과 비교하여 갱신 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #define MX 1002 using namespace std; int arr[MX]; int N, C, W, dab, lim = 987654321; bo..
이 문제는 TRIE를 구현해서 모든 전화번호를 입력시킨 후, 하나하나 비교하면서 탐색주시면 됩니다. 전화번호 입력과 동시에 TRIE에 입력시켜 주고, 각 전화번호가 모두 포함되어 있다면 NO, 하나라도 포함되어 있지 않고 모두 다르다면 YES 이 문제를 풀면서 TRIE를 제대로 이해할 수 있었고, 구현까지 익힐 수 있었던 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 ..
블로그 시작하고 첫 포스팅... 요즘 TRIE에 빠져서 문제를 찾아서 풀어보는중에 좀 쉬운문제를 만났습니다 ㅎㅎ 이진트리를 구현하는거라 TRIE라고 하기도 뭐하고, 그냥 이분탐색과 재귀로 할 수 있는 문제지만 연습을 위해 트리를 구현해서 풀어보았습니다. 그냥 트리를 구현하면서, 각각 깊이에 도착할 때, 선언한 2차원 배열에 차례대로 각 깊이에 대한 숫자를 입력해놀고 탐색이 끝나면 출력하면 끝! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include #include #i..