혼종 꼬지마루

BFS에 올리긴 했지만, 다익스트라 문제 벽 부수고 이동하기와 같은 문제인 듯 하지만, 이동거리가 최소가 아닌, 벽을 최소로 부수는 것 1. visit배열을 선언해서 최대값으로 초기화 2. BFS탐색을 하면서 벽이 있는 것을 dis로 계산해서 이동위치가 최소가 되는 지점만 큐에 담는다 3. 도착위치에 있는 visit을 출력 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #define MX 102using namespace std; struct ALGO { int x, y;}q[MX*MX*MX]; int map[MX][MX], visit[MX][MX];int dx[] = { ..

이 문제는 저도 참고하고 풀었습니다 처음 접근은 크기가 40밖에 되지 않아서 정렬하고 구간으로 나누어 S가 되는 것을 카운팅 했으나 -10 3 10의 경우 S가 0일때 답은 1, 하지만 제가 푼 방법으로는 0이 나왔기에 잘못됬다는 것을 알았습니다. 이 문제를 해결하기 위해서 먼저 배열을 양쪽으로 나누어 나올 수 있는 모든 합의 경우의 수를 L, R로 나누어 저장 그리고 나서 L에서의 하나의 값과 R에서 나오는 값이 합이 S가 되는 갯수를 세어주면 됬습니다. 하지만 N = 40일 경우 각각 경우의 수가 1048575개 씩 나오기 때문에 모두 비교하기 보다는, 두개의 합이 S가 되는 시작점, S보다 커지는 시작점을 R에서 찾아서 그 위치의 차를 더해주었습니다. 12345678910111213141516171..

전형적인 DP문제 입력을 받으며 DP배열의 (r - 1, c), (r, c - 1), (r - 1, c - 1) 중 가장 큰값을 현재 입력되는 위치의 사탕개수를 더해주면 끝 123456789101112131415161718192021#include #define MXSIZE 1002#define MAX(X, Y) (X) > (Y) ? (X) : (Y)using namespace std; int map[MXSIZE][MXSIZE], dp[MXSIZE][MXSIZE];int N, M; int main(void){ cin >> N >> M; for (int i = 1; i map[i][j]; dp[i][j] = MAX(dp[i - 1][j - 1], MAX(dp[i - 1][j], dp[i][j - 1]));..

테트로미노를 두개 놓고 최대값을 구하는 문제 이 문제 그냥 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..