다락방

시험 문제를 풀 때 너무 조급해서 막 접근했던 것 같다. 다음에 풀 때는 조금만 더 생각해서 하는게 오히려 시간을 줄일 수 있을 것같다. BFS DFS 문제에 대해서 잘 생각해보자 1388 import sys from collections import deque n,m = map(int,sys.stdin.readline().split()) floor = [] for i in range(n): floor.append(list(map(str,sys.stdin.readline().rstrip()))) visited = [[False for i in range(m)] for i in range(n)] cnt = 0 def bfs(x,y): q = deque() q.append((x,y)) dx = [0, 0, ..

2Week 24.01.19 - 24.01.24 회고 2주차가 다 끝나고 3주차가 바로 쉬지않고 시작됐다. 뭐랄까 난이도가 점점 올라가면서 쉴 틈 없이 몰아치는 기분. 크래프톤 정글보다 폭풍이라는 이름이 더 잘 어울릴 것 같다는 생각도 문득 문득 떠오른다. 하지만 많이 힘들었던 2주차 동안 정말 중요하다고 생각이 들었던 것이 동료학습에 관한 부분이 었다. 폭풍에서는 동료고 뭐고 다 날라가겠지만 정글에서 동료와 함께 라면 살아남을 수 있으니까 이름을 잘 짓긴 한 것 같다. 문제풀이에 적응되기 전에 계속 새로운 키워드가 나오고 그것에 또 적응하려니 많이 힘든 주간이었다. 하루 종일 문제와 답을 번갈아가며 보다가 하루가 끝나기도 하고, 그렇게 하루가 끝나면 내가 과연 오늘 무엇을 한 걸까? 잘했을까? 라며 자책..

CSAPP 3.9 이기종 (Heterogeneous) 자료구조 C는 서로 다른 유형의 객체를 연결해서 자료형을 만드는 두 가지 방법을 제공한다. Struct 키워드를 사용해서 선언하는 구조체는 다수의 객체를 하나의 단위로 연결한다. 키워드 union으로 선언하는 공용체는 하나의 객체를 여러개의 다른 자료형으로 참조 될 수 있도록 한다. 3.9.1 구조체 C struct 선언은 서로 다른 유형의 객체들을 하나의 객체로 묶어주는 자료구조를 생성한다. 하나의 구조체 내의 서로 다른 컴포넌트들은 이름을 이용해서 참조된다. 구조체의 구현은 구조체의 모든 컴포넌트들이 메모리의 연속된 영역에 저장되며, 구조체의 포인터가 첫번째 바이트의 주소라는 점에서 배열과 유사하다. 컴파일러는 각 필드의 바이트 오프셋을 가리키는 ..

CSAPP 3.8 배열의 할당과 접근 C에서 배열을 스칼라 데이터를 보다 큰 자료형으로 연계 시키는 수단이다. 한가지 특이한 점은 배열 원소들에 대한 포인터를 만들고 이들 포인터간에 연산을 할 수 있다는 점이다. 이것은 기계어에서 주소 계산으로 번역된다. 3.8.1 기본원리 자료형 T와 정수형 상수 N T A[N]; 시작하는 위치를 xA라고 표시했을 때, 이 선언은 두 가지 효과를 갖는다. 이것은 L*N 바이트의 연속적인 공간을 메모리에 할당하며, 여기서 L(바이트의 단위)은 자료형 T의 크기를 나타낸다. 새로운 식별자 A를 통해서 배열이 시작하는 위치의 포인터로 사용한다. 이 포인터의 값은 xA다. 배열의 각 원소는 0에서 N-1 사이의 정수형 인덱스를 사용해서 접근 가능하다. 배열의 원소 i는 xA ..

CSAPP 3.6.5 조건부 분기를 조건 제어로 구현하기 C에서 조건부 수식과 문장을 기계어 코드로 번역하는 가장 일반적인 방법은 조건부 및 무조건 점프를 함께 사용하는 것이다.(일부 조건문은 제어의 이동보다 데이터 이동으로 구현 할 수 있다.) GOTO문을 사용하는 것은 코드를 해독하고 디버깅하기 어렵게 할 수 있기 때문에 일반적으로 나쁜 프로그래밍 스타일이다. 3.6.6 조건부 이동으로 조건부 분기 구현하기 조건부 동작을 구현하는 전형적인 방법은 조건이 만족되면 프로그램의 한 가지 실행경로를 따르고, 아닌 경우에는 다른 경로를 따라가도록 하는 제어의 조건부 전환을 통해 이루어진다. 이 방법은 간단하고 일반적이지만 최신 프로세서들에서는 매우 비효율적일 수 있다. 또 다른 전략은 데이터 조건부 전송을 이..

백준 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 과정은 ..