Jonyo Programming

이 포스트는 「"Computer Organization and Design -The hardware / software interface" by Patterson and Hennessy, 5th edition, 2013.」을 참고하여 작성했습니다. Comparing Performance 성능의 기준은 무엇일까? 이전 강의에서 Respose time, Throughput 등 성능을 측정하는 기준에 대해 살펴봤다. 실제로 성능의 기준은 여러가지가 될 수 있지만 이번 강의에서는 오직 Response time을 기준으로 할 것이다. Response time 을 기준으로 성능을 살펴보았을 때 성능이 우수하다는 것은 결국 작업이 빨리 끝나는 것이다. 즉, 실행시간이 짧을 수록 성능은 높다고 말할 수 있다. 식으로 ..

이 포스트는 「Computer Networks: A System Approach , By L.Peterson , 5th, 2011」 을 참고하여 작성했습니다. What we will Learn? 통신의 개념 유무선 집적 연결 / LAN 패킷 네트워킹 인터넷 기초 호스트/단말 통신 시스템 네트워크를 보는 관점에는 세가지가 있다. 1. 네트워크 사용자 관점 : 통신 응용이 필요로 하는 서비스를 제작(이용)한다. 내부 동작원리에 대해 깊이 알 필요가 없다.(ex. 보낸 메시지가 오류 없이 정해진 시간 안에 전달되는 것을 원한다.) 2. 네트워크 설계자 관점 : 네트워크 자원들이 효율적으로 이용되며 각각의 사용자에게 공평하게 할당되도록 효율적인 설계를 해야 한다. 3. 네트워크 제공자 관점 : 네트워크 통신 장..

[BOJ 1202(G2) 리뷰] 상덕이에게는 가방이 K개가 있고 가방마다 담을 수 있는 무게가 다르다. 보석점에는 보석이 N개가 있고, 보석의 무게와 가격이 주어진다. 상덕이가 최대한 가격이 높은 보석들을 훔치려면 어떻게 해야 할까? 보석가격의 합이 최대가 되게하려면 다음과 같은 조건을 만족해야 한다. 가지고 있는 가방 K개를 다 사용해야 한다. 가방에 담을 수 있는 보석의 무게 중 가장 가격이 높은것을 훔쳐야 한다. 위와 같은 조건을 만족하며 보석을 훔치기 위해서는 먼저 가방의 무게를 오름차순으로 정렬해야 한다. 왜냐하면 가방에 담을 수 있는 무게가 높음에도 낮은 무게의 보석을 훔치게되면 낮은 무게를 담을 수 있는 가방이 가격이 높은 보석을 훔칠 수 없는 가능성이 생기기 때문이다. 예를들어 가방에 담을..

이 포스트는 「"Concepts of programming languages" by Sebesta, 10th edition.」 을 참고하여 작성했습니다. Chapter 1 주제 Reasons for studying Programming domains Launguage Evaluation Criteria Influences on Language Design Language Categories Language Design Trade-Offs Implementation Methods Programming Environments Reasons for Studying Concepts of Programming Languages 1. 아이디어를 표현하는 능력을 기르기 위해 2. 적절한 프로그래밍 언어 사용의 배경지..

[BOJ 1700(G2) 리뷰] 처음에 문제를 보고 '골드2 문제치고는 쉽네..?' 했지만 실제 구현하는 부분에서 엄청나게 애를 먹었다. 머리론 어떻게 하면 답이 나올지 알겠는데 그걸 코드로 옮기는 과정이 조금 복잡했다. 알고리즘은 그리디 알고리즘이다. 항상 최선의 선택을 해야 한다. 멀티탭이 비어있다면 비어있는 공간에 먼저 꼽아야 한다. 이미 해당 작업이 멀티탭에 꼽혀 있다면 그냥 사용하면 된다. 멀티탭은 꽉차있고 새로운 작업을 해야 할때는 가장 나중에 사용되는 작업의 코드를 뽑아야 한다. 위 세가지의 규칙을 만족하며 진행시키면 코드를 빼는 작업을 가장 최소로 만들 수 있다. 내가 애를 먹었던 부분은 가장 나중에 사용되는 작업을 고르는 과정이였다. set도 사용해보고, 배열하나 더 만들어서 해보고 별의..

[BOJ 1744(G4) 리뷰] 이 문제도 조건을 살펴보면 그리디 문제임을 알 수 있다. 엄밀한 증명은 못하겠지만, 우리는 수의 합이 최대가 나오도록 묶어야 한다는 점을 기억하자. 따라서 우리는 다음과 같은 조건을 항상 만족하게 해야 한다. 양수는 양수끼리 곱해야 한다. 음수는 음수끼리 곱해야 한다. 양수 중 최대한 큰 값 끼리 묶어야 한다. 음수 중 최대한 작은 값 끼리 묶어야 한다. 0은 음수랑만 곱해야 한다. -1,2,1,3 이라는 값이 존재할때 어떻게 묶어야 합이 최대가 나오게 할 수 있을까? 위 조건을 만족시킨다면 -1 + 1 + (2*3) 일때 최대값이 된다. 따라서 나는 입력을 받을때 음수의 값과 양수의 값을 구별하여 우선순위 큐를 통하여 정렬하여 저장했다. 그후 음수의 값은 가장 작은 값끼..

[BOJ 2457(G4) 리뷰] 전형적인 그리디 문제라지만 나에겐 너무 어려웠다 ㅠ.. 날짜를 저장하는 방식과 꽃을 선택하는 방식에 대해 이해는 했지만 막상 코드로 짜려니 막막했다. 알고리즘은 다음과 같다. 현재 날짜를 기준으로 현재 일보다 이전에 핀 꽃들중 가장 오랫동안 피는 꽃을 선택해야 한다. 공주는 3월1일부터 꽃이 피어있어야 한다 했으므로 3월1일을 기준으로 3월1일 이전에 핀 꽃들 중 가장 오랫동안 피는 꽃을 선택하면 된다. 예를들어 3월1일부터 6월3일까지 핀다면 다음 꽃은 6월3일 이전에 피는 꽃 중 가장 오랫동안 피는 꽃을 선택해야 한다. 위 알고리즘으로 11월 30일까지 꽃이 피어있도록 하고, 11월 30일이 지나면 반복문을 종료하고 정답을 출력하면 된다. 말로 설명하면 쉽지만 경계조건..

이 포스트는 「"Computer Organization and Design -The hardware / software interface" by Patterson and Hennessy, 5th edition, 2013.」 을 기반으로 작성했습니다. What we will learn? 어떻게 프로그램이 machine language로 번역되는지 (+ 어떻게 하드웨어는 프로그램을 실행하는지) Hardware / Software interface 프로그램 성능을 결정하는 요인 (+어떻게 성능향상을 할 것인가) 하드웨어 성능 향상의 요인 pipelining과 parallel processing 메모리가 어떻게 동작하는가 결과적으로 computer/CPU가 어떻게 동작하는지 컴퓨터 구조 강의를 통해 배우게 될 ..

[BOJ 2096(G4) 리뷰] 전형적인 DP문제처럼 보였으나 메모리 제한이 걸려있다. 가장 쉽게 풀기 위해서는 DP[3][100001]을 선언하며 각 위치에 대해 DP계산을 해주면 되지만 이렇게 하면 불필요한 메모리 공간때문에 메모리 초과를 맞게 된다. 따라서 우리는 계산 후 불필요한 데이터는 굳이 메모리에 저장하지 않도록 해야 한다. 그러기 위해서 입력받는 순간 MAX DP, MIN DP값을 계산하며 단계를 거듭할때마다 값을 복사하여 한정된 메모리를 통하여 DP계산이 가능하게 했다. 결국 실질적으로 사용하는 메모리는 MAXDP[2][3], MINDP[2][3]이 된다. /* 20.09.01 BOJ : 2096 내려가기 (https://www.acmicpc.net/problem/2096) 다이나믹 프로..

[BOJ 1937(G3) 리뷰] 이 문제는 내리막 길 문제와 굉장히 유사하다. 언뜻 보기에는 단순한 BFS,DFS문제로 보이지만 만약 모든 경우에 대해 탐색하려 한다면 당연히 시간초과가 날 것이다. 따라서 이 문제 역시 이미 팬더가 지나갔던 길에 대해서는 다시 탐색할 필요가 없게 해야 한다. 예를들어 아래와 같은 맵이 존재할때 14 9 12 10 1 11 5 4 7 15 2 13 6 13 16 8 (1,2)인 9가 존재하는 위치에서 팬더의 최대 생존일은 9->11->15 3일이다. 따라서 만약 다른 위치에서 (1,2)를 다시 방문하게 된다면 이미 그곳에서의 최대 생존일을 알고 있으므로 다시 한번 탐색을 진행하지 않아도 된다. 이를 DP배열을 통해 관리하면 된다. 위 로직을 이해 하고 코드를 본다면 바로 ..