본문 바로가기

전체 글203

[알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱) 분할 정복(Divide & Conquer) 분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘이다. 교수님께서 미친듯이 강조해서 "디바이드앤퀀쿼"만 기억이 난다.. * 동적 계획법(DP)과의 차이점 1. 동적 계획법은 분할한 문제들이 서로 영향을 미침. 2. 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음. * 분할 정복의 필요조건 1. 문제를 나눌 수 있어야 한다. 2. 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 한다. * 분할 정복의 알고리즘의 접근법 1. 분할: 문제를 작은 문제로 분할하는 과정 2. 정복: 분할한 작은 문제들을 해결 3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다. 분할 정복을 이용한 거듭제곱 먼저, 거듭제곱이란 주어진 수를 주.. 2022. 10. 5.
[알고리즘] 행렬 곱셈, 행렬 제곱 행렬 제곱의 문제를 풀어야하는데, 행렬 곱셈을 하는 법부터 정확히 알지 못 했기 때문에 정리하는 글이다. 1. 2740: 행렬 곱셈 문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오. => 행렬의 곱셈 공식에 의해서 N*M, M*K 행렬을 곱하면 N*K 행렬이 된다. 오른쪽 사진에 의하면, 3 x 2 행렬과 2 x 3 행렬이다. 3 x 2 행렬과 2 x 3 행렬을 곱하면 3 x 3 행렬이 만들어진다. 두 행렬을 곱하면 위의 왼쪽 사진과 같은 결과가 나온다. 1) N과 K에 대해 이중 for문을 돌면서, 2) 벡터의 크기 M만큼 for 돌면서 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고 3)결과 행렬에(2차원 리스트) 넣어주면 된다. impo.. 2022. 10. 4.
[알고리즘] 우선순위 큐, 힙 & 백준(최대 힙, 최소 힙, 가운데를 말해요, 카드 정렬하기) 우선순위 큐란, 데이터 삽입은 어떤 순서로 해도 상관없지만 데이터를 삭제할 때는 우선순위에 맞춰 더 높은 우선순위를 갖는 데이터를 먼저 삭제하는 큐를 말한다. 우선순위 큐는 힙을 통해 구현할 수 있다. 힙이란 완전 이진트리의 일종으로 대표적으로 최대 힙과 최소 힙이 있다. - 최대 힙: 루트 노드가 가장 큰 값을 가지며, 부모 노드는 항상 자식 노드보다 큰 값을 갖는다. - 최소 힙: 루트 노드가 가장 작은 값을 가지며, 부모 노드는 항상 자식 노드보다 작은 값을 갖는다. 힙에서의 삭제는 항상 루트 노드를 먼저 삭제하며 노드 변동 시 힙의 성질을 만족하도록 힙을 변동시킨다. 이러한 힙의 특징을 이용하여 우선순위 큐를 구현하는 것이다. 사실상 우선순위 큐를 구현하는 것은 힙을 구현하는 것이다. 최대 힙 구.. 2022. 10. 3.
[WEEK01] 개발일지 (부제: 알고리즘 start) ※ 개발일지가 아니라 일기일 수도 있는 점 양해바랍니다. 오전, 오후, 새벽이 모두 담겨있어요.※ ※ WEEK 시작인 매주 목요일에 업데이트 됩니다. 많.관.부 ※ DAY01 22.09.22 (목) WEEK00의 끝과 새로운 시작 GJ님과 SW님의 도움과 헌신 아래 3일만에 프로젝트 하나를 완성했다. 그래도 힘들게 했던 프로젝트이기에 리드미를 작성했다. WEEK00을 무사히 끝마치고 WEEK01 발제를 한 뒤 예상에도 없던 회식을 하였다. 코치님, 대표님, 의장님과 술을 한 잔을 하고, (한 잔이 아니였..) 얼른 동기들끼리 친해져서 모르는 것도 빨리빨리 물어보라는 명확한 의도의 술자리였다. 정말 덕분에 거의 대부분의 동기들과 안면과 말(?)을 텄고, 친해질 수 있었다. DAY02 22.09.23 (금).. 2022. 9. 29.
[Python] 파이썬 영문 대소문자 변환 참고 공부) https://mwultong.blogspot.com/2006/12/python-uppercase-lowercase-capitalize.html 2022. 9. 27.
[Python] 순열 permutations, 조합 combinations 순열과 조합을 직접 구현하려다가 구현의 벽에 부딪혔고, (ㅠㅠ) import itertools를 이용하여 간편하게 순열과 조합을 이용할 수 있는 방법을 찾았다. 순열 permutation 순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다. 즉, '서로 다른 n개 중 r개를 골라 순서를 정해 나열한 경우의 수'이다. 순열은 순서를 고려하기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 순서를 정해 나열하면 [(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] 이다. 즉, (A, B)와 (B, A)는 다른 것이다. import itertools arr = ['A', 'B', 'C'] nPr = itertools.permutations(arr, 2) .. 2022. 9. 27.
[Python] 리스트의 문자열을 int로 변환 1. map 함수 활용 # list_a = ['1', '2', '3', '4'] -> list_a = [1, 2, 3, 4] 로 바꾸고 싶을 때, list_a = map(int, list_a) 2. 입력 받은 n을 통해 n개의 int형 num 리스트를 출력 import sys n = int(sys.stdin.readline()) num = [int(sys.stdin.readline()) for i in range(n)] # int()를 씌워줌으로써 int 형태로 변환해준다. 3. 입력받기에서 int로 받고 싶다면 list(map(int, sys.stdin.readline().split())) 2022. 9. 27.
[Python] 파이썬 데이터 입력받기 # 1. 하나의 값만 입력받을 때 sys.stdin.readline().strip() # 2. 입력이 한 줄로 여러 값이 들어왔을 때 sys.stdin.readline().split() 결과: ['20', '1', '15', '8', '4', '10'] # 3. 입력이 한 줄로 여러 값이 들어왔을 때, 리스트의 요소들이 int일 경우 list(map(int, sys.stdin.readline().split())) 결과: [20, 1, 15, 8, 4, 10] # 4. 입력이 여러 줄로 들어왔을 때 N = int(sys.stdin.readline()) num = [sys.stdin.readline().split() for i in range(N)] data = list(map(lambda s: s.stri.. 2022. 9. 26.
[Python] 파이썬 숫자 각 자리수 분리 number = 123 num_list = list(map(int, str(number))) print(num_list) 2022. 9. 26.
[WEEK01] 특별한 과제 (부제: 찬찬히 나를 돌아보는 시간) 정신없이 정글 WEEK00가 끝나고 새로운 WEEK01가 시작되었고, 특별한 과제가 주어졌다. 지나온 과거에 대한 성찰 난 유난히도 걱정이 많았고, 생각이 많았다. 학점을 위해, 나의 경험을 위해 쌓아온 대학교 3년의 시간이 어느 날 갑자기 아무것도 아닌 것 같은 느낌이 들었다. 모든게 상대적이라고 누군가에게는 얻고 싶은, 경험하고 싶은 기회들이 있었을 것이다. 하지만, 또 상대적으로 내가 생각하는 대단한 사람들에 비하면 난 아무것도 아니었다. 꽤나 부정적이었고, 앞으로 어떻게 해야할지에 대한 고민들로만 쌓여갔다. 더이상 이렇게는 안 되겠다는 생각에 일단 해보기로 하였다. 무엇이든! 새해가 밝았고 내가 이뤄내고 싶은 모든 일들을 세부 분야로 나누어 작성하였다. 소위 말하는 버킷리스트를 작성한 것이다. 날.. 2022. 9. 24.
[Git] Git 협업 필수 작업 - branch, issue, PR git으로 협업하기 위해 사용했던 방법에 대해 간략하게 정리해보려고 한다. 1. 먼저, 작업할 레포지토리(다른 사람의 Github repository)를 fork 한다. fork ? : 다른 사람의 Github repository에서 내가 어떤 부분을 수정하거나 추가 기능을 넣고 싶을 때 해당 respository를 내 Github repository로 그대로 복제하는 기능이다. 그럼 내 깃허브에 fork한 레포지토리가 생성된다. 내 깃허브에 나만의 레포지토리로 생성된 것이기 때문에 수정하거나 추가를 해도 원본 레포지토리에 영향이 없다. 2. fork한 레포지토리를 IDE에서 clone 한다. git clone [repo url] clone한 레포지토리를 각자의 IDE에서 코드 작업하면 된다. 3. 수정.. 2022. 9. 19.
[Project] 장고 프로젝트 생성 1. 장고 프로젝트 생성 다음 명령어들을 입력하여 장고 프로젝트를 생성한다. 명령어 입력 1) 최신의 pip로 update하는 명령어이다. pip : 파이썬을 설치하면 깔린다. : 다운로드를 받을 수 있게끔 해주는 앱스토어 같은 아이이다. root@goorm:/workspace/jejucoding# pip install --upgrade pip 2) mkdir라는 폴더를 만든다. mkdir : 디렉토리를 만들어주는 명령어 root@goorm:/workspace/jejucoding# mkdir mystie 3) 앞서 만든 mysite라는 폴더로 이동한다. cd : change directory 명령어로, 말그대로 디렉토리를 이동하는 역할을 해주는 명령어 root@goorm:/workspace/jejucod.. 2022. 8. 29.

티스토리툴바