💻

이전글 ) 2020/02/29 - [알고리즘/기본기 다지기] - [알고리즘][DFS와BFS 완전정복] 그래프의 표현 [알고리즘][DFS와BFS 완전정복] 그래프의 표현 어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다. 백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!! 그래서 나.. hyonee.tistory.com 2. 그래프 탐색 DFS:깊이 우선 탐색 -> 최대한 깊숙히 많이 BFS:너비 우선 탐색 -> 최대한 넓게 가는 것 모든가중치가 1인경우 최단거리 탐색 - 위의 2가지 탐색 모두 목적은 모든 정점을 1번씩 방문하는 것 DFS - 스택을 이용해서 갈 수 있을 만큼 최대한 많이 가고 갈 수 ..

어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다. 백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!! 그래서 나와 같이 알고리즘 문제풀이 새내기 왕초보들을 위해 완전 정복이라는 카테고리로 올리고자 한다. 글을 쓰면서 나도 공부하고, 자료가 부디 도움이 되길 바라는 마음입니다 :) 1. 그래프 표현 인접 행렬 - 양방향 그래프 일 때 A[i][j], A[j][i] - 인접 행렬은 없는 간선도 저장하기 때문에 자주 쓰이지는 않는다. 쉬운 문제를 풀 때 주로 사용한다. - 인접 행렬의 공간 복잡도는 O(V^2)이다. 가중치가 없는 경우) #include #include int a[10][10]; int m..

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 ----------------------------------- RRRBB GGBBB BBBRR BBRRR RRRRR ----------------------------------- 적록색약이 아닌 ..

문제 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다. 출력 A와 B의 길이가 같으면서, A와 B..

문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 ..

Q # 1) DBMS를 정의하십시오. 답변 : DBMS는 데이터베이스 관리 시스템을 나타냅니다. 사용자가 데이터에 관한 정보를 가능한 한 효율적이고 효과적으로 구성, 복원 및 검색 할 수 있도록하는 응용 프로그램 모음입니다. 널리 사용되는 DBMS 중 일부는 MySql, Oracle 등입니다. Q # 1-1) RDBMS를 정의하십시오. 답변 : 관계형 데이터베이스 관리 시스템 (RDBMS)은 데이터베이스에 별도의 테이블에 저장된 관계형 데이터 모델을 기반으로하며 공통 열의 사용과 관련이 있습니다. SQL (Structured Query Language)을 사용하여 관계형 데이터베이스에서 데이터에 쉽게 액세스 할 수 있습니다. Q # 1-2) DBMS의 장점에 대해 설명하세요. 답변 : DBMS의 장점은 ..

문제 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다. 출력 첫째 줄에 문제의 정답을 출력한다. 예제 입력1 7 10 20 30 40 50 60 70 1 예제 출력1 20 10 30 40 50 60 70 예제 입력2 5 3 5 1 2 4 2 예제 출력2 5 3 2 1 4..

문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 ..