분류 전체보기

방학방학

드디어 학기가 끝났다..! 안드로이드 텀프도 잘 마무리되었고 시험도 모두 끝났다. 시스템소프트웨어는 bit연산이랑 어셈블리어 등을 처음배워서 많이 어려웠다. 솔직히 알고리즘, 자료구조가 어렵다고 하는데 나는 이 과목이 지금까지 들은 강의 중 제일 어려웠다. 그래도 이렇게 low level 프로그래밍을 언제 배울 수 있을까. 열심히 과제도 하고 공부했는데 시험은 잘 못본 느낌이다. 아쉽. 공선대는 그냥 집어 던졌다. 너무 어려워.. 제발 C0만 받을 수 있으면 좋겠다ㅋㅋ 컴퓨터 구조, 운영체제는 서로 공유하는 내용이 많아서 편했다. 하지만 하드웨어 부분을 이론위주로 다루는 컴퓨터 구조보다 실제 운영체제인 XV-6를 가지고 배운내용을 과제형식으로 실습할 수 있는 운영체제가 훨씬 재미있었다. 아직 블로그엔 C..

[백준 2162] 선분 그룹 C++

2162번: 선분 그룹 첫째 줄에 N(1≤N≤3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 www.acmicpc.net 선분 교차 알고리즘, Union-Find 1. 문제 해결 아이디어 [백준 17387] 선분 교차 2 C++ 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을.. hyeo-noo.tistory.com 위 문제에서 사용했던 선분 교차 알고리..

SystemSoftware - Cache Memory #3

SystemSoftware - Cache Memory #2 SystemSoftware - Cache Memory #1 cache memory에 대해서 알아보자 Locality Temporal locality(시간 지역성) : 최근에 접근했던 data나 명령이 가까운 미래에 다시 사용될 가능성이 높다. (마지막으로 사용된 시.. hyeo-noo.tistory.com Cache 최적화에 대해서 알아보자 miss rate : cache에 찾고자 하는 정보가 없는경우. 예를 들어 hit 상태일 때 cache에서 정보를 가져오는 경우 1Cycle이 걸린다고 하면, miss 상태라면 memory를 참조해서 정보를 가져오게 되고, 이 때 약 100Cycle걸린다. (단순 비교를 위한 cycle 수) 따라서 hit가 ..

[백준 1405] 미친 로봇 C++

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백트래킹 1. 문제 해결 아이디어 로봇이 최대 14번 움직이므로 14번 동안 자유롭게 움직일 수 있는 좌표 Map[32][32]를 설정해주었다. 초기 좌표를 적당한 중간 좌표로 잡아주고 백트래킹 dfs를 해준다. 움직일 때마다 확률을 곱해줘야 하므로 함수의 인자로 초기값 1을 가지는 확률 변수를 넘겨준다. 이동 중에 방문했던 곳을 다시 들리게 된다면 지금까지 곱해진 확률을 결과값에 더해준다. (단순하지 않을 때만 더해 줌) 결과는 단순한 경우를 찾으므로 1-..

[자료구조] Single Linked List 예제 코드 #2 (C)

Single Linked List 구현하기 #2 따로 list의 크기를 입력받는 상황은 구현하지 않고 정적으로 이미 만들어진 노드에서 circular list로 만들고 검색하는 기능을 구현했다. 구현을 위한 메서드들 struct Node : list의 한 노드를 구성하는 구조체 struct Node* Create(int data) : list의 새 노드를 만드는 함수 struct Node* Insert(struct Node* current, int data) : current 라는 노드 뒤에(after라는 노드 앞에) 노드를 새로 만들고 data값을 설정 후 노드를 반환하는 함수 void destroy(struct Node* destroy, struct Node* head) : head 노드부터 탐색해서..

[백준 6543] 그래프의 싱크 C++

6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net 강한 연결 요소 코사라주 알고리즘 1. 문제 해결 아이디어 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 이전에 포스팅 했던 문제에서 사..

[자료구조] Single Linked List 예제 코드#1 (C)

Single Linked List 구현하기 #1 list의 크기를 입력받고 순서대로 value를 입력받아 동적할당 받은 list노드를 서로 연결해서 linked list로 만들어주었다. 구현을 위한 메서드들 typedef sturct _intlinked : list의 한 노드를 구성하는 구조체 il* make_node() : list의 헤더를 만드는 함수 void add_node(il* head, int value) : head 노드 뒤에 value값을 가진 노드를 연결해주는 함수 void destroyall(il* head) : head 노드부터 시작해서 list의 끝까지 메모리를 해제해주는 함수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

[운영체제] Semaphore

운영체제의 병행성 기법 중 하나인 Semaphore에 대해서 알아보자 Semaphore는 정수 값을 가지는 객체라고 생각하면 된다. Sem_wait(), Sem_post()같이 Semaphore의 값을 조절하는 함수를 가지고 있다. 첫 번째 인자는 Semaphore객체, 두 번째 인자는 여러 개의 쓰레드에 의해서 공유되고 있다는 것을 의미, 세 번째 인자는 Semaphore값을 1로 초기화 하겠다는 뜻이다. Semaphore의 2가지 동작에 대해서 알아보자 sem_wait() Semaphore값을 1 감소시킨다. 값이 0 이상이라면 즉시 return 한다. 값이 음수가 된다면 wait상태에 들어가고, sem_post()가 호출될 때까지 wait 한다. 여러 개의 쓰레드가 sem_wait()을 호출한다면 ..

[백준 1708] 볼록 껍질 C++

1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net Convex hull jarvis march와 graham scan 알고리즘은 그림도 없고, 설명도 많이 부족하니 다른 분들의 글을 참고해주세요 코드는 determinant를 사용한 풀이입니다 1. 문제 해결 아이디어 Convex hull 문제를 해결하기 위한 대표적인 2가지 알고리즘에는 Jarvis march(gift wrapping) 알고리즘 Graham scan 알고리즘 위 2개가 있다. Jarvis march(gift wrapping)..

[컴퓨터 구조] Addressing Mode

[컴퓨터 구조] Instruction Set 컴퓨터의 Instruction set에 대해서 알아보자 Ex ) 3 + 6 = 9 Operands : '3', '6' Operator : '+' 명령어 사이클의 기본 상태 Diagram을 알아보자 Instruction fetch : 메모리에 있는 명령어를 가져오는 작업(Op.. hyeo-noo.tistory.com 명령어 set을 가져오기 위한 여러 주소 지정방식을 알아보자 Immediate mode : 명령어에 이미 operand가 있다. Register mode : 명령어에 operand가 있는 Register를 가리키는 게 있다. Direct memory mode : operand를 가진 메모리의 주소가 있다. Register indirect mode :..