본문 바로가기

전체 글

 (339)
[방송대 알고리즘]해 탐사 알고리즘 해 탐사 알고리즘 되추적 알고리즘 DFS로 해를 찾아다니다가 앞쪽에 더 이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법 상태 공간 트리 주어진 입력으로 만들어 낼 수 있는 모든 후보해를 리프 노드로 갖는 트리 내부 노드는 각 후보해를 만들어 가는 부분 후보해를 나타냄 특징 다항 시간 알고리즘이 없지만 정확한 해를 구해야 하는 경우에 적용 저울 문제, 0-1 배낭 문제 → O(2^n) 시간 복잡도 분석과는 별개로 실제 동작 시 빠른 수행 결과를 보이는 경우가 많음 분기한정 알고리즘 최적화 문제에 대한 상태 공간 트리를 각 노드의 한정값을 이용하여 탐색 하는 방법 한정값: 현재 노드로 만들 수 있는 해의 상항이나 하한, 혹은 둘 다 한정값이 그 순간의 최적해보다 좋은 경우에만 탐색 후보로 보..
[방송대 알고리즘]근사 알고리즘 근사 알고리즘 1. 기본 개념 튜링 기계 컴퓨터의 이론적 모델 구성 요소 → 테이프, 기호, 헤드, 상태, 규칙 무한한 길이의 테이프, 유한한 개수의 기호와 상태, 상태와 기호에 따른 헤드의 동작을 정해둔 규칙 현재 상태와 읽은 기호에 따라 헤드가 테이프의 기호를 쓰거나 좌우로 이동 결정론적 튜링 기계 테이프의 위치를 바꾸거나 쓰인 기호를 바꿀 때 한 가지 상태로만 변경 가능 순차 처리 컴퓨터와 비슷 비결정론적 튜링 기계 하나 이상의 상태로 바뀔 수 있거나 혹은 바뀔 상태가 없을 수 있음 연산 결과가 상황에 따라 달라질 수 있는 연산을 수행 병럴 처리 컴퓨터와 비슷 다항 시간 알고리즘 알고리즘 수행 시간이 입력 크기 n에 대한 다항식으로 표현 O(1), O(logn), O(n^2) 등등.. O(2^n)같..
[방송대 알고리즘]탐색 알고리즘 탐색의 개념 여러 데이터 중에서 원하는 값을 가진 데이터를 찾는 것 데이터 형태 → 리스트, 트리, 그래프 등 순차탐색 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 배열의 연산 삽입 연산 n번째 인덱스에 내가 삽입하고 싶은 원소를 추가하고 배열의 크기를 1 증가시킴 삭제 연산 n번째 인덱스의 원소를 삭제하고, 마지막 원소를 삭제한 인덱스에 대입한 후 배열의 크기를 1 감소시킴 연결리스트의 연산 삽입 연산 원하는 데이터를 추가하고 포인터를 연결함 삭제 연산 원하는 데이터를 삭제하고 삭제된 앞 노드와 뒤 노드의 포인터를 연결함 성능분석 탐색 실패의 경우 → 항상 n번 비교 탐색 성공의 경우 → 최소 1번 ~ 최대 n번 비교 → 탐색의 성능은 O(n) ..
[Git] Git의 기초 2 - Pro git book, 2nd Edition 정리 2.3. 커밋 히스토리 조회하기 git log : Git의 히스토리를 조회하는 명령어 특별한 아규먼트 없이 git log 명령을 실행하면 저장소의 커밋 히스토리를 시간순으로 보여준다. 즉, 가장 최근의 커밋이 가장 먼저 나온다. 그리고 이어서 각 커밋의 SHA-1 체크섬, 저자 이름, 저자 이메일, 커밋한 날짜, 커밋 메시지를 보여준다. -p, --patch: 각 커밋의 diff를 보여줌 -(정수): 정수개만큼의 결과만 보여줌 --since : 시간을 기준으로 조건에 해당하는 결과만 보여줌. “2008-01-15”나 “2 years 1 day” 같은 다양한 옵션을 지원함 --stat : 각 커밋의 통계 정보를 조회, 어떤 파일이 수정되었는지, 얼마나 많은 파일이 변경되었는지, 얼마나 많은 라인을 추가하거..
운영체제 - 교착상태 정리 (방송통신대학교 운영체제) 교착상태 필요조건 상호배제 점유대기 비선점 환형대기 상호배제 프로세스들이 자원에 대한 배타적인 통제권을 요구 적어도 하나 이상의 자원은 공동 사용될 수 없음 즉, 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야 함 점유대기 프로세스가 이미 다른 자원을 할당받아 배타적으로 점유하고있는 상황에서 다른 프로세스가 점유하고 있는 자원이 해제되기를 기다리는 상호아 비선점 프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에 제거되지 않음 즉, 다른 프로세스에 의해서는 해제되지 않음 환형 대기 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기 자원할당 그래프 정점 V = P U R P: 프로세스 R: 자원 Q(p,r): 요구간선, p가 r을 요구함 S(..
인프런 Rookiss 유니티 Part3 : 유니티 엔진 완강 나름 현업자라 기초강의는 도움 안될거같아서 안보려고 했는데, 누가 노트정리 한거 보니까 상상 이상으로 알찬강의같아서 결제해서 들어보았다. 진짜 도움이 많이 됬다. 지금까지 State서버 붙이며 멀티플레이를 구현해본 경험이 없는데, 보통 유니티강의들도 이러한걸 전혀 고려하지 않고 진행되다 보니 관련 지식을 쌓을 기회가 없었다. 하지만 이분은 3편인 기초 강의부터 나중에 서버 연동할걸 생각해서 어떤 패턴으로 개발하면 좋을지 알려주시고, 그게 실제 현업의 개발에서도 도움이 되었다. 지금까지 본 유니티 기초 강의와 책 중에서 가장 실무에 도움이 되는 기초 내용들이 꾹꾹 담겨 있었으며, 혼자서는 배우기 어려운 노하우들이 가득 담긴 강의이다. 유니티를 사용하여 현업 개발자가 되고싶다면 꼭 이 강의를 들어보는걸 추천..
[Git] Git의 기초 1 - Pro git book, 2nd Edition 정리 2.1. Git 저장소 만들기 Git을 사용하는 방법을 알고 싶은데 한 챕터밖에 읽을 시간이 없다면 이번 챕터를 읽어야 한다. Git에서 자주 사용하는 명령어는 모두 2장에 등장한다. Git 저장소 만들기 아직 버전관리를 하지 않은 로컬 디렉토리 하나를 선택해서 Git 저장소를 적용하는 방법 다른 어딘가에서 Git 저장소를 Clone 하는 방법 기존 디렉토리를 Git으로 만들기 해당 디렉토리로 가서 명령어를 입력한다. 시스템마다 디렉토리 이동 명령어가 조금 다른 점을 주의하자. $ git init 이 명령은 .git 이라는 하위 디렉토리를 만든다. .git 디렉토리에는 저장소에 필요한 뼈대 파일이 들어 있다. 이 명령만으로는 아직 프로젝트의 어떤 파일도 관리하지 않는다. Git이 파일을 관리하게 하려면 ..
알고리즘 2018년도 기말 기출문제 풀이 - 방송대, 방송통신대학교 알고리즘 알고리즘 2018 1번. 교재 및 강의에서 다루어지지 않은 알고리즘 기하 알고리즘 정렬 알고리즘 - 버블, 선택, 삽입, 셸, 합병, 퀵, 힙, 계수, 기수 유전 알고리즘 - 외판원 문제의 근삿값 구하기 욕심쟁이 알고리즘 - 동전 거스름돈, 배낭, 최소신장트리, 최단경로, 작업스케줄링, 작업선택, 허프만 코딩 정답: 1번 2번. 주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은? 모든 명령은 컴퓨터에서 수행 가능해야 한다. 각 명령은 단순하고 명확해야 한다. 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다. 외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다. → 외부 입력이 반드시 존재할 필요는 없다. 정답 : 4번 3번. 최대 개수의 노..

티스토리툴바