다락방

백준 1191 트리 순회 트리 전위순회, 중위순회, 후위순회 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문 import sys n = int(sys.stdin.readline()) tree = {} for i in range(n): root, left, right = map(int,sys.stdin.readline().split()) tree[root] = [left, right] def preorder(root): if root != '.': print(root,end='') pr..

24.01.20 CSAPP 3.5- CSAPP 3.5 산술연산과 논리연산 각 인스트럭션 클래스는 네개의 서로 다른 크기의 데이터 연산을 갖는다. 연산들은 4개의 그룹으로 나누어진다. 유효주소 적재 단항(Unary) 이항(Binary) 쉬프트(Shift) 이항연산은 두개의 오퍼랜드를 가지는 반면, 단항연산은 한개의 오퍼랜드를 갖는다. 3.5.1 유효주소 적재(Load Effective Address) 유효주소 적재 인스트럭션 leaq는 실제로는 movq 인스트럭션의 변형이다. 메모리에서 레지스터로 읽어들이는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않는다. 이 인스트럭션의 첫번째 오퍼랜드는 일종의 메모리 참조처럼 보이지만, 가리키는 위치에서 읽기를 수행하는 대신에 유효주소를 목적지에 복사한다. ..

CSAPP 3.4 3.4 정보 접근하기 x86-64 주처리 장치 CPU는 64비트를 저장할 수 있는 범용 레지스터 16개를 보유한다 레지스터는 정수 데이터와 포인터를 저장하는데 사용한다. 인스트럭션들은 16개의 레지스터 하위 바이트들에 저장된 다양한 크기의 데이터에 대해 연산 할 수 있다. 바이트 수준 연산은 가장 덜 중요한 바이트에 대해 연산, 16비트 연산은 덜 중요한 2바이트, 32비트는 4바이트 , 64비트 연산은 레지스터 전체에 접근한다. 일반적인 프로그램에서 서로 다른 레지스터들은 서로 다른 목적으로 이용한다. 스택 포인터 %rsp는 런타임 스택 끝 부분을 가리키기 위해 사용된다. 일부 인스트럭션들은 특별히 이 레지스터를 읽고 쓴다. 다른 15개의 레지스터는 사용이 저금 더 자유롭다. 3.4...

벌써 1주가 또 지났다. 배운 것, 공부한 것은 많은 느낌이지만 내 것이 안됐다. 지식들이 머리속에서 붕 떠있다는 느낌이 든다. 빠르게 캐치해서 내 것으로 만들지않는다면 그대로 날아가지 않을까 생각한다. 조금 더 공부할 때 집중해서, 효율을 늘려봐야겠다. 시간은 이미 많이 투자하고 있으니 집중의 정도를 늘려 효율의 향상을 기대해보는게 맞지 않을까..? CSAPP 정보는 비트와 컨텍스트로 이루어진다. 모든 시스템 내부의 정보 - 디스크 파일, 메모리 상의 프로그램 , 데이터, 네트워크를 통해 전송되는 데이터는 - 비트들로 표시된다. 서로 다른 객체들을 구분하는 방법은 이를 바라보는 컨텍스트에 의해서 결정된다. 다른 컨텍스트에서는 동일한 일련의 바이트가 정수, 부동소수, 문자열 또는 기계어 명령을 의미 할 ..

24.01.17 분할정복, 병합정렬, 코어타임 코테가 바로 내일이여서 백준 문제를 많이 풀려고 노력했다. 쉽지않다. 흑흑.. Algorithm 분할정복(Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식 대표적인 예 퀵정렬 합병정렬 이진탐색 선택문제 고속 푸리에 변환 분할정복의 설계 Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. Divide를 제대로 나누면 Conquer 과정은 ..

피보나치 수열 피보나치 수열의 각 항에 있는 수들을 ‘피보나치 수(Fibonacci number)’ 라고 한다 Fn+2 =Fn+1 + Fn 퀵 정렬(QuickSort) def quick_sort(a = list): if len(a) pivot: greater_arr.append(i) else: equal_arr.append(i) return quick_sort(less_arr) + equal_arr + quick_sort(greater_arr) 여기서 피벗을 더 좋게 바꾸는 것도 도전해보자. 내일 화이트보드에 코드 구현 해보기 🎆 Python sys.stdin.readline() 쓰는 이유 input()이 느린 이유 input()은 매개변수로 prompt message를 받는다. (입력을 받기 전에 pr..

CSAPP 어셈블리 코드를 짤때 저급 인스트럭션을 명시해야 하는데, 대개의 경우 고급 언어가 제공하는 높은 수준의 추상화를 사용하는 것이 보다 더 생산적이고 안정적이다. 그렇다면 왜 WHY 기계어를 사용하고 공부할까? 컴파일러를 적절한 커맨드라인 인자와 함께 호출하면 컴파일러는 어셈블리 코드 형태의 파일로 출력을 생성한다. 이 코드를 이해하면 컴파일러의 최적화 성능을 알 수 있고, 코드에 내재된 비효율성을 분석할 수 있다. 프로그램이 얼마나 효율적으로 실행될지 이해하기 위해서 생성된 어셈블리 코드를 컴파일하고 분석해 보곤한다. 더욱이 고급언어에서 제공하는 추상화 계층 때문에 이해 가능한 프로그램의 런타임 동작이 감춰지는 경우도 종종 있다. 또 다른 예로 악성 프로그램이 시스템을 감염 시킬 수 있도록 프로..

python 구현 부분이 내가 너무 부족하다는 것을 알아버렸다. 매 문제를 풀 때마다 기본적인 함수를 검색하고, 찾아볼 수 없기 때문에 solved.ac 기초적인 문제로 함수에 익숙해 지도록 했다. Python Ascii ord(문자) - 아스키 코드를 반환 chr(숫자) - 숫자에 맞는 아스키 코드 반환 for문 역순 for(큰 수, 작은 수,-1) 백준 2420 파이썬 절대값 함수 abs() 2475 파이썬 제곱 x ** 2 2738 2중 for문을 이용해서 문제를 해결했다. 3003 띄어쓰기로 구분된 여러개의 숫자 5579 list.remove() 함수를 이용해서 풀었다. 10872 재귀함수 factorial def factorial(num): if num 0 , n! = nxn-1! 자신과 똑같은..

24.01.13 CSAPP 1.7 - 1끝 운영체제는 하드웨어를 관리한다. 운영체제는 하드웨어와 소프트웨어 사이 소프트웨어 계층. 응용프로그램이 하드웨어를 제어하려면 언제나 운영체제를 통해서 해야 한다. 운영체제의 2가지 목적 제멋대로 동작하는 응용 프로그램들이 하드웨어를 잘못 사용하는 것을 막기 위해서 응용프로그램들이 단순하고 균일한 매커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치를 조작할 수 있게 이러한 두 가지 목적을 추상화를 통해 달성한다. 추상화에 대해서 여러가지 글들을 봤는데, 그것들이 가져야 할 핵심적인 특징을 가지는 모델을 만드는 것, 어떤 복잡한 것들을 단순화 시켜 표현한 것. 이런 설명들이 많았다. 프로세스 프로그램이 최신 시스템에서 실행될 때 운영체제는 시스템에서 이 한 ..

24.01.12 정보는 비트와 컨텍스트로 이루어진다. 모든 시스템 내부의 정보 - 디스크 파일, 메모리상의 프로그램, 데이터, 네트워크를 통해 전송되는 데이터- 는 비트들로 표시된다. 서로 다른 객체들을 구분하는 방법은 이를 바라보는 컨텍스트에 의해서다. 다른 컨텍스트에서는 동일한 일련의 바이트가 정수, 부동소수, 문자열 또는 기계어 명령을 의미할 수 있다. 프로그램은 다른 프로그램에 의해 다른 형태로 번역된다. GCC 컴파일러 드라이버는 소스파일을 읽어서 실행파일로 번역한다. 번역은 4개의 단계를 거쳐서 실행된다. 이 네 단계를 실행하는 프로그램들(전처리기, 컴파일러 ,어셈블러, 링커)을 합쳐서 컴파일 시스템이라고 한다. 전처리 단계 : 전처리기(cpp)는 본래의 C프로그램을 #문자로 시작하는 디렉티브..