반응형 전공 관련21 백준 9663 이 문제는 정말 유명한 N-Queen 문제이다. 퀸은 양옆, 위아래, 대각선 방향 어디든 갈 수 있다. 따라서 한 행에 최대 하나의 퀸이 존재할 수 있다. 이때 N*N 크기의 체스판 위에서 N개의 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다. 만약 N = 8 이라면 위의 그림과 같이 배치할 수 있을 것이다. N-Queen 문제는 dfs, 백트래킹을 필요로 한다. 먼저 dfs를 위해 체스판을 표현할 배열이 필요하다. 퀸이 서로 공격할 수 없게 배치하려면 무조건 한 행에는 최대 한 개의 퀸만 존재할 수 있다. 그래서 a_row라는 배열을 만들었는데, 이 배열은 특정 행의 어느 열에 퀸이 위치하는지를 저장한다. 예를 들어 위 그림처럼 1행에서 6열에 퀸이 위치한다면 a_row[1] = 6.. 2021. 5. 2. 백준 2493 백준에서는 분류가 스택으로 되어있었는데 도저히 스택으로는 답이 보이지 않아서 다른 방식으로 풀었다. 1. data, res 라는 2개의 배열을 만든다. 2. data 배열에는 input값(탑들의 높이)을 저장한다. 3. res에는 해당 탑의 레이저를 송신받는 탑의 번호를 저장한다. res에 저장되는 탑의 번호는 0부터 시작한다고 가정하였다. 4. 현재 탑의 높이를 앞의 탑의 높이와 비교한다. 만약 앞의 탑의 높이가 더 낮다면 앞의 탑의 레이저를 송신받는 탑의 높이와 비교한다. 예를 들어, 6 10 5 6 7 11 8 이렇게 input이 들어온다면 6번째 탑의 높이는 8이므로 5번째 탑이 레이저 송신을 받을 것이다. 따라서 data[5] = 8, data[4] = 11, res[5] = 4 가 될 것이다... 2021. 4. 26. 백준 18115 이 문제는 deque을 사용하여 푸는 문제였다. 문제 풀이의 핵심은 주어진 input에 대해 역순으로 확인하며 deque에 카드번호를 집어넣는 것이다. 예를 들어 input이 5 2 2 1 3 2 1 이렇게 주어졌다면 1 → 2 → 3 → 1 → 2 → 2 순서로 값을 읽고, 각 숫자에 해당하는 과정을 해주면 된다. 카드 숫자는 1부터 N까지 수행을 할 때마다 1씩 증가한다. 1의 경우: 제일 앞에 카드가 들어가므로 deque.appendleft()를 사용해주었다. 2의 경우: 1. 앞에서 두 번째에 카드가 들어가야 하기 때문에 deque.popleft()를 이용하여 제일 앞의 카드를 빼네준다. 2. 카드를 deque.appendleft()를 이용해 넣는다. 3. 빼낸 카드를 deque.appendlef.. 2021. 4. 26. Routing Algorithm(라우팅 알고리즘) 라우팅 알고리즘 라우팅 알고리즘은 송신자로 부터 수신자까지 데이터를 전송할 때 라우터를 통과하는 최상의 경로를 선택하는 것이다. 우리가 고려해볼 요소는 비용, 속도, congestion이 있을 것이다. 비용은 어떻게 정의하냐에 따라 달라질 수 있다. 그러면 우리는 가장 빠르고, 가장 짧은 경로를 최상의 경로라고 생각할 수 있을 것이다. 즉, 거치는 라우터의 개수가 적거나, 아니면 라우터에서 발생하는 congestion이 적어서 빠르게 전송할 수 있는 경우를 말한다. 우리는 네트워크를 그래프로 표현할 수 있다. 여기서 v, w와 같은 node는 라우터가 되고, node끼리 연결한 것을 edge라고 한다. 각 엣지에는 비용이 적혀져 있다. 예를 들어 c(w,z)는 w와 z를 연결하는 엣지의 비용이므로 5가 .. 2020. 12. 8. 8. FSM Optimization 7장에서 FSM 설계하는 과정 중 state encoding 과정이 있었다. state 개수가 너무 많다면, state encoding 과정에서 많은 수의 bit를 state에 할당해야 할 것이다. 이 경우 equation도 길어지고, 복잡해질 것이다. 그래서 state minization을 통해 stae에 할당되는 bit 수를 줄일 수 있고, equation도 간단하게 만들 수 있으며 회로 구조도 간단하계 설계할 수 있는 것이다!! 이를 통해 필요한 gate, flip-flop의 수도 줄어들 것이고, 비용도 줄일 수 있다. 이러한 이유들 때문에 state minimization이 중요하다. 그렇다면 어떻게 state minimization을 할 수 있을까? 첫 번째로 해야 할 일은 equivalent한.. 2020. 12. 5. 7. FSM(유한 상태 기계) FSM(Finite State Machine) state, transition, clock 요소 고려하기.... FSM 구조 구하는 법 1. state diagram 구하기 2. state transition table(=truth table) 찾기 3. state encoding : state에 binary code를 부여하는 과정이다. 4. karnaugh map을 통해 minimize eqation 찾기 5. 회로 구성하기. : d flip-flop을 사용한다. state가 6개일 경우 3bit를 사용해서 binary code를 부여할 것이다. 이때 3bit binary code는 총 8개인데, 그러면 남은 2개는 어떻게 해줄 것인가? 우리는 모든 code를 사용해야 하기 때문에 이 2개에 대해서는.. 2020. 12. 5. 이전 1 2 3 4 다음 반응형
