티스토리

오도원입니다.

검색하기

블로그 홈

오도원입니다.

ohdowon064.tistory.com/m

오도원공육사 님의 블로그입니다.

구독자: 12

방명록 방문하기

반응형

주요 글 목록

Database와 Storage의 차이점 1. 차이점1 : Physical vs Logical 스토리지는 파일 또는 물리적 저장소이 객체 스토리가 될 수 있다. 데이터베이스는 조직화된 데이터가 저장된 논리적 저장소이다. 2. 차이점2 : 관계 데이터베이스는 일종의 스토리지이다. 3. 차이점3: 저장 데이터 종류 스토리지는 텍스트파일, 이미지, 영상 등 다양한 종류의 데이터가 저장될 수 있다. 데이터베이스는 ID, record, 거래정보와 같은 구조적 또는 반구조적 데이터가 저장된다. 정리 스토리지는 파일이 담긴다. DB는 nosql을 차치하고 일반적으로 2차원 데이터 형태인 컬럼(column, field)와 로우(row, record)로 구성되는 테이블형 데이터가 담긴다. 즉, 스토리지는 파일형태가 되면 무엇이든 담을 수 있지만 DB에 담기 위.. 공감수 2 댓글수 2 2020. 9. 4.
ORM이란 무엇인가 ORM (Object Relational Mapping, 객체 관계 매핑) ORM은 데이터베이스와 객체 지향 프로그래밍 언어 간의 호환되지 않는 데이터를 변환하는 프로그래밍 기법이다. 객체 지향 언어에서 사용하는 '가상' 객체 데이터베이스를 구축하는 방법이다. 객체와 관계형 데이터베이스의 데이터를 자동으로 매핑(연결)한다. 관계형 데이터베이스에서의 테이블은 객체 지향 언어에서의 클래스을 사용한다. 관계형 모델과 객체 모델간에 불일치가 존재한다. ORM을 통해 객체 간의 관계를 바탕으로 SQL을 자동 생성하여 불일치를 해결한다. 객체를 통해 간접적으로 데이터베이스의 데이터를 다룬다. 공감수 0 댓글수 0 2020. 9. 3.
프로비저닝(provisioning)이란 1. 정의 프로비저닝(provisioning)은 사용자의 요구에 맞게 시스템 자원을 할당, 배치, 배포해 두었다가 필요 시 시스템을 즉시 사용할 수 있는 상태로 미리 준비해 두는 것을 말한다. 2. 예시 서버 자원 프로비저닝, OS 프로비저닝, 소프트웨어 프로비저닝, 스토리지 프로비저닝, 계정 프로비저닝 등이 있다. 수동으로 처리하는 '수동 프로비저닝'과 자동화 툴을 이용해 처리하는 '자동 프로비저닝'이 있다. 출처. https://ko.wikipedia.org/wiki/%ED%94%84%EB%A1%9C%EB%B9%84%EC%A0%80%EB%8B%9D 공감수 1 댓글수 0 2020. 9. 2.
어부의 고기잡이 1. 문제 현재 위치에서 N미터 떨어진 곳까지 물고기가 얼마나 있는지 주어진다. 정확히 M마리의 물고리를 잡고자 할 때 그물은 딱 한번 내리고 딱 한번 올릴 수 있다. 이때 정확히 M마리를 잡을 수 있는 경우의 수를 구하라. 예를 들어 5 3 7 2 1의 물고리가 존재할 때, 10마리의 물고리를 잡을 수 있는 경우의 수는 위와 같이 2가지가 존재한다. 가장 밑의 경우 떨어져있으므로 불가능한다. 2. 입력 3. 출력 가능한 경우의 수를 출력한다. 4. 알고리즘 : 투포인터 그물을 내리는 위치, 그물을 올리는 위치를 가리키는 두개의 포인터를 이용해서 구할 수 있다. 왼쪽에서 시작하기 때문에 물고기가 너무 적다면 그물을 올리는 위치를 오른쪽으로 이동하고, 물고기가 너무 많다면 그물을 내리는 위치를 오른쪽으로 .. 공감수 0 댓글수 0 2020. 8. 26.
수열 만들기 1. 문제 수열에 있는 연속된 원소들의 합을 이용하여 새로운 수열을 만들 수 있다. 예를 들어 1, 2, 3, 4, 5와 같은 수열이 있다고 했을 때, 1, 2를 합쳐서 3, 3, 4, 5 또는 2, 3, 4를 합쳐서 1, 9, 5를 만들 수 있다. 모든 원소를 합쳐서 15 등의 수열을 만들 수도 있다. 두 개의 수열이 주어질 때, 두 수열을 같은 수열로 만들 수 있을 때, 만들수 있는 가장 긴 같은 수열의 길이를 구하는 것이다. 2. 입력 3. 출력 두 수열을 똑같은 수열로 만들 수 있다면 그 수열의 최대 길이를, 만들 수 없다면 -1을 출력한다. 4. 알고리즘 : 그리디, 투포인터 첫번째로 두 수열의 총합이 다르다면 절대로 같은 수열로 만들 수 없다. 해당 확인이 끝났다면 투 포인터를 이용해서 원소들.. 공감수 0 댓글수 0 2020. 8. 26.
다리 건설 1. 문제 강의 상부와 하부를 연결하는 다리를 건설해야한다. 다리는 여러 지점으로 나눠져있고, 같은 번호의 지점끼리만 연결할 수 있다. 다리를 건설하기 위해 미리 N개의 지점을 골라두었다. 강 한쪽은 1번부터 N번까지 순서대로 지점에 번호를 매겼지만 반대쪽은 무작위로 매겨져 있다. 같은 번호의 두 지점끼리만 다리로 연결할 수 있다. 두 개의 다리는 겹칠 수(교차될 수) 없다. 주민들의 편의를 위해 다리는 최대한 많은 개수를 건설하고자 한다. 2. 입력 첫 번째 줄에는 지점의 개수 N이 주어진다. (5 공감수 0 댓글수 0 2020. 8. 26.
우주의 평화를 위하여 1. 문제 지구를 호시탐탐노리는 아주 질나쁜 외계인들을 다 무찔러야한다. 그러기 위해서는 외계인들의 행성인 A행성의 모든 기계들을 파괴시켜야한다. A 행성에 있는 모든 기계의 위치는 N x N크기의 격자판 상에 나타낼 수 있다. 격자판 위의 모든 기계가 같은 종류의 기계라면 단 한 번의 공격으로 모든 기계를 파괴할 수 있다. 만약 격자판 위의 기계들 중 하나라도 다른 종류의 기계가 있다면, 4개의 구획으로 나누어 다시 기계를 확인한다. 모든 기계가 파괴될 때까지 2-3단계의 작업을 반복한다. 2. 입력 첫번째 줄에는 격자판 크기 N이 주어진다. 이때 N은 항상 2^k(2의 지수승) 형태이다. 두번째 줄부터 N x N 행렬에 기계번호 3이하의 자연수가 주어진다. 3. 출력 기계의 최소 공격횟수 4. 알고리.. 공감수 0 댓글수 0 2020. 8. 25.
HTTP / Nodejs. request entity too large error. Error 413 body size가 너무 커서 발생하는 에러이다. client_max_body_size 설정 때문이다. 대용량의 request를 보내지 못 하도록 제한을 건다. default값은 1MB이다. request의 Content-Length 헤더값이 여기 설정된 값을 초과할 수 없다. POST나 PUT 등의 request 사이즈 제한을 할 수도 있지만, 악의적으로 대용량의 파일을 업로드해서 디스크를 가득 채우는 경우를 방지하는데 사용된다. 1. nginx.config 파일을 수정한다. 파일의 위치는/etc/nginx/nginx.conf 이다. default size가 1mb이므로 이것을 0mb로 바꿔서 제한을 없애거나 늘린다. nginx.conf 파일에서 http, server, location에 설정이 가능하.. 공감수 0 댓글수 0 2020. 8. 24.
하노이의 탑을 풀어보자. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다. 하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n -1번의 이동으로 원판을 모두 옮길 수 있다. 이 규칙들을 이용하여 63(64)개의 원판을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가.. 공감수 0 댓글수 1 2020. 8. 6.
HTTP 에러 코드; 400, 404, 500 에러 등 설명 에러코드 의미 200 에러없이 성공적으로 페이지를 불러오거나 데이터를 전송 400 Bad REquest로써, 요청 실패. 문법상 오류가 있어서 서버가 요청사항을 이해하지 못한 경우 404 Not Found, 문서를 찾을 수 없는 경우. 클라이언트가 요청한 문서를 찾지 못한 경우에 발생. => URL을 잘 살펴봐야한다. 405 Method not allowed, 메소드 허용불가. Request 라인에 명시된 메소드를 수행하기 위한 해당 자원의 이용이 허용되지 않는 경우 발생. => 페이지는 존재하지만 접근하지 못하게 막거나 리소스를 허용안하는 경우 415 지원되지 않는 형식으로 클라이언트가 요청을 해서 서버에서 요청에 대한 승인을 거부한 경우 => ContentType, Content Encoding 데이.. 공감수 0 댓글수 2 2020. 7. 29.
Error Code: 2013. Lost connection to MySQL server during query 1. Error 2013 쿼리문을 실행했을 때, 다음과 같은 화면이나 하단 로그창에서 로딩아이콘만 계속 돌아가다가 2013에러가 발생할 때가 있다. 다음 에러는 해당 쿼리의 수행시간이 너무 오래걸려서 서버에서 끊어버린것이다. 본인은 계속 중간에 멈춰버려서 해당 쿼리문을 될 때까지 실행하다가 다음과 같은 문제가 발생했다. AWS RDS의 cpu 점유율이 100%를 찍은 것이다. 왜이렇게 됐나 살펴보니깐 문제를 발견했다. 서버에서 끊어버린 쿼리문은 데이터베이스 내에서는 계속해서 수행중이라는 것이다. 다음 쿼리는 작업중인 프로세스를 확인하는 쿼리다. show processlist; 해당 쿼리가 Execute 상태라는 것을 알 수 있다. 이때부터 문제가 발생했다. 쿼리가 안 끝나서 실행중인데 똑같은 쿼리를 실행.. 공감수 1 댓글수 0 2020. 7. 23.
조엘 테스트 https://zetawiki.com/wiki/%EC%A1%B0%EC%97%98_%EC%8A%A4%ED%8F%B4%EC%8A%A4%ED%82%A4 조엘 스폴스키 - 제타위키 다음 문자열 포함... zetawiki.com 1 한국어 1. 소스 컨트롤을 사용하는가? 2. 한번에 빌드를 만들어낼 수 있는가? 3. 일별 빌드(daily build)를 만드는가? 4. 버그 데이터베이스가 있는가? 5. 새 코드 작성 전에 버그를 고치는가? 6. 최신 스케줄이 있는가? 7. 설계서(spec)가 있는가? 8. 프로그래머들에게 조용한 작업 환경이 제공되는가? 9. 돈으로 살 수 있는 최고의 도구를 사용하는가? 10. 테스터가 있는가? 11. 면접시에 코딩시험을 보는가? 12. 무작위 사용성 테스트(hallway usab.. 공감수 0 댓글수 0 2020. 7. 12.
19년 9월 2주차 : 신에게는 아직 12척의 배가 남았사옵니다 1. 문제 - 난이도 ★ 12척의 배가 주어졌을 때, 대장선을 제외한 11척을 이용해 최적의 진형을 찾는 것이다. 2. 입력 11 * 11의 행렬이 주어지며, aij는 i번째 배가 진형의 j번째 위치했을 떄의 전투력을 뜻한다. 3. 출력 첫번째 줄에 최적의 진형을 이루었을 때의 합을 구한다. 두번째 줄에는 아군의 진형을 첫번째부터 순서대로 출력한다. 최적의 진형이 여러개인 경우 사전순으로 앞선 진형을 출력한다. 4. 알고리즘 문제는 11척의 배를 순서대로 나열할 때, 그 능력치가 최대가 되는 순서를 찾는 문제이다. 가장 간단한 방법은 역시 완전탐색이다. 1번배가 1번자리에, 2번배가 2번자리에, ... , 11번 배가 11번자리에 들어가는 진형부터, 1번배가 11번자리에 2번배가 10번자리에, ..., .. 공감수 0 댓글수 1 2020. 7. 11.
19년 9월 2주차 : 애틋한 친구 1. 문제 - 난이도 ★ 거리가 가장 먼 친구를 찾아보자. 2. 입력 첫번째 줄에는 사람 수 N이 주어진다. 두번째 줄부터 N + 1번째 줄까지 i번째 사람의 위치 정보가 좌표로 주어진다. 3. 출력 가장 애틋한 친구의 번호를 구분하여 낮은 번호부터 출력한다. 4. 알고리즘 이중 반복문을 이용하여 모든 친구들 사이의 거리를 비교하여 가장 거리가 먼 친구를 출력한다. 5. 코드 # 입력 처리 N = int(input()) friends = [list(map(int, input().split())) for _ in range(N)] # 거리 구하는 함수 def dist(x, y): return (x[0] - y[0])**2 + (x[1]-y[1])**2 max_list = [] # 가장 거리가 먼 친구 저장.. 공감수 0 댓글수 5 2020. 7. 4.
19년 9월 1주차 : 환상의 조합 1. 문제 - 난이도 ★★ 팀원들의 능력치가 주어졌을 때 홍현이의 능력을 포함한 그 합이 S가 되게하는 환상의 조합을 구하라. 2. 입력 첫번째 줄에는 사람 수 N과 팀원들의 능력합 S가 주어진다 두번째 줄부터 N명의 사람들의 능력치가 주어진다. 첫번째로 주어지는 능력은 홍현이의 능력이다. 3. 출력 최고의 팀을 만들 수 있는 경우의 수 출력, 팀원은 최소 1명 이상이어야 한다. 즉, 홍현이 혼자 팀을 구성할 수 있다.. 4. 알고리즘 : 완전 탐색 홍현이를 포함하는 부분집합의 합이 S가 되는 경우의 수를 찾는 문제이다. 집합 A의 크기가 n일 때 공집합을 포함한 부분집합의 개수는 2^n개이다. 따라서 문제는 O(2^N)시간안에 풀 수 있다. 완전 탐색은 두가지 방법이 있다. 1. 재귀 함수 2. 비트 .. 공감수 0 댓글수 0 2020. 7. 4.
투 포인터(two pointer) 출처 : 한국 코드페어 비타알고 시즌2 투 포인터(two pointer) 1. Two Pointer 정렬된 배열에서 두 개의 인덱스를 사용하여 원하는 값을 찾는 기법 투 포인터는 정렬된 배열에서 2개의 포인터(인덱스)를 이용하여 두 포인터가 가리키는 값과 찾고자 하는 값(key값)을 비교한 뒤 포인터를 조정하여 원하는 결과를 얻어내는 기법이다. 대표적인 예로 '배열 내 합이 S가 되는 순서쌍 찾기'가 있다. for(int i = 0; i < n; ++i){ for(int j = i + 1; j < n; ++j){ if(data[i] + data[j] == S) cout 공감수 0 댓글수 0 2020. 7. 4.
19년 9월 1주차 : 수의 비밀 1. 문제 - 난이도 ★ 해당 수가 2^k인지 판별하는 것이다. 2. 입력 10^18 이하의 자연수가 주어진다. 3. 출력 2의 거듭제곱이면 Yes, 아니면 No를 출력한다. 4. 알고리즘 먼저 바로 떠오르는 생각은 2로 계속 나누다가 나머지가 0이면 2의 거듭제곱이고 1이면 2의 거듭제곱이 아닌 수이다. 그러나 입력값을 보면 절대로 안된다는 것을 알 수 있다. 그렇다면 다른 방법으로 접근해야한다. 바로 비트연산이다. 2의 거듭제곱은 딱 한 비트만 1인 수이다. 위와 같이 2의 거듭제곱은 비트 하나만 1이다. 해당 수를 n이라고 했을 때, n & -n은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다. 따라서 2개 이상이 켜져있다면 n과 n & -n은 절대로 같을 수 없다. 그러나 2의 거듭제곱과 같이 .. 공감수 0 댓글수 0 2020. 6. 17.
19년 9월 1주차 : 시공의 폭풍 속으로 1. 문제 - 난이도 ★ 시공의 폭풍은 5대5 대결게임이다. 당신의 팀원들이 선택한 4명의 영웅번호와 당신이 선택하고자 하는 5명의 영웅번호가 주어질 때, 이미 팀원이 선택한 영웅이 아닌 영웅의 수를 구하라. 2. 입력 첫줄에 팀원이 선택한 4명의 영웅 번호가 주어진다. 두번째 줄에는 당신이 선택하고자 하는 5명의 영웅번호가 주어진다. 3. 출력 당신이 선택하고자 하는 영웅들 중에서 팀원이 선택하지 않은 영웅의 수를 출력한다. 4. 알고리즘 선택하고자하는 영웅리스트를 돌면서 팀원 리스트에 없으면 카운트를 1증가시킨다. 본인은 파이썬의 filter() 함수를 사용했다. x = list(map(int, input().split())) y = list(map(int, input().split())) n = l.. 공감수 1 댓글수 1 2020. 6. 17.
데이터 AI 사이언티스트로서의 개발 진로 https://www.youtube.com/watch?v=8mjeJpHtLVQ 실제로 DSC를 처음 시작할 때 머신러닝에 관심을 가지는 가장 큰 이유는 '멋있어보인다.'이었다. 물론 하다가 막히니깐 관심이 없어졌고, 그렇게 열정도 식었다. 현재 내가 컴퓨터 공학을 전공으로 하지만 컴공에서 확실하게 정한 분야는 없다. 프론트, 백, 클라우드, 네트워크, 머신러닝 등 여러가지의 분야가 존재하지만 나는 뭐를 해야할지 모르겠다. 그러는 와중에 송호연님의 이 영상을 보고 어느정도 진로를 정하게 되었다. 해당 영상의 골자는 이것이다. 일단 개발을 잘해야한다. 컴공이면 꼭 머신러닝 모델링은 한번씩 해본다. 그러면서 여러 머신러닝 관련 지식들을 가볍게 알게되고 관심을 가지게 된다. 물론 나는 관심이 없어졌지만, 데이터.. 공감수 7 댓글수 2 2020. 6. 1.
Algorithm. 문자열 - 압축 1. Run-Length Encoding 2. Huffman Coding 3. Lampel-Zicv-Welch Encoding 4. Arithmetic Coding 공감수 0 댓글수 0 2020. 5. 31.
Algorithm. 문자열 - 접미어 배열 1. 접미어 배열 텍스트의 접미어들을 사전식으로 나열한 배열 파이썬에서는 리스트로 구현한다. 접미어 트리보다 메모리를 효율적으로 사용하지만 다소 느리다. 텍스트 인덱싱, 데이터 압축, bio-informatics등의 다양한 분야에서 사용한다. 예시) s = abab b, ab, bab,b abab => 접미어 사전순 정렬 : ab, abab, b, bab => 접비어 배열 : [3, 1, 4, 2] 2. 접미어 배열 복잡도 O(n)의 메모리 크기 O(nlogn) 시잔에 생성 텍스트 T에 패턴 P의 존재를 O(|P| + logn) 시간에 계산 3. 접미어 배열 장점 생성 방법이 접미어 트리에 간단하다. 적은 메모리로 구현 가능 2개의 선형 크기의 리스트로 구성 전형적으로 접미어 트리에 비해 1/4크기의 메.. 공감수 0 댓글수 0 2020. 5. 31.
Algorithm. 문자열 - 접미어 트리 1. 접미어 트리 하나의 문자열의 모든 접미어들을 포함하는 트라이(Trie)의 압축된 표현 문자열 연산에 필요한 알고리즘을 빠르게 구현할 수 있다. 응용 문자열 매칭(Exact string matching) 부분 문자열 매칭(Substring matching) 최장 공통 부분 문자열(Longest common substring of 2 strings) 예시) 문자열 S = {xabxac}에 대한 접미어 트리 길이가 6이므로 6개의 접미어가 존재 단말노드에는 접미어의 시작위치를 저장한다. 루트를 제외한 내부 노드는 최소 2개의 자식을 갖는다. 각 간선은 문자열 S의 부분문자열 라벨(label)이 부여된다. 한 노드에서 나가는 두개의 간선이 같은 문자열 라벨을 가질 수 없다. 루트에서 단말노드 i까지 경로에.. 공감수 0 댓글수 0 2020. 5. 31.
Algorithm. 문자열 - 트라이 1. 트라이 정보 검색에 사용된 자료구조 문자열의 집합을 표현하는 트리 다음 5개의 문자를 하나의 트라이로 표현. 각 간선은 하나의 문자에 대응 같은 노드에 나오는 간선들은 같은 레벨을 갖지않는다. 각 문자열을 단말 노드에 대응하고 문자열의 개수만큼 단말 노드가 존재한다. 2. 접미어 트라이 문자열의 모든 접미어를 Trie로 표현 길이가 n인 문자열 A = a0 a1 a2 ... an-1 ai ai+1 ai+2 an-1인 n개의 접미어 접미어 트라이를 이용한 문자열 연산 부분 문자열 검사 두 접미어의 최장 공통 접두어 찾기 사전적 순서로 정렬된 k번째 접미어 찾기 부분 문자열 검사 'abac' 문자열 접미어 트라이가 있을 때, 어떤 문자열이 부분 문자열인지 검사하는 방법은 한 문자씩 루트에서 대응되는 간.. 공감수 0 댓글수 0 2020. 5. 31.
Algorithm. 문자열 - 문자열 매칭 1. 문자열 처리 예제) 다음 중 x안에 y가 존재하는지 찾아보자. 2. 문자열 매칭(패턴 매칭) 텍스트 문자열(t)에서 패턴 문자열(p) 포함 여부를 찾는 것. 고지식한 패턴 검색 알고리즘 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 파이썬의 패턴 매칭 3. 고지식한 알고리즘(Brute Force) 텍스트 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 # t : 텍스트 # p : 패턴 # N : 텍스트의 길이 # M : 패턴의 길이 def BruteForce(t, p): N = len(t); M = len(p) i = 0 # 텍스트 인덱스 j = 0 # 패턴 인덱스 while i < N and j < M: if t[i] != p[i]: # 다.. 공감수 0 댓글수 0 2020. 5. 31.
Algorithm. 문자열 - 해싱 자주 수행되는 작업들 디렉토리 경로 따라가기 디렉토리 내에 존재하는 파일들 나열하기 특정 파일의 존재 유무 판별하기 해당 작업들은 시스템의 성능 저하의 원인이 된다. 이 작업들은 검색에 기반해서 수행되는 작업들이므로 어떻게 해결해야할까. 1. 해싱 특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법이다. O(1) 시간 복잡도 1. 직접 번지 테이블 직접 번지 테이블(배열)에 저장하는 경우 전체 키(key)들의 집합(U)이 작은 경우에 효율적이다. 키 k가 테이블(T)에서 위치 k에 저장 테이블(배열)의 크기 = 집합 U의 크기 그러나 전체 키 값들의 집합 U가 클 때, 현실적인 컴퓨터 메모리 공간에서 테이블 T를 생성하는 것은 불가능하다. 또한 실제 저장되.. 공감수 0 댓글수 0 2020. 5. 31.
Algorithm. 2주차 스터디 정리 1. 백트래킹 2. 그래프의 기본과 탐색 3. 그래프의 최소 비용 문제 1. 백트래킹 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는다. 2. 그래프의 기본과 탐색 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 1) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 너비 우선 탐색(BFS) 시작 정점에서 인접한 정점을 먼저 모두 차례로 방문 3. 그래프의 최소 비용 문제 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 다익스트라 알고리즘.. 공감수 0 댓글수 0 2020. 5. 25.
Algorithm. 3주차 스터디 계획 3주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주 공부할 내용은 문자열 탐색입니다! 파이썬은 타 언어에 비해서 문자열을 다루는데 굉장히 강력한 언어입니다. 그러면 이러한 파이썬의 특성을 이용해서 문자열 탐색을 공부해봅시다. 1. 문자열 탐색 1) 학습 목표 1. 해싱에 대한 기본 개념에 대해 이해한다. 2. 문자열에서 패턴을 탐색하는 주요한 알고리즘에 대해 이해한다. 3. 트라이, 접미어 트리, 접미어 배열에 대해 학습하고 문자열 .. 공감수 0 댓글수 0 2020. 5. 25.
Algorithm. 그래프 - 다익스트라 알고리즘 https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 최단 경로 간선의 가중치가 있는 directed graph가 있을 때, 두 정점 사이의 경로들 중 간선의 가중치가 합이 최소인 경로 단일 시작점 최단 경로 문제 출발점에서 다른 모든 정점들에 이르는 최단경로를 구하는 문제 다익스트라 알고리즘 : 음의 가중치 허용 안함. 밸만 포드 알고리즘 : 음의 가중치 허용, 음의 사이클은 허용 안함 모든 쌍 최단 경로 문제 모든 정점 쌍 간의 최단 경로를 구하는 문제 플로이드-워샬 알고리즘 : 동적계획.. 공감수 0 댓글수 3 2020. 5. 24.
Algorithm. 그래프 - 크루스칼 알고리즘 1. 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 정점이 n개인 그래프에서 n-1개의 간선을 선택하는 방식 초기 상태는 n개의 정점들이 하나의 트리가 된다. 하나의 정점을 포함하는 n개의 상호 배타 집합이 존재 간선을 선택하면 간선의 두 정점이 속한 트리가 연결되고 하나의 집합으로 합쳐진다. 사이클이 생기면 안된다. 두 정점이 같은 집합의 원소인지 검사해야한다. 동작과정 최초, 모든 간선을 가중치에 따라 오름차순 정렬 최소 가중치 간선부터 선택하면서 트리 증가 사이클이 존재하면 다음 가중치 낮은 간선 선택 n-1개의 간선이 선택될 때 까지 (2) 반복 소스코드 # G : 그래프 def mst_kruskal(G): mst = [] # 선택된 간선 집합, 공집합으로 .. 공감수 0 댓글수 0 2020. 5. 24.
Algorithm. 그래프 - 프림 알고리즘 1. 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 임의의 정점을 하나 선택해서 시작 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 (2) 반복 두 종류의 상호 배타 집합(disjoint set)이 필요 트리 정점 : 최소 신장 트리에 선택된 정점들 비트리 정점 : 선택되지 않은 정점들 소스코드 # G : 그래프 # s : 시작 정점 def mst_prim(G, s): key = [INF] * N # 가중치를 무한대로 초기화 pi = [None] * N # 트리에서 연결될 부모 정점 초기화 visited = [False] * N # 방문 여부 초기화 key[s] = 0 # 시작 정점의 가중치를 0으로 .. 공감수 2 댓글수 0 2020. 5. 24.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.