메이쁘

https://maivve.tistory.com/20 AWS(Amazon Web Service) 프리티어 1년 무료 서버 1대 받는 과정 개인 프로젝트, 이전에 진행했던 프로젝트에서 서버 및 DB를 개발하기 위해 회사에서 익혔던(배웠던...) AWS 서버를 받아서 어떻게 사용하면 되는지까지를 포스팅해보겠다. 거두절미하고 바로 진행하겠다. 1. 홈페.. maivve.tistory.com 위 포스트에서 AWS 1년 무료 인스턴스를 만들어봤습니다. 1년이면 여러 사이드 프로젝트를 진행하고 테스트할 수 있겠네요!! 아무튼 이제 서버를 구축했으니까 서버에 들어가서 디비든 통신이든 구축해야겠지요! 서버 안으로 들어가는 과정을 담아봤습니다. PUTTY와 이전에 만들었던 pem 파일을 가지고 와주세요! PUTTY는 여..

개인 프로젝트, 이전에 진행했던 프로젝트에서 서버 및 DB를 개발하기 위해 회사에서 익혔던(배웠던...) AWS 서버를 받아서 어떻게 사용하면 되는지까지를 포스팅해보겠다. 거두절미하고 바로 진행하겠다. 1. 홈페이지가서 회원가입하기 http://console.aws.amazon.com 에 들어갑니다. 가서 회원가입을 진행합니다. 이름 및 이메일, 비밀번호는 취향과 조건에 맞게 기입하고 진행합니다. 사용자는 개인 사용자로 하는데 전화번호는 010~으로 기입하는데, -나 띄어쓰기 없이 입력을 하기 바랍니다. 국적은 대한민국 주소는 영어로 입력하라 해서 대충 한글을 영어로만 바꿔서 기입했다. 마지막 단계에서 카드번호와 유효년월을 입력하면 SMS 또는 전화 인증을 하라고 합니다. 이것까지 하면 회원가입 완료! ..

허프만 코드란? - 데이터를 효율적으로 압축하는 데 사용하는 알고리즘으로, 그리디 알고리즘에 속함. - 데이터 빈도 수에 따라 우선순위 큐에서 작은 두 개의 노드를 꺼내고 이를 합쳐 트리를 만드는 과정이 있다. - 고정 길이 코드와 가변 길이 코드 두 가지 표현 방법이 존재함. 허프만 코드 인코딩 과정(허프만 코드를 만드는 과정) ** 참고로 여기서 말하는 방식은 가변 길이 코드 표현 방법에 해당한다. - (a) ~ (f) 까지의 과정을 담은 그림으로, 이 그림을 보면 바로 이해할 수 있을 것이다.. - (a) : 예를 들어, 인코딩을 할 문자열이 casdffsdasadceacsd 라고 주어지면, 이 문자열에 각 알파벳 별로 얼마나 포함되어있는지(빈도 수) 나타낸 수 이다. 이 수들을 우선순위 큐에 담아..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net 문자열 처리 분류 문제. 두 문자열 A와 B의 length를 구한 다음 0부터 B.length - A.length 까지 for문 진행. 이..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net 다익스트라 알고리즘 + BFS(너비우선탐색)을 섞은? 문제이다. 2차원 int 배열 map과 각 지점마다의 최단 거리..

Union / Find 알고리즘이란? -> 그래프 알고리즘 중 하나로 합집합을 찾는 방법. -> 상호 배타적 집합(Disjoint-Set)이라고도 함. -> 여러 노드(정점)가 주어질 때, 두 개의 노드(정점)를 선택해서 현재 두 노드(정점)가 서로 같은 그래프에 속하는지 판별하는 알고리즘. -> Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 -> Union : x와 y가 포함되어 있는 집합을 합치는 연산 -> 처음에는 모든 노드의 부모를 해당 인덱스(자기 자신)로 설정 샘플 코드 - Union 함수 // 두 노드를 합치는 함수 public static void union(int x, int y) { x = find(x); y = find(y); if(x != y) parent[y] = x; ..

크루스칼 알고리즘이란? -> 프림 알고리즘과 같이 MST(최소 스패닝 트리) 를 찾기 위한 알고리즘. -> 조금 Greedy한 방법. -> 간선을 중심으로 탐색하면서 노드를 확인용으로만 사용함. -> 핵심은 각 단계에서 사이클을 이루지 않은 간선을 선택하는 것! -> Union-Find 개념이 필요함! https://maivve.tistory.com/11 -> 시간복잡도 : O(ElogV) 지만, 프림보다 크루스칼이 빠르다. 매커니즘 1) 모든 간선들을 우선순위 큐에 넣고 weight를 오름차순해서 가장 작은 값부터 poll 한다. 2) poll 한 간선의 양 끝 점이 같은 부모인지 체크한다. 3) 같은 부모이면 다음 간선을 선택하고 3-1) 다른 부모이면 해당 간선을 최종 선택한다. -> 가중치 추가 ..

벨만-포드 알고리즘이란? -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. 사이클 포함 X. -> 음의 가중치도 계산 가능. 다익스트라 알고리즘보다 시간복잡도 높음(더 느림). -> 간선들을 중심으로 찾음 -> 방문되지 않은 정점(값이 무한대인 정점)에서 출발하는 간선들은 고려하지 않는다. -> 즉, 다익스트라의 변형을 통해 음수간선에 대한 처리 및 음수 사이클을 체크하기 위한 알고리즘. -> 여기서 모든 사이클을 한 번 다 돌아도 distance의 변화가 하나도 없으면 그냥 해당 for문을 종료시켜도 됨. ** 최악의 경우 시간복잡도 O(n^3), 보통 O(VE) 샘플코드 public static boolean bellman(int n, int m, int sta..

프림 알고리즘이란? -> n개의 정점을 가지는 그래프에서 MST(Minimun Spanning Tree = 최소 신장 트리) 를 구하기 위해 사용하는 알고리즘 -> 그래서 결과로 나온 트리는 N-1개의 간선을 가진다. = N-1번 반복 수행 -> 그래프의 간선을 넣을 때 간선이 방향이 없는 양방향이므로 양 쪽 다 넣어야 한다.(한 쪽만 넣어도 가능한 듯) -> 프림 : 원리 상 정점을 중심으로 간선을 탐색함. 크루스칼 : 간선을 중심으로 탐색함 -> 시간복잡도 : O(ElogV) -> 이진 힙(우선순위 큐)을 사용했을 때 매커니즘 1) 정점 중 아무 시작 정점을 고르고, 정점과 연결된 모든 Vertex를 큐에 넣는다. 2) 해당 정점에 연결된 모든 간선 중 가장 최소 비용을 가진 간선을 선택해서 연결. ..

다익스트라 알고리즘? -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘. -> 사이클 포함 X -> 음의 가중치가 존재하면 사용 불가능. 매커니즘 1) 체크되어있지 않은 정점 중에서 D(Distance)의 값이 가장 적은 정점(또는 시작점)을 선택(우선순위 큐에 삽입) 2) 우선순위 큐에서 해당 점을 꺼내고, 이 점을 인덱스로 하는 visited 배열의 값을 True로 변경(방문했다는 표시) -> 방문 따지면 안되는 경우도 있음..! 3) 해당 점과 연결된 모든 점을 검사(방문 여부에 관계 없이 진행. 그 이유는 최단 경로가 갱신될 수 있으므로) 4) 해당 점을 x, 연결된 다른 끝 점을 y, 이동하는 Weight를 w라고 했을 때, D[y] > D[x] + w를 만..