104%

여태 삼성 문제 4개를 풀었는데 4개 모두다 DFS문제다 삼성은 DFS를 정말 좋아하는듯 문제 풀이 먼저 1일에 있는 스케쥴을 선택한 경우 5일이 걸리므로 6일 부터 10일 사이에 있는 스케쥴을 그다음 스케쥴로 고를 수 있다.고를 수 있는 스케쥴의 모든 경우의 수 를 살펴보자.1일,6일,7일 -> 801일,6일,8일 -> 902,6,7일 -> 702,6,8->803,6,7->603,6,8->704,6,7,->504,6,8->605,6,7->405,6,8->506,7,8->307 -> 208 -> 30 위의 경우를 빼고는 스케쥴을 선택 할 수 없고 이 모든 경우의 수 중에서 가장 큰 이익을 얻을수 있는건 1일 6일 8일에 있는 스케쥴을 선택해서 총 90의 가치를 얻는 것이다. 이런식으로 모든 경우의 수를 ..

삼성 문제들은 DFS문제가 많은것 같다. 3문제를 풀었는데 모두다 DFS문제였음.. 보니까 실제 자기네 회사에 들어갈만한 알고리즘에 대한 문제를 내는것 같음 이 로봇 청소기 문제 같이 문제 내는 스타일이 실생활과 매우 밀접한 연관이 있음.이 알고리즘이 실제로 로봇 청소기 안에 알고리즘으로 들어갈듯함 풀이 방법로봇이 왼쪽으로 회전한다음 앞으로 갈수 있으면 그곳을 방문해서 그곳을 청소함.따라서 방문 순서를 상 좌 하 우 순서로 잡아서 탐색을 진행해 나가야 한다. 만약에 현재 내가 위쪽을 바라 보고 있는데, 위쪽, 왼쪽 아래쪽,오른쪽 모두 청소를 했거나 벽으로 막혀있는데, 처음 바라보고있던 위치인 위쪽의 반대편 방향 즉 아래쪽 방향으로 로봇이 문워크 하듯이 현재 바라보고있는 방향 그대로 유지한채 뒤로만 움직인..

쉬운 문제 같은데 부동 소수점 오차 때문에 한 15번 넘게 틀린거 같다.. double형 변수에 어떤 값을 넣을때 0.3이란 실수를 넣게 되면 0.300000000으로 정확하게 들어가는게 아니라 0.2999998888 또는 0.300000000001등과 같이 약간 오차가 있게 값이 들어가기 때문에 이것을 해결해주어야 한다. 0~1의 구간을 6개로 나눈다 했을때, 0

문제를 보면 알겠지만 수를 하나씩 추가해 가면서 모든 경우의 수에 대해 다 해봐야 되는 문제이다. 따라서DFS를 쓰면 해결할 수 있다. 위 처럼 수를 하나씩 추가해가면서 모든 경우의수에 대해서 DFS를 하면 되는데맨 마지막 깊이에서 최대값, 최소값을 구해야 하므로dfs를 해 나가면서 계속 기록해야 하는 정보는 트리의 깊이, 현재 깊이 까지의 누적값, + - * / 연산자의 남은 횟수이렇게 3가지 이다. 배열의 경우 call by value로 매개변수를 전달해야 각 DFS흐름별로 연산자의 남은 횟수가 기록이 되는데 그냥 전달할 경우 call by reference로 전달 되기 때문에 연산자의 남은 개수가 저장된 op에 담긴 정보들을 임시배열인 tempop에 옮겨 담고 나서 다음 깊이로 이동하게끔 만들었다...

DFS를 활용하는 약간은 응용된 문제 그냥 단순히 바이러스인 2를 퍼트리는것 자체는 별로 어렵지 않다. 그냥 DFS혹은 BFS를 사용하면 된다.하지만 기둥인 1을 3개 세워야 하기 때문에 좀 생각을 해야 한다. 기둥을 3곳에 세워야 하는데 이거는 그냥 모든 경우의수를 다 해 보는 수 밖에 없다. 따라서 처음에 입력을 받을때 0인곳의 위치를 벡터에 넣어 놓고 나중에 그 벡터에 있는 값중 3개를 차례차례 중복되지 않게 꺼낸 다음그 세곳에 기둥을 세워 놓고 나서 DFS를 돌린다. DFS를 돌리면 바이러스가 퍼질것이고(2) 그리고 나서 안전 영역의 수를 카운트 하며, 안전 영역 크기의 최대값을 갱신한다. 위의 과정을 벡터에 있는 모든 0의 3개 조합에 대해서 전부 수행했을때의 안전영역의 최대값이 정답이 된다. ..

풀이 및 해설https://docs.google.com/document/d/1tY1X9U63XZ4EF7VQIjWltnzFvgo3bsyQriNdN2cCzRY/edit?usp=sharing

예전에 풀었던 문제인데 O(n2)방식이 아닌 O(NLOGN)방식으로 다시 풀어봤다. 벡터에는 최장 길이 부분 수열이 만들어 진다. 값이 들어있는 배열을 처음부터 끝까지 반복해 가면서 현재 인덱스의 원소가 벡터안에 어느 위치에 들어가야 하는지를 찾아서 그곳에 값을 넣어주는 방식이다. 자세한 내용은 아래 링크에 있으니 먼저 문서를 보고 나서 코드를 보면 이해가 갈것이다.클릭 1234567891011121314151617181920212223242526272829303132333435363738#include #include using namespace std; vector vt;vector::iterator it;int arr[1000]; vector::iterator find(int x){ for(it=v..

802.11의 로밍기능은 이동전화망에서의 로밍과 차원이 다른 더 좁은 범위의 로밍이다.같은 ESS에 속한 다른 AP에게 Reassociation요청을 주고 받음으로써 커넥션 재설정을 하고 연결이 끊기지 않게 한다. 지하철 타고 가다보면 알아서 연결이 끊겼다 연결됬다 반복한다. 802.11의 PHY는 모듈레이션에 따라 1~2Mbps밖에 지원되지 않았지만802.11b에서는 5,11mbps까지 전송속도를 높였다.(모듈레이션 변경) 맥 레이어는 그대로 사용하고 PHY레이어의 모듈레이션 기법만 재정의해서 높은 속도를 낸다. Physical Layer의 헤더인 PHY 포맷에서 헤더는 무조건 최저속도인 1mbps로 전송되지만 payload부분이 더 높은 전송속도로 전송된다.이때 헤더가 큰 오버헤드로 작용할수 있다고 ..