[PY] <!> 11049 : 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049그냥 DP인줄 알았는데행렬 곱 최소 비용 문제는구간 범위쪼개서 비교를 하고최소비용을 계속 갱신해나가는 것이 핵심이다.자를 수 있는 한 최대한 범위를 자르고, 작은 해부터 최적의 해를 알아가는 것인데,해외 검색 키워드로는 Matrix Chain Multiplication 이 있다. 아무 곳에서 잘라서, 왼쪽 오른쪽 그룹을 고려하게 되면 그룹이 더 나눠질 수 없는 상황까지 줄인 다음, 거기서부터 값을 채워나가는 형태를 생각하게 된다. 이게 전형적인 Bottom Up방식으로 피티 지는 설명한다.dp[i][j] = min( dp[i][k] + dp[k+1][j] + (i~k 행렬) * (k+1~j 행렬) 곱셈비용) for 모든 k in [..

• format_list_bulleted 문제풀이
• · 2025. 4. 9.

[CS:APP] Chap 3.10 - 11

3.10 기계수준 프로그램에서 제어와 데이터의 결합지금까지 머신코드가 프로그램 제어를 구현한 방법, 서로 다른 자료구조가 구현되는 방법을 보았다.이곳에서, 가장 C 프로그래밍 에서 심오한 데이터와 자료가 상호작용하는 방식을 볼 것이다.3.10.1 포인터 이해하기포인터는 C의 핵심 특징이다. 이들은 다른 자료구조 내 원소들에 대한 참조를 생성하는 통일된 방법으로서의 역할을 수행한다.포인터는 초보들에게 혼란의 원인이지만, 그 아래에 깔려 있는 개념은 매우 간단하다.[continue ..]포인터는 연관된 자료형을 갖는다.이 자료형은 어떤 종류의 객체를 이 포인터가 가리키는가를 의미한다. 다음과 같은 포인터 선언을 예제로 사용하겠다.int *ip;char **cpp;변수 ip는 int형 객체의 포인터이지만, c..

• format_list_bulleted 컴퓨터 이론/CS:APP
• · 2025. 4. 9.

한 템포 끊기

꾸역꾸역이라는 말을 참 안좋아하는데 여긴 매일이 꾸역꾸역이다. 심지어 검산같이 cross checking 을 모든 부분에 할 여유조차 없다.그리고 학습 분위기 조성이라는 말이라는게 굉장히 무서운 단어로 느껴진다. 우리의 무의식은 놀고싶어도 의식적으로 그러한 마음을 꾹꾹 누르고 있지 않은가. 모두가 이런 가면을 쓰고 공부를 하려는게 기특하다가도 얼마나 고생스러운가 생각이 든다. 그러니 가면을 쓴 김에 좀 더 뺑이를 쳐보도록 하자.쓰러지지 않을 정도와 너무 게으른 그 사이 어딘가의 영역을 잘 저울질 하는게 꾸준함을 꾸준하게 하는 내용이라는데, 우린 우리 자신에게 좀 더 노골적으로 묻자. 진짜 누울만할 정도로 한걸까?난 잠은 죽어서 자자도 싫고, 밥 퍼먹는 와중에 공부하는 것도 싫다.잠도 포기한 삶의 질에서 ..

• format_list_bulleted 별 잡다
• · 2025. 4. 9.

[CS:APP] Chap 3.7 - 9

3.7 프로시저프로시저 호출은 소프트웨어에서의 주요 추상화이다. 이들은 지정된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공한다.이 함수는 프로그램의 여러 지점으로부터 호출 될 수 있게 된다.[우] 즉, 함수는 프로그램 안에서 어디서든 호출 될 수 있는 ‘독립적인 코드 덩어리’ 이다.잘 설계된 소프트웨어는 무슨 값이 계산되고, 이 프로시저가 프로그램 상태에 무슨 효과를 갖는지에 대한 명쾌하고 간결한 인터페이스 정의를 제공하는 한편, 일부 동작의 구체적인 구현은 감춰주는 방식이다.이런 식으로 추상화 메커니즘을 이용하며, 프로시저는 서로 다른 프로그래밍 언어에서 여러가지 다른 모습 : 함수, 메소드, 서브루틴, 핸들러 등으로 사용된다. 그러나 이 모두는 일반적인 특징들을 공유한다.[..

• format_list_bulleted 컴퓨터 이론/CS:APP
• · 2025. 4. 9.

[CS:APP] Chap 3.4 - 6

3.4 정보 접근하기일반적인 PC의 CPU는 64비트 값을 저장 할 수 있는 16개의 범용 레지스터를 가지고 있다.인텔의 첫번째 CPU 였던 8086 에선 8개, 32비트인 IA32에서도 8개. 64비트에서 와서야 이 레지스터 갯수가 늘어난 것이다.이들 레지스터는 정수 데이터와 포인터를 저장하는 데 사용한다. 아래 설명 할 그림은 이 레지스터들을 보여준다.이름은 모두 %r 로 시작하지만, 인스트럭션 집합의 역사로 인해 여러 개의 명명법이 존재한다.원조 CPU 8086에서 레지스터들은 %ax ~ %sp 까지, 16비트 레지스터를 가지고 있었다.IA32 (32-bit)로 확장하면서 이 레지스터들은 %eax ~ %esp까지 이름을 붙였다.64bit로 확장하면서 본래 8개의 레지스터들은 %rax ~ %rsp까지..

• format_list_bulleted 컴퓨터 이론/CS:APP
• · 2025. 4. 9.

[CS:APP] Chap 3.1 - 3

컴퓨터는 데이터를 처리하고, 메모리를 관리하고, 저장장치에 데이터를 읽거나 쓰는 다양한 행위들을 인코딩한 연속된 바이트인 기계어 코드를 실행함으로써 이루어진다.컴파일러는 프로그램 언어의 규칙, 대상 컴퓨터의 인스트럭션 집합, 운영체제의 관례 등에 따라 기계어 코드를 생성한다.GCC C 컴파일러는 기계어 코드를 문자로 표시한 어셈블리 코드의 형태로 출력을 만들어 프로그램의 각 인스트럭션을 만들어낸다. 그러고 나서, GCC는 어셈블러, 링커를 호출하여 어셈블리 코드로부터 실행 가능한 기계어 코드를 생성한다.개발 수단은 점점 고수준 언어화 되었다. 자바같은 자연어스러운 것으로 개발하는 것은 편리하다. 프로그램 에러를 검출하는데 상당한 도움이 되기도 한다.근데 우리가 기계어를 배워야 하는 이유가 있나?컴파일러가..

• format_list_bulleted 컴퓨터 이론/CS:APP
• · 2025. 4. 7.