본문 바로가기

분류 전체보기

 (61)
플로이드 와샬 (Floyd Warshall) 플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘. 1. 시작점에서 목적지로 가는 경로에 한 정점을 지나갈 때 거리가 더 짧아지면 해당 경로로 갱신한다. 2. 모든 시작점과 모든 목적지 쌍에 대해 1을 반복한다. 당연히 O(n^3)이다. 그냥 코드만 봐도 3중첩 for문이다. 갱신될 때 마다 지나야 하는 k를 저장해두면 되돌아가면서 경로를 찾을 수 있다. #include using namespace std; int INF = 987654321; int PAD = 0; int dist[6][6] = // 그래프 셋팅 //직관적이기 쉽게 index0은 패딩으로 채움 { {PAD,PAD,PAD,PAD,PAD,PAD}, {PAD,0,6,8,INF,2}, {PAD, INF,0,..
다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 : 한 정점에서 다른 정점들로 가는 최단경로를 구하는 알고리즘 그냥 기본적인 알고리즘은 노드를 선택할 때 계속 최단 거리의 노드를 찾아주어야 하기에 O(n^2) 시간복잡도가 걸린다. 그렇기에 넣을 때 logn시간이 걸리는 priority_queue를 사용하면 O(nlogn)시간 복잡도로 줄일 수 있다. 그렇기에 현재 코드는 priority_queue로 구현 하였다. 1. 시작노드에서부터 해당 노드로의 최단 거리(배열에 저장된 거리) 중 가장 짧은 노드 선택.(전에 선택된 것들 제외) 2. 선택된 노드에서부터 다음 노드로 가는 경로가 배열에 저장된 최단 경로보다 작으면 갱신 3. 1-2를 끝날 때까지 반복 1. 최단 거리가 갱신될 때마다 pre배열에 그 전 노드를 기록해둠. 2. 나중에..
객체지향 프로그래밍(JAVA) 객체지향 프로그래밍 : 로직을 상태와 행위로 이루어진 객체로 만드는 것이다. 추상화 : 복잡함 속에서 필요한 관점만을 추출하는 행위 refactoring : 코드를 개선해서 더 효율적으로 만드는 행위 class -> 설계도 , 데이터 타입 정의 instance -> 제품 , 구현체 class member(static) : - class에 의해 만들어진 모든 instance가 class 변수를 공유함.(값의 변경도 모두 공유) - class member는 인스턴스화 하지 않고도 class로 직접 접근 가능 함. - instance 가 계속 새로 생성되어도 메모리 하나로 공유 instance member : 인스턴스 끼리 개별적으로 소유 함. instance 가 생성될 때 마다 메모리 새로 할당 -변수와 메..
[프로그래머스] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT) (level 3) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42893 파씽 능력과 자료구조 사용 능력을 알아보기 위한 문제로 보여진다. 자신의 url , 외부링크 url , 일치 단어 개수를 찾는 문제이다. 문자열을 파씽해서 값을 얻을 수 있다. 웹페이지 개수가 최대 20개 밖에 되지 않으니 배열에 넣어서 저장하여도 시간복잡도에 크게 영향을 주지 않는다. 하지만 페이지 개수가 많아지면 map을 사용하여야 하니 연습삼아 map으로 구현하였다. 부가적인 설명은 코드 주석에 달아 놓았다. #include #include #include #include using namespace std; class info { public: int index, base_score; vector..
구조 패턴(Structual patterns) 어댑터 패턴(Adapter Pattern) 어댑터 패턴 : 연관성 없는 두 객체 묶어 사용하는 패턴 (알고리즘을 요구사항에 맞춰 사용할 수 있음) ex) 한 객체의 함수를 다른 객체에서 원하는 형태로 쓸 수 있게 Adapter에서 그에 맞게 변경해서 보내줌 ex - A객체 interface를 B가 호출하는 interface에 맞게 adapter에서 변경해줌 브릿지 패턴(Bridge Pattern) 브릿지 패턴 : 기능과 구현을 따로 만들고 이들을 연결 시키는 것이 목적 (Adapter 처럼 연결 시켜주는 역할이지만 bridge pattern 은 미리 독립적인 진화를 고려한 상태로 만든 것이고 Adapter는 이미 존재하는 두 인터페이스의 불일치를 해결하려는 것이다. (기억 ex-모스부호 - 소리 문자 등..
크루스칼 알고리즘 (Kruskal algorithm) 최소 신장 트리 : 노드를 모두 연결하는 트리에서 가장 짧게 연결할 수 있는 트리 (가장 적은 비용으로 모든 노드를 연결) 크루스칼 알고리즘은 그래프가 주어졌을 때 최소 신장 트리를 찾는 알고리즘이다. 위 그래프에서 최소 신장 트리는 선으로 굵게 칠해진 부분들이다. 우선 크루스칼 알고리즘을 구현 하기전에 Union-Find 알고리즘을 알아야 한다. 또 다른 이름으로는 서로소 집합(disjoint-set)알고리즘 이라고도 부른다. 이 알고리즘은 두 개의 노드가 주어졌을 때 서로 같은 집합인지 아닌지 판별해준다. #include using namespace std; int d[11]; int n = 10; int find_parent(int a) //집합의 부모(루트)를 찾아줌 { if (d[a] == a)..
생성 패턴(Creational patterns) 싱글톤(Singleton) 싱글톤 : 클래스에서 하나의 인스턴스만 생성하도록 구현 하는 것 public class singleton { private static singleton instance; private singleton() {} public static singleton getInstance() { if(instance==null) { instance=new singleton(); } return instance; } } - 기본생성자를 private으로 정의 -> 다른 class에서 생성을 못함. 내부에서만 가능 - 외부에서 생성자가 아니라 함수로 생성하게 함, instance없으면 만들어서 반환하고 이미 있으면 그대로 반환 - getInstance함수는 외부에서 인스턴스화 없이 바로 사용해..
백준 2776번: 암기왕 (C++) 문제 링크 : www.acmicpc.net/problem/2776 문제 자체는 간단한 문제이지만 조금 문제점이 있다. nlogn 복잡도로만 풀면 되는 문제이기에 set을 이용하는 방식과 이분탐색을 이용하는 방식 둘다 통과해야하지만 set으로 풀면 통과가 되지 않는다.(set 자체가 느리기 때문) 문제를 읽어보면 정수의 개수만 1000000개이다. 이것을 그냥 배열에 넣어서 순차 탐색으로 수를 찾는다면 1000000*1000000수준의 복잡도가 나온다. 그러므로 방법은 set을 이용하는 방법과, 이분 탐색을 이용하는 방법이 있다. -set을 이용하는경우 -> 균형 이진 트리 구조임으로 해당 값을 찾는데 logn수준의 복잡도이다. -이분탐색을 이용하는 경우 -> 역시 분할 정복임으로 logn수준의 복잡도이다..
[프로그래머스] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) (level 3) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60061 특별한 함정이 없는 구현, 시뮬레이션 문제이지만 머리속으로만 그리다보니 잦은 실수가 발생하였다. 1. build_frame vector의 순서대로 건물을 짓는다. 단 설치할 때 존재할 수 없는 경우에는 스킵한다. 2. 건물을 삭제하라는 명령어가 나올경우에는 우선 건물을 삭제해본다. 그리고 삭제할 때 영향을 받는 건물들만 존재할 수 있는지 확인해본다. 3. 건물이 완성되면 (x축), (y축), (기둥, 보) 이런 순서로 3중 포문으로 vector에 저장을 한다면 굳이 sorting 하지 않아도 문제에서 원하는 순서대로 저장 가능하다. -> 위 설명에서 빨간글씨에 사용하는 함수 기둥의 경우 -> 바닥위에 있..
[프로그래머스] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42888 단순한 문자열 문제이다. 하지만 map을 모르는 사람이라면 당황할 만 하다. 문자열과 닉네임을 단순한 배열에 쌍으로 저장한다면 아이디를 찾는데만 해도 존재하는 아이디 개수n 만큼 어마어마한 시간이 걸린다. 하지만 map으로 저장한다면 tree구조 이기때문에 logn이라는 짦은 시간이 걸린다. 1. record를 차례대로 쭉 훑으면서 Enter일 경우 아이디와 닉네임을 쌍으로 저장하고 Change일 경우에는 갱신한다. 이렇게 한번 쭉 훑으면 결국 map에는 아이디에 대해 최신 닉네임이 저장된다. 2. 다시 record를 처음부터 쭉 훑으면서 명령어가 enter, leave일 경우만 최신 닉네임으로 출력해준..

티스토리툴바