Archive: 2018

2018
0
computer sciencealgorithms

백준[14864] - 줄서기

문제백준 14864 문제 보기 접근 방법문제를 손으로 적어보고 그대로 구현해보니깐 정답이 나왔다. 그래도 초반 몇번의 제출에서는 시간 초과가 나왔는데 벡터를 사용하는 대신 배열을 사용해서 시간 초과가 났다. 이유는 중간을 지웠을 경우 중간 인덱스서 부터 맨끝까지 한 칸씩 앞으로 땡겨야 했다.문제 접근은 처음 입력을 받으면서 나보다 뒤에 몇명이 작은 숫자를

0
project정리

13. 콘솔 셸을 만들자

들어가기셸을 구현하는데 필요한 콘솔 라이브러리를 구현하고 콘솔 라이브러리를 구성하는 함수를 구현하는데 필요한 가변 인자 처리 방법. 본론13.1 sprintf()와 가변 인자 처리13.1.1 포맷 스트링과 가변 인자// 가변 인자 예시 printf("%s", "test") 포맷 스트링에는 함수의 파라미터가 가변적이라는 전제가 포함. 함수를 호출하는 쪽에

0
project정리

12. 키보드 디바이스 드라이버를 업그레이드하자

들어가기데이터를 전달하는 큐를 구현해 인터럽트 핸들러에서 셸 코드로 키 정보를 전달. 본론12.1 인터럽트 핸들러와 큐12.1.1 인터럽트 핸들러와 어떻게 통신할까? 인터럽트 핸들러는 디바이스에서 읽은 데이터를 버퍼에 저장하고, 프로그램은 버퍼를 확인하여 이를 처리. 12.1.2 큐란 무엇인가? FIFO 구조의 자료구조. 12.1.3 범용 큐 설계 범용

0
project정리

11. PIC 컨트롤러와 인터럽트 핸들러를 이용해 인터럽트를 처리하자

들어가기PIC 컨트롤러로 인터럽트를 프로세서에 전달하고 실행 중이던 코드로의 복귀를 구현해보자. 본론11.1 PIC 컨트롤러 소개11.1.1 PIC 컨트롤러란 PIC 컨트롤러는 인터럽트 처리에 관련된 세부기능을 프로그래밍할 수 있는 컨트롤러. 마스터-슬레이브 방식으로 연결해 15개의 인터럽트를 처리. PIC 컨트롤러는 각각 8개의 핀으로 총 16개를 구성하

0
computer sciencealgorithms

백준[14863] - 서울에서 경산까지

문제백준 14863 문제 보기 접근 방법빠르게 틀을 만들어 놓고 이상한 곳에서 실수를 너무 많이했다. 문제 접근은 처음 도보와 자전거를 모두 dfs로 탐색한다. 하지만 이전에 진행했던 경로를 저장하지 않으면 시간복잡도는 O(2^n)으로 시간 초과를 유발한다. 따라서 이전에 지나갔던 노드라면 memo에서 꺼내어 여지껏 노드까지 온 거리를 더해서 리턴한다.하지

0
computer sciencealgorithms

백준[14697] - 방 배정하기

문제백준 14697 문제 보기 접근 방법처음에는 dfs로 문제를 접근하려했다. 하지만 dfs로 문제를 풀 경우 O(3^N)이라는 큰 시간복잡도를 보인다. 이를 해결하기 위해 복잡한 예외 처리 및 메모이제이션을 사용해야할 것 같아 다른 방법을 생각해 보았다. 결과적으로 브루스포스로 접근하면 O(N^3)으로 쉽게 해결할 수 있다. 코드 #include <i