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 레지스터, 메모리 스택을 의미한다. ...
1.개발 진행 및 완료상황 2주차 python algorithm bfs 문제 풀이 중 CSAPP 2주차 목표 읽기 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 18352 18352번: 특정 거리의 도시 찾기 문제 어떤 나라에는 1번부터 N 번까지의 도시와 M 개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X 로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X 에서 출발 도시 X 로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N =4, K =2, X =1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4… ...
1.개발 진행 및 완료상황 2주차 python algorithm dfs 문제 1회독 완료 CSAPP 2주차 목표 읽기 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2644(파이썬) 2644번: 촌수계산 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2… ...
1.개발 진행 및 완료상황 3주차 python algorithm 그래프 탐색 기본 개념 공부 3주차 python algorithm 그래프 탐색 기본 문제 풀이 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 1991 1991번: 트리 순회 1991번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 트리 순회 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 43388 28410 21707 66.502% 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 … ...
1.개발 진행 및 완료상황 2주차 python algorithm 종료 3주차 python algorithm 시작 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 1715 1715번: 카드 정렬하기 1715번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 카드 정렬하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 46099 15534 11930 33.435% 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶… ...
1.개발 진행 및 완료상황 2주차 python algorithm 틀린 문제 복습 완료 CSAPP 2주차 목표 읽기 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2110(파이썬) 2110번: 공유기 설치 2110번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 공유기 설치 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 55494 18901 13282 36.209% 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x 1 , …, x N 이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수… ...
이곳에 입소한지 2주가 되었다. 하루가 길고 바쁘다보니 체감으로는 더 오래된 것처럼 느껴진다. 이 기간동안 2번 팀이 바뀌었고, 공부해야 할 주제도 2번 바뀌었다. 시간이 꽤나 느리게 간다는 생각이 든다. 하루 빨리 이곳을 나가야 한다는 생각보단하루라도 더 빨리 성장하고 싶다는 욕심 때문인듯 하다. 보름간 성장을 했다면 했다지만 여전히 배우고 익혀야 할 것은 산더미다. 끝이 있는지, 어디 쯤일지 가늠조차 못하는 주제에 왜이리 조급한지 모르겠다. 그저 더 잘하고자 하는 마음이겠거니 스스로 달랬다. 두번째 에세이를 쓰기 전, 첫 글을 읽어보았다. 다행히 난 여전히 다음날에게 부족했던 모습을 잊지 않고 전해주고 있다. 글을 쓸 때의 다짐을 잊지 않고 하루하루 살아가고 있어서 다행이다. 지금도 난 더 배우고 싶고, 잘하고 싶은 마음이 굴뚝같다. 2주간 초심을 잃지 않았다고 안심하는 꼴이 우스울수도 있지만 보름이 한달이 되고 한달이 석달이 되는 법이니까. ...
자료구조와 시간복잡도에 관한 무작위 정리 큐와 우선순위 큐의 시간복잡도차이 우선순위 큐 구현시 리스트, 힙자료구조 사용 가능 데이터 N개일때, 리스트기반시 최악의 경우 복잡도는 O(N^2), 힙은 O(NlogN) 데이터 갯수가 많아질수록 복잡도는 기하급수적으로 증가. 리스트와 딕셔너리의 차이점 list : 순서 존재, index 존재, mutable, index지정하여 값변경 가능 , 존재확인하는 in연산자는 하나씩 스캔후 반환하여 오래걸린다(성능 낮음) tuple : 순서 존재, index존재, immutable, immutable,같이 저장시 list보다 적은용량(수정 필요없고 간단한형태는 tuple이 좋다) unpacking(튜플의 값 차례대로 변수에 대입 가능 a,b = b, a가 그예임. 하나씩 안넣어도됨) dictionary : key와 value로 구성, 중복불가, 순서x, 크기와 무관하게 in 연산 속도 일정(key값만 찾으니까) set : key값으로만 구성, 중복불가, 순서 X ...