반응형 분류 전체보기103 [백준] 4195번 : 친구 네트워크 유형 : 해시, 집합, 그래프 [예시] 2 3 Fred Barney Barney Betty Betty Wilma 3 Fred Barney Betty Wilma Barney Betty [출력] 2 3 4 2 2 4 핵심 아이디어 1. 해시를 활용한 Union-Find 알고리즘을 이용 2. 딕셔너리 자료형을 해시처럼 사용 가능(파이썬) 1. 합집합 찾기(Union-Find) 알고리즘 - 원소들의 연결 여부를 확인하는 알고리즘 - 부모 테이블을 이용해서 현재 어떤 집합에 포함되어 있는지 확인 def find(x): if x == parent[x]: return x else: p = find(parent[x]) parent[x] = p return parent[x] def union(x,y): x = find(.. 2021. 12. 19. [알고리즘] 그래프 1. 그래프 관련 용어 정리 - 그래프(Graph) : 실제 세계의 현상이나 사물을 정점(노드)와 간선으로 표현 - 노드(Node) : 위치를 말하며 정점(Vertex)와 같은 말 - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 의미, link나 branch라고도 함 - 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 노드 2. 그래프 종류 1) 무방향 그래프(Undirected Graph) - 방향이 없는 그래프 → 노드는 양방향으로 갈 수 있음 - 노드 A,B : (A,B)나 (B,A)로 표현 2) 방향 그래프(Directed Graph) - 방향이 있는 그래프 - 노드 A,B (A→B) : 로 표현 3) 가중치 그래프(Weighted Graph) 또는 네.. 2021. 12. 15. [SQL] 프로그래머스 : 코딩테스트 연습 - 중복 제거하기 1. 풀이 SELECT COUNT(DISTINCT NAME) AS 'count' FROM ANIMAL_INS - 중복 제거 제약조건이 UNIQUE인줄 알았는데 DISTINCT였다. - UNIQUE인 경우 해당 컬럼에 동일한 값이 들어가지 않도록 하는 제약조건으로, CREATE, ALTER 명령문일 때 쓰인다. ** UNIQUE 더 알아보기 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/59408 2021. 12. 15. [SQL] 프로그래머스 : 코딩테스트 연습 - 최댓값 구하기 1. 풀이 1) ORDER BY 이용 SELECT DATETIME AS '시간' FROM ANIMAL_INS ORDER BY DATETIME DESC LIMIT 1 2) MAX 이용 SELECT MAX(DATETIME) AS '시간' FROM ANIMAL_INS 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/59415 코딩테스트 연습 - 최댓값 구하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 progra.. 2021. 12. 15. [SQL] 프로그래머스 : 코딩 테스트 연습 - 상위 n개 레코드 [풀이] SELECT NAME FROM ANIMAL_INS ORDER BY DATETIME LIMIT 1 - 상위 n개를 출력하는 방법을 몰라 검색하였다. - MySQL의 경우 LIMIT를 이용하여 출력 개수를 조절할 수 있는 것을 알았다. - LIMIT 1을 써서 상위 1개 동물 이름을 출력하였다. ** 오라클에서는 WHERE rownum 2021. 12. 14. [알고리즘] 탐색 알고리즘 - 이진탐색, 순차탐색 1. 분할 정복 알고리즘과 이진 탐색 1) 분할 정복 알고리즘(Divide and Conquer) - Divide : 문제를 하나 or 둘 이상으로 나눔 - Conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눔 2) 이진 탐색 - Divide : 리스트를 2개의 서브 리스트로 나눔 - Conquer - 검색할 숫자 > 중간값 : 뒷 부분의 서브 리스트에서 검색할 숫자를 찾음 - 검색할 숫자 < 중간값 : 앞 부분의 서브 리스트에서 검색할 숫자를 찾음 2. 이진 탐색 코드 def binary_search(data, search): if len(data) == 1 and search == data[0]: # 사이즈가 1일 때, 그 때 검색할 데이터 존재할 경우 r.. 2021. 12. 13. 이전 1 ··· 5 6 7 8 9 10 11 ··· 18 다음 반응형
