Chapter 3 프로그램의 기계수준 표현 컴퓨터 : 데이터를 처리하고, 메모리를 관리하고, 저장장치에 데이터를 읽거나 쓰고, 네트워크를 통해 통신하는 등의 하위 동작들을 인코딩한 연속된 바이트인 기계어 코드(machinc code)를 실행한다. 컴파일러 : 프로그램 언어의 규칙, 대상 컴퓨터의 인스트럭션 집합, 운영체제의 관례 등에 따라 기계어 코드 생성 GCC C 컴파일러 : 기계어 코드를 문자로 표시한 어셈블리 코드의 형태로 출력을 만들어 프로그램의 각 인스트럭션 생성 GCC : 어셈블러와 링커 호출 => 어셈블리 코드로부터 실행 가능한 기계어 코드 생성 ...

개발 진행 및 완료 상황 3주차 python algorithm 난이도 중 이하 문제 풀이 완료 CSAPP 3.3 까지 공부 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 9084 동전(https://www.acmicpc.net/problem/9084) 풀이 과정 : j원을 만들 수 있는 경우의 수를 dp[j]라 한다면 동전의 한 종류인 i원을 더한 j+i원을 만드는 경우의 수도 dp[j+i]를 더함으로서 구할 수 있다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys ans = [] t = int(sys.stdin.readline()) for _ in range(t): n = int(sys.stdin.readline()) coin = list(map(int,sys.stdin.readline().split())) m = int(sys.stdin.readline()) dp = [0] * 10001 dp[0] = 1 for i in coin: for j in range(1,m+1): if j-i >= 0: dp[j] += dp[j-i] ans.append(dp[m]) print(*ans, sep='\n') 출처 : ...

2023-03-27 습관 이 곳에 온지 한 달이 된 날이다. 어느덧 파이썬 알고리즘은 마지막 주차에 들어섰다. 잘해왔다 라고 말하기는 많이 부족하다. 그래도 조금씩 더 나아지고 있는 모습을 스스로에게 찾을 수 있는 건 참 다행이라는 생각이 들었다. 저번 달의 나와 비교하면 참 많은것이 변했다. 이제 남들의 말을 조금은 더 잘 알아들을 수 있게 되었다. 생소한 단어 투성이였던 주변 사람들의 대화는 이제 무슨 이야기인지는 알겠다. 물론 그 개념을 완벽하게 이해하고 있는 것은 또 다른 얘기긴 하지만 말이다. 최선의, 최단의 ...

삽입 정렬 : 점진적인 방법 사용 원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입 2.3.1 분할정복 접근법 재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다. 분할정복의 3단계 ...

2.2 알고리즘의 분석 알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 메모리, 통신 대역, 하드웨어 등 대부분은 계산 시간을 의미한다. 이 책에서의 가정 알고리즘은 단일 프로세서와 랜덤 접근 기계(RAM, random-access machine) 모델로 가정 : 명령어는 동시X, 하나씩 실행 산술 연산, 데이터 이동연산, 제어 연산 등 : 상수 시간 RAM 모델의 데이터형 : 정수(integer)와 부동소수(floating point) 각 워드 크기에 제한을 가정 : 입력 크기가 n인 입력을 다룰 때 정수는 상수 c>= 1에 대해 clg2비트로 표현된다고 가정(워드는 상수로 처리하므로 너무 크면 안된다.) ...

2.1 삽입정렬 정렬문제 입력 : n개 수들의 수열 $$ <a_1, a_2, …, a_n> $$ 출력 : $$ a’_1 <= a’_2 <= … <= a’_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a’_1,a’_2, …, a’_n> $$ 정렬하고자 하는 숫자를 키라고 한다. 의사코드와 “실제” 프로그램 코드의 차이는, 의사 코드에서는 알고리즘을 가장 분명하고 간결하게 서술할 수 있다면 어떤 표현 방법을 사용해도 좋음. 영어, 한글 문장등이 들어갈 수 도 있음. 데이터 추상화, 모듈화, 오류처리 등의 소프트웨어 공학 관점의 문제를 고려하지 않음. ...

1.개발 진행 및 완료상황 2주차 python algorithm 문제풀이 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2252 2252번: 줄 세우기 2252번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 줄 세우기 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 37709 21883 14481 56.278% 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, … ...

1.1 알고리즘 알고리즘 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차 어떤 입력을 어떤 출력으로 변환하는 일련의 계산과정 잘 정의된 계산 문제를 풀기 위한 도구 정렬 문제 입력 : n개 수들의 수열 $$ <a_1,a_2, …, a_n> $$ 출력 : $$ a^{’}_1≤a^{’}_2≤ …≤a^{’}_n $$ 을 만족하는 입력 수열의 순열(재배치) $$ <a^{’}_1, a^{’}_2, …, a^{’}_n> $$ ex) <31, 41, 59, 26, 41, 58>이 입력 수열로 주어지면 정렬 알고리즘은 수열 <26, 31, 41, 41, 58, 59>를 출력한다. -> 입력수열 : 정렬 문제의 사례 ...

1.2 기술로서의 알고리즘 컴퓨터는 상당히 빠를 수 있지만 ‘무한히’ 빠를수는 없다. 메모리도 매우 저렴할 수 있지만 비용이 ’전혀‘ 들지 않을 수는 없다. 효율성 동일한 문제 해결을 위한 알고리즘이 효율성 면에서 극적으로 다를 수 있다. 하드웨어, 소프트웨어로 인한 차이보다 더 심각할 수 있다. ex) 삽입 정렬 : n개의 값 정렬위해 $$ c_1n^2 $$ 에 비례하는 시간 걸림(c_1은 n에 독립인 상수). 즉, n^2에 비례함 병합 정렬 : $$ c_2nlog_2n $$ 의 시간 걸림(c2는 n에 독립인 또 다른 상수). 즉, nlog_2(n) 상수는 입력 크기 n에 비해 수행시간에 영향을 훨씬 작게 준다. ...

1.1 정보는 **비트****와** **컨텍스트****로 이루어진다.** 비트(Bit) : binary digit의 준말. 0과 1로 이루어진 가공된 데이터(정보)의 최소 단위이다. 보통 8bit = 1byte이지만, 반드시 그렇게 정의된 것만은 아니다. 1Mb 와 1MB는 다르며, 전자를 8로 나눈 결과가 후자이다. 우리가 흔히 광고에서 보는 인터넷 속도도 100Mbps도 초당 12.5MB의 속도라는 뜻이다. 컨텍스트(Context) : 단순한 정보 원본 이상으로 문맥, 상황에 따라 어떤 해석이 가미되어 이해되는 한차원 높은 공간을 의미한다. 하드웨어나 운영체제 관점에서 프로세서 안에 있는 레지스터, 플래그등의 현재 값 상태들의 집합를 의미한다. 소프트웨어 관점에서는 상황에 맞게끔 실행/결정/판단 해야 하는 부분을 의미한다. 더 나아가 문맥 교환(context switching)은 멀티태스킹 작업 수행시 태스크 상태 정보를 레저스터들에 저장 또는 이전 상태를 불러오기 위한 작업을 의미한다. 여기서 태스크 상태 정보는 CPU 레지스터, 메모리 스택을 의미한다. ...