처음에 원소의 개수가 20만을 넘지 않는다는걸 원소의 값이 20만이 넘지 않는다는걸로 착각해서 약간 삽질을 좀 했다. 이 문제를 풀려면 O(nlogn)방식을 사용해야 한다. 왜냐하면 원소의 개수가 20만개 까지가능하기 때문에 O(n^2)을 쓰면 시간초과가 난다. 이 문제를 풀면서 벡터에 push_back연산이 얼마나 느린지를 깨달았다.처음에 벡터를 통해서 문제를 풀었는데 똑같은 코드인데 벡터는 시간초과가 나고 배열로 풀었을땐 시간초과가 나지 않았다 내생각에는 입력을 받을때 벡터로 받게 되면 벡터는 연속적인 메모리 공간에 값을 나란히 저장하므로, 벡터가 처음에 할당한 크기를 넘어서는 입력이 들어오게 되면 메모리를 재 할당하기 때문에 굉장히 시간이 오래걸릴수 있는 연산이 바로 push_back연산이다. 우선..
다익스트라 알고리즘은 one to all 최단경로 알고리즘이다. 다시말해서, 하나의 정점에서 시작해서 다른 모든 정점까지의 최단경로를 구하기 위해 사용하는 알고리즘이다. 다익스트라 알고리즘은 모든 엣지중 하나라도 음의 가중치를 가지면 제대로 동작하지 않는다. 배열 2가지를 사용하는데1. 배열 d[i] => i번째 정점까지의 최단거리가 몇인지가 저장된다.2. 배열 visited[i] => i번째 정점을 방문 했는지 안했는지 여부가 저장된다. 알고리즘의 동작 순서는 다음과 같다.1. 배열 d[i]에 들어있는 값중 제일 작은값을 갖는 정점을 선택한다.2. 그 정점에 연결 되어 있는 정점들 중에 아직 방문하지 않은 정점을 포함하는 엣지에 대해서3. 릴렉스 연산을 한다. 릴렉스 연산이란, 두 정점 U,V가 있을때..
이 문제는 알고리즘 수업시간때 배웠던 최소 신장 트리를 구하는 알고리즘 2개(프림,크루스칼)중 하나를 이용해서 푸는 문제이다. 나는 크루스칼 알고리즘으로 풀었다. 크루스칼알고리즘의 시간 복잡도는 엣지의 개수가 E일때 O(ElogE)라고 한다. 왜냐면 엣지를 처음에 가중치가 낮은 순서대로 오름차순으로 정렬하는데, 이 정렬이 최소신장트리를 구하는 알고리즘에서 제일 오래걸리는 연산이기 때문이다. 이 문제를 풀기위해서는 분리-집합이라는 개념도 알아야 한다. 유튜브에 아주 좋은 강의(우리 교수보다 훨씬 잘가르치는듯)가 있으니 꼭 이걸 듣고나서 문제를 풀어 보길 바란다. 듣고나면 왜 코드가 이렇게 짜여졌는지 이해할수 있게 된다. https://www.youtube.com/watch?v=i4ZDgJS0_yMhttps..
재귀를 활용한 좋은 문제인것 같다. 정사각형을 정해진 순서대로 방문해야 하고 , 어떤 특정 점을 방문했을시 그 점이 몇번만에 방문된건지 출력하면 되는문제. 지금 현재 재귀 함수가 커버하는 사각형 영역을 식별하기 위해서 시작점(x,y)와 그 정사각형의 길이가 필요하다. 8*8에서 방문 순서를 보면처음에 8*8 정사각형의 Z 그다음 4*4 정사각형의 Z 4개 그다음 2*2 정사각형 16개 1*1 정사각형 64개 이런식으로 재귀호출 해야한다. DFS문제를 많이 풀다보니까 재귀호출에 대한 이해가 조금은 깊어진것 같다. 근데 단순히 주어진 순서대로 방문만 하는 경우 시간초과가 뜬다. 왜냐하면 정사각형이 최대 15*15의=225의 크기를 가질수 있으므로 엄청나게 많은 재귀 호출을 하게 될수 있다. 그렇기 때문에 현..
여태 삼성 문제 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문제였음.. 보니까 실제 자기네 회사에 들어갈만한 알고리즘에 대한 문제를 내는것 같음 이 로봇 청소기 문제 같이 문제 내는 스타일이 실생활과 매우 밀접한 연관이 있음.이 알고리즘이 실제로 로봇 청소기 안에 알고리즘으로 들어갈듯함 풀이 방법로봇이 왼쪽으로 회전한다음 앞으로 갈수 있으면 그곳을 방문해서 그곳을 청소함.따라서 방문 순서를 상 좌 하 우 순서로 잡아서 탐색을 진행해 나가야 한다. 만약에 현재 내가 위쪽을 바라 보고 있는데, 위쪽, 왼쪽 아래쪽,오른쪽 모두 청소를 했거나 벽으로 막혀있는데, 처음 바라보고있던 위치인 위쪽의 반대편 방향 즉 아래쪽 방향으로 로봇이 문워크 하듯이 현재 바라보고있는 방향 그대로 유지한채 뒤로만 움직인..
문제를 보면 알겠지만 수를 하나씩 추가해 가면서 모든 경우의 수에 대해 다 해봐야 되는 문제이다. 따라서DFS를 쓰면 해결할 수 있다. 위 처럼 수를 하나씩 추가해가면서 모든 경우의수에 대해서 DFS를 하면 되는데맨 마지막 깊이에서 최대값, 최소값을 구해야 하므로dfs를 해 나가면서 계속 기록해야 하는 정보는 트리의 깊이, 현재 깊이 까지의 누적값, + - * / 연산자의 남은 횟수이렇게 3가지 이다. 배열의 경우 call by value로 매개변수를 전달해야 각 DFS흐름별로 연산자의 남은 횟수가 기록이 되는데 그냥 전달할 경우 call by reference로 전달 되기 때문에 연산자의 남은 개수가 저장된 op에 담긴 정보들을 임시배열인 tempop에 옮겨 담고 나서 다음 깊이로 이동하게끔 만들었다...
- Total
- Today
- Yesterday
- return type
- es6
- useEffect
- webpack
- Polyfill
- computed
- reactdom
- javascript
- reflow
- Babel
- server side rendering
- rendering scope
- state
- react
- storybook
- mobx
- Action
- promise
- react hooks
- type alias
- reducer
- async
- props
- typescript
- await
- atomic design
- design system
- Next.js
- hydrate
- useRef
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |