전체 글397

• [백준/BOJ] 11724번: 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤.. PS(Problem Solving)/BOJ 2022. 6. 19.

• [백준/BOJ] 2573번: 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보 빙산의 높이는 바닷.. PS(Problem Solving)/BOJ 2022. 6. 16.

• [백준/BOJ] 1697번: 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의.. PS(Problem Solving)/BOJ 2022. 6. 14.

• [백준/BOJ] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 1.. PS(Problem Solving)/BOJ 2022. 6. 14.

• 

  [알고리즘] 그래프 탐색(Graph Search) /BFS, DFS 그래프 그래프란 공집합이 아닌 노드(vertex, node)들의 유한 집합 V와 이 노드들을 연결하는 간선(edge)들의 집합 E로 구성된다. -> G = (V, E), |V| = n, |E| = m 트리는 그래프의 한 종류이다. 그래프에서 사이클이 존재하지 않으면 곧 트리이다. 노드의 차수: 노드에 연결된 간선의 수를 말하며, 방향 그래프에서는 진입 차수(indegree)와 진출 차수(outdegree)로 나누어 고려한다. 경로(path): 두 개의 노드를 연결하는 일련의 노드들 - 노드 a에서 b까지의 경로 a, v1, v2, . . . , vk, b가 존재하기 위해서는 간선 (a, v1), (v1, v2), . . ., (vn-1, vk), (vk, b)가 존재해야 한다. - 단순 경로: 한 노드를.. Algorithm 2022. 6. 2.

• 

  [백준/BOJ] 7576번: 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 .. PS(Problem Solving)/BOJ 2022. 4. 23.

• [백준/BOJ] 2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고.. PS(Problem Solving)/BOJ 2022. 4. 17.

• [백준/BOJ] 2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 .. PS(Problem Solving)/BOJ 2022. 4. 16.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - 랜덤 피벗 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com https://jjunsu.tistory.com/188 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알.. Algorithm 2022. 4. 14.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com https://jjunsu.tistory.com/188 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알.. Algorithm 2022. 4. 13.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추 jjunsu.tistory.com 퀵 정렬 왼쪽 피벗 저번에는 피벗을 중앙으로 잡았을 때를 알아봤었다. 이번에는 피벗을 맨 왼쪽으로 잡았을 때를 알아보도록 하자. 맨 앞의 원소를 pivot으로 하고, left를 pivot의 한칸 뒤 원소로 잡는다. 또한 right는 맨 뒤의 원소로 잡는다. 이제 left가 pivot보다 클 때까지 증가시키고, right는 pivot보다 작아.. Algorithm 2022. 4. 13.

• 

  [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추가적인 공간을 거의 사용하지 않는다. 실제 가장 많이 사용하는 정렬 알고리즘이기도 하다. 비교 기반 정렬 알고리즘은 O(nlogn)보다 빠를 수 없다. 퀵 정렬의 과정 1. 배열 안에 있는 요소 중 하나를 피벗(pivot)으로 고른다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮겨 분할한다. 3. 분할된 왼쪽 배열과 오른쪽 배열에서 다시 pivot을 정하고 재귀를 이용하여 더 이상 나눠지지 않을 때까지 분할을 반.. Algorithm 2022. 4. 10.

• 

  [알고리즘] 마스터 정리(도사 정리) 도사정리 재귀 관계씩으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법으로, 재귀 알고리즘의 시간 복잡도를 결정해주는 블랙박스 툴이다. 재귀 알고리즘의 점화식(recurrence)으로부터 시간 복잡도를 결정하며, 표준 점화식으로만 가능하다. f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대해 f(n)이 양이라는 의미이다. 표준 점화식 3개의 파라미터로 구성된 대부분 재귀 알고리즘을 분석할 때 사용할 수 있는 점화식을 표준 점화식이라 한다. 여기서 a는 재귀호출의 수, b는 입력 크기가 줄어드는 정도, d는 일반 과정에서 소요되는 시간 복잡도의 지수이다. (a는 작을수록 좋으며, b는 클수록 좋다.) a, b, d는 모두 n과 독립적인 상수이고, d=0이라면 상수 시간을 뜻.. Algorithm 2022. 4. 9.

• 

  [알고리즘] 분할 정복(Divide & Conquer) 분할정복이란? 문제를 나눌 수 없을 때까지 나누어 각 작은 사례에 대한 해답을 얻고, 이들을 결합하여 원 문제에 대한 해답을 얻는 알고리즘이다. 시간복잡도는 O(nlogn)이며, 공간복잡도는 O(n)을 갖는다. 보통 다차시간 알고리즘의 성능을 개선하기 위해 사용한다. 분할정복의 전략 문제를 같은 유형의 작은 문제로 나눈다. (Divide) 작은 문제를 재귀적으로 해결한다. 해결 결과를 결합하여 원래의 문제에 대한 해결책을 제시한다. (Conquer) 합병 정렬(Merge Sort) 일반적인 방법으로 구현했을 때, 안정 정렬에 속한다. 구체적인 방법을 알아보면, 하나의 리스트를 두 개의 균등한 크기로 분할, 정렬한 후, 정렬된 두 리스트를 합하여 하나의 정렬된 리스트가 되게 하는 것이다. 합병 정렬의 단계.. Algorithm 2022. 4. 6.

• 

  [알고리즘] 재귀 함수, 꼬리 재귀 재귀 함수 재귀 함수는 어떠한 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식의 함수이다. 반복문을 사용하는 함수를 재귀 함수를 통해 구현하는 것이 가능하다. 재귀 함수는 보통 재귀적 사용이 자연스러울 때 사용된다. 재귀 함수의 장점 코드가 간결해지고, 가독성이 좋아진다. 변수 선언을 줄일 수 있다. 재귀 함수의 단점 시간 복잡도의 계산이 반복문에 비해 어렵다. 함수 호출이 많아지면 Stack Overflow의 위험이 있다. 호출할 때마다 메모리의 스택이 쌓여 성능에 문제가 생긴다. 재귀 함수의 예제 public static int factorial(int n) { if(n == 1) return 1; return n * factorial(n - 1); } 꼬리 재귀 알고리즘 재귀 함수의 단점을.. Algorithm 2022. 4. 6.

• 

  [알고리즘] Brute Force Algorithm(전수 조사 알고리즘) Brute Force Algorithm(전수 조사 알고리즘) 모든 경우를 다 조사해보는 방법이다. 처음부터 끝까지 계산을 해나가며 해답을 찾는데, 이는 경우의 수가 제한적일 경우에만 사용 가능하다. 하지만 컴퓨터가 계산을 해나가기 때문에 생각보다 범위가 크다. Brute Force의 종류 선형 구조 - 순차 탐색 비선형 구조 - DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 순차 탐색이 흔히 말하는 Brute Force라고 생각이 된다. DFS와 BFS는 후에 따로 설명을 하겠다. 전수 조사 방법 전수 조사는 보통 재귀적으로 구현한다. 하지만 모든 재귀는 반복문을 이용해 동일한 기능을 구현할 수 있으므로, 반복문을 통해서도 구현이 가능하다. 가능한 모든 경우의 수를 전부 조사하는 방법이라 단순한 접.. Algorithm 2022. 4. 4.

• [백준/BOJ] 11722번: 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N.. PS(Problem Solving)/BOJ 2022. 3. 28.

• 

  데이터베이스 시스템 개요 DB 시스템(Database System: DBS)이란? - 데이터를 DB에 저장하고, DBMS를 사용해서 필요한 정보를 관리하고 생성하는 컴퓨터 중심의 시스템이다. DB 시스템의 구성 요소 No. 구성 요소 역할 1 데이터베이스(DB) 데이터를 저장한다. 2 데이터베이스 관리 시스템(DBMS) DB를 생성, 관리, 조작함으로써 사용자와 DB를 연결해주는 소프트웨어이다. 3 데이터 언어 (Data Language) DB 정의와 조작, 제어를 위한 DB 전용 언어이다. 4 DB 사용자 데이터 언어를 사용해서 DB에 접근하는 사람으로, 일반 사용자와 응용 프로그래머, DB 관리자로 구분할 수 있다. 5 DB 컴퓨터 효율적인 DB 관리를 위해서 DB에 대한 연산을 전담하는 DB 관리 전용 컴퓨터이다. 데이터 .. Database 2022. 3. 27.

• [백준/BOJ]1927번: 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보.. PS(Problem Solving)/BOJ 2022. 3. 27.

• [백준/BOJ] 6603번: 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13.. PS(Problem Solving)/BOJ 2022. 3. 27.