본문 바로가기
728x90
반응형

분류 전체보기

 (198)
[백준] 단지번호붙이기 : 2667번 - Python https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 풀면서 몰랐던 개념 DFS 알고리즘에 대한 개념 ->https://ye5ni.tistory.com/108 참고! 문제의 접근 방법 1. 아이디어 - 2중 for문, 값 1 && 방문 X => DFS - DFS를 통해 찾은 값을 저장 후 정렬해서 출력하기 2. 시간복잡도 - DFS : O(V+E) - V, E : N^2, 4N^2 - V+E = 5N^2 ~= N2 ~= 625 >> 가능함 3...
[백준] 그림 : 1926번 - Python https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제를 풀면서 몰랐던 개념 BFS 알고리즘에 대한 개념 -> https://ye5ni.tistory.com/105 참고! 문제의 접근 방법 1. 아이디어 - 2중 for => 값 1 && 방문 X => BFS - BFS 돌면서 그림 개수 +1, 최댓값을 갱신 2. 시간복잡도 - BFS : O(V+E) = V + 4V = 5V = 5(m*n) - V : m * n = 500 * 500 (m, n이 최대 ..
너비 우선 탐색(Breadth-First Search) : BFS 너비 우선 탐색(Breadth-First Search) - 그래프 탐색 방법 중 한 가지 종류 "시작 정점에 인접한 노드를 중심으로 탐색함" 아이디어 - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex를 Queue에 저장 - Queue의 가장 먼저 것 뽑아서 반복 [그래프 예시] 파이썬으로 구현한 BFS 알고리즘 from collections import deque # BFS 함수 정의 def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 - 젤 처음에는 큐에 1만 들어가있음 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐..
[데이터베이스] key, 1:1 관계, 1:N 관계, N:M 관계의 개념 키 - 슈퍼키 : 특정 튜플을 고유하게 식별할 수 있는 것. ex) 고객 아이디 = 슈퍼키가 될 수 있음. (각 아이디가 같은 고객은 없기 때문이다) 나이, 등급, 직업 = 슈퍼키가 될 수 없음 X. (나이, 등급, 직업이 같은 고객은 충분히 존재할 수 있기 때문이다) (고객아이디, 나이, 등급, 직업) = 슈퍼키가 될 수 있음. (고객 아이디로 각 튜플을 구분할 수 있기 때문이다) 즉 슈퍼키는 유일성은 만족하지만 최소성은 만족하지 않는다. - 후보키 : 기본키가 될 수 있는 컬럼들 - 기본키 : 후보키들 중 선택받은 키로 데이터를 명확하게 구분하고 찾기 위한 것. ***기본키 조건*** 테이블에 저장된 행을 식별할 수 있는 유일한 값이어야 한다. 값의 중복이 없어야 한다. NULL 값을 가질 수 없다...
[UMC] Server 워크북 모음 보호되어 있는 글입니다.
Quick DBD 사용 후기 데이터베이스 설계시, ERD를 그려야할 일이 매우 많은데 그 때 사용하면 편리할 좋은 애플리케이션을 소개해보려고 한다. 데이터베이스 수업 시간에 ERD를 설계해 본 경험이 있어서 흥미가 생겼다. 하지만 그 때는 적당한 툴을 찾지 못해서 손으로 그리기도 하고 그냥 그려진 것을 보고 이해하기도 했었는데 확실히 한계가 있다는 것을 느꼈다. 여러가지 툴이 있다는 것을 알고 있었지만 그 중에서 가장 많은 사람들이 추천한 Quick DBD를 사용해보려고 한다. 다른 것으로 ERD를 확인하려면 각 테이블 정의를 마친 이후에 새 창을 띄워서 봐야 하기도 하고, 사용자의 편의성과 거리가 먼 작업도 있었다. 또 디자인 면에서도 만족하지 못한 경험이 있었다. 아무래도 ERD를 그리는 궁극적인 목적이 나와 나의 팀들, 또는 ..
[백준] 거스름돈 : 14916번 - Python https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 어떤 계산의 몫이 3이라고 하자. 그 몫에서 1을 빼주어서 2로 만들어주고 싶을 때는 나머지에 나누는 수를 더해주면 됨. ex) n // 5 = 3 3 -> 2 로 취급해서 계산을 하고 싶다면, (n % 5)에 + 5 를 해주기! 문제의 접근 방법 - 거스름돈이 1과 3일 경우에는 5와 2 모두로 나누어 떨어질 수 없기 때문에 계산 불가하다. 따라서 -1을 출력해주어야 함. - 거스름돈이 5로 나누었을 때의 나머지가 짝수이면, 2로 나눌 수 있다는 것이므로 5로 먼저 나눠준 후(최대 횟..
[백준] 포인트 카드 : 14471번 - Python https://www.acmicpc.net/problem/14471 14471번: 포인트 카드 예제 입출력 1에서, 포인트 카드 1의 꽝 도장 3개와 포인트 카드 3의 꽝 도장 1개를 당첨 도장으로 바꾸면, 4엔으로 5-1=4장의 카드가 경품과 교환 가능하게 되어, 이것이 최소 비용이다. 예제 입출 www.acmicpc.net 문제의 접근 방법 - 내림차순 정렬 - 이미 당첨 도장의 개수가 M보다 큰 A값을 제외한 나머지 경우의 수만 생각하기 나머지 경우의 수가 M-1이 될 때까지 계산. - 경품의 개수가 충족이 되지 않아서 도장을 바꿔야할 때 내는 1엔이 비용에 들어감. - 최소 비용을 구해야 하기 때문에 M-1에서 M보다 작은 A값들의 개수를 빼준 횟수만큼만 반복문을 돌려서 바꿔야 할 도장의 개수(1..
728x90
반응형

티스토리툴바