전체 글533 [알고리즘] 가르침 (백준 1062번) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트랙킹을 통한 완전탐색을 하는 문제다. 비트마스크와 배열 둘 중 하나를 이용해서 풀 수 있다. 2개의 메모리, 시간 효율 차이는 거의 없다. 그냥 똑같은 수준이다. Solution 공통적으로 행해야 할 것은 우선 가르칠 수 있는 단어가 5개 미만이면 어떤 글자도 읽을 수 없다. 만약 5개 이상이라면 남극언어의 기본 시작단어, 끝단어를 이루고 있는 알파벳들 'a c t n i' 5가지부터 추가시키고 시작한다. 1. boolean 배열로 가르침 여부 체크 .. 2020. 10. 3. [알고리즘] 퍼즐 (백준 1525번) 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 비트마스킹 문제를 찾고 있었는데 비트마스킹으로 풀기엔 시간이 너무 오래걸려서 그냥 배열을 이용해서 풀었다. BFS를 이용해야 하는 문제다. Solution 우선 고려해야할 것은 1차원 배열의 index와 2차원 배열의 row, column을 왔다갔다 해야되는 것이다. 여기서 핵심은 visited, 즉 방문 처리를 무엇으로 할 것이냐 인데 난 int형 배열을 이용해서 처리했다. 문자열을 사용하는 사람도 있는데 문자열로도 성공은 하지만 메모리 사용량 측면에선 int형 배열이 훨씬 효율적이다. 1. 전역 변수 static HashSet visi.. 2020. 10. 3. [알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘 플로이드 와샬 (Floyd-Warshall) 유향 그래프에서 '모든 정점' → '모든 정점' 까지의 최단 경로를 구하는 알고리즘이다. 시간복잡도 : O(N ^ 3) , (N은 노드의 수) 삼중 반복문을 사용하기에 N의 크기가 상대적으로 적을 때 사용해야한다. 알고리즘 정점 i → 정점 j 까지의 최단 거리를 저장하는 dist[][] 배열을 둔다. dist 초기화 i == j : 0 i → j 까지의 간선이 존재한다면 dist[i][j] = w[i][j] i → j 까지의 간선이 존재한다면 dist[i][j] = INF (무한대) 삼중 반복문 실행 첫번째 반복문 k = 1 ~ N : 거쳐가는 정점 두번째 반복문 i = 1 ~ N : 시작점 세번째 반복문 j = 1 ~ N : 도착점 dist[i][j] = .. 2020. 10. 3. [데이터베이스] JOIN JOIN 2개의 테이블에 대해서 서로 연관되어있는 튜플들을 결합하여 새로운 릴레이션을 반환하는 것을 의미한다. 쉽게 말해 2개의 테이블에서 데이터들을 검색하는 방법이다. 1. INNER JOIN 2개의 테이블이 모두 가지고 있는 튜플들만 반환하는 방법이다. 교집합 SELECT A.name, B.age FROM A INNER JOIN B ON A.ID = B.ID 2. LEFT OUTER JOIN JOIN 연산자 왼쪽에 위치한 테이블의 튜플 모두를 반환한다. JOIN 되지 않는 튜플들의 오른쪽 COLUMN값은 NULL로 채운다. SELECT A.name, B.age FROM A LEFT OUTER JOIN B ON A.ID = B.ID 3. RIGHT OUTER JOIN JOIN 연산자 오른쪽에 위치한 테.. 2020. 10. 3. 이전 1 ··· 86 87 88 89 90 91 92 ··· 134 다음
