본문 바로가기

분류 전체보기

 (126)
연결 리스트와 배열 (Linked list) ▶연결 리스트종류는 단일/이중/원형 연결 리스트가 있다. 데이터를 가진 노드를 포인터로 연결해 놓은 자료구조이다.연결리스트는 데이터의 추가/삭제가 O(1)의 시간에 가능하다는 장점이 있지만 (다음 노드의 주소만 변경해주면 됨)배열과는 달리 특정 위치의 데이터 찾기가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.(가장 앞이나 뒤에 있는 노드부터 포인터를 하나씩 이동해가며 데이터를 찾아야함) ▶배열번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조로, 같은 종류의 데이터들을 순차적으로 저장한 것을 말한다.특정 위치의 데이터에 접근하는 것이 O(1)의 시간에 가능하다는 장점이 있지만 (인덱스로 데이터에 바로 접근)데이터 추가/삭제가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.(데이터를..
데이터베이스란? ▶데이터베이스의 정의 어느 한 조직에서 업무 처리를 위해 다수의 사용자들이 공용으로 사용하는 통합/저장된 운영 데이터의 집합을 말한다. 쉽게 말하면, 데이터의 중복을 최소화하고 여러 사용자들이 공유할 수 있도록 저장되어 조직을 운영하는데 사용되는 데이터의 집합이라고 할 수 있다. ▶데이터베이스의 특징 실시간으로 데이터가 검색/삽입/갱신/삭제될 수 있으며, 여러 사용자가 동시에 접근하여 이용할 수 있고, 데이터 중복을 최소화하여 관리한다. 또한, 데이터 검색 시 요구받은 데이터 내용으로 검색하게 된다는 특징이 있다. 1. 계속적인 변화 2. 동시 공유3. 실시간 접근성4. 내용에 의한 참조5. 데이터 중복의 최소화 ▶데이터베이스의 구성 요소- 개체(Entity) : 실세계에 존재하는 (서로 구별되는)유형 ..
[BOJ] 백준 2468. 안전 영역 ▶문제설명[BOJ] 백준 2468. 안전 영역 https://www.acmicpc.net/problem/2468 ▶Hint BFS/DFS 문제이다. 1. NxN 배열에 높이 정보를 입력받으면서 가장 높은 값과 낮은 값을 구한다. 2. 1에서 구한 가장 낮은 값부터 가장 높은 값까지 모든 경우에 대하여 NxN배열의 모든 인덱스에 대해 안전 영역을 구하는 BFS를 수행하며 BFS를 수행한 횟수를 카운트하면서 카운트 값의 최대 값을 구한다. 인접한 안전 영역을 체크하는 BFS를 수행하여 visited배열에 안전 영역을 true값으로 저장하고 visited[i][j]==false인 경우에만 BFS를 수행하도록 구현한다. ▶시간 복잡도최악의 경우 O(N^6) 만에 정답을 구할 수 있다. N = 100, 최소 높이..
[BOJ] 백준 16236. 아기 상어 ▶문제설명[BOJ] 백준 16236. 아기상어 https://www.acmicpc.net/problem/16236 ▶HintBFS 알고리즘을 활용해서 먹을 수 있는 물고기를 먹으러 가는데 걸리는 시간을 구하고, 먹을 수 있는 물고기들을 vector에 담는다. - 먹으러 가는데 걸리는 시간이 동일한 물고기가 둘 이상일 경우는?BFS를 통해 먹을 수 있는 물고기를 vector에 담아서 r(행)을 기준으로 오름차순으로 정렬하고, r이 동일한 경우 c(열)를 기준으로 오름차순 정렬하여 인덱스 [0]에 있는 물고기를 먹으면 가장 상단이면서 왼쪽에 있는 물고기를 먹을 수 있게 된다. - 아기 상어의 데이터 관리는?전역변수로 관리하면 편하다. int shark_r, shark_c, shark_size, eat_num..
[BOJ] 백준 1726. 로봇 ▶문제설명[BOJ] 백준 1726. 로봇 https://www.acmicpc.net/problem/1726 ▶Hint BFS 문제이다. BFS 수행 시 모든 방향에 대해서 방문 체크를 해야한다는 점이 핵심이다. - 어떻게 해당 위치에서 모든 방향에 대해 방문 체크를 수행하나?visited[R][C][0 ~ 4] : 좌표 R,C에 방향 0, 1, 2, 3으로 방문했는지의 여부 체크 [Queue에서 꺼낸 뒤 수행해야 하는 일]1. 현재 위치와 현재 방향이 도착지점인 경우 answer 값을 현재 카운트 값으로 업데이트 2. 현재 카운트 값이 answer보다 같거나 큰 경우는 더이상 볼 필요 없으므로 무시(continue) 3. 현재 위치에서 현재 방향으로 1칸/2칸/3칸 전진하는 경우에 대해 카운트를 1 증가..
[SWEA] 5658. 보물상자 비밀번호 ▶문제설명[SWEA] 5658. 보물상자 비밀번호 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE ▶Hint 브루트포스 & 시뮬레이션 문제이다. 사각형의 각 변에 적힌 16진수들을 시계방향으로 회전시키기 위해서 Queue 자료구조를 사용하는 것이 적합하다. 하지만 Queue는 저장된 데이터에 인덱스로 접근하는 것이 불가능하다. 그래서 Deque 자료구조를 활용한다. 1. 16진수들을 Deque에 모두 push_back한다. 2. 4개의 변에 있는 16진수를 각각 10진수로 변환하여 list에 저장한다.[변..
[BOJ] 백준 17140. 이차원 배열과 연산 ▶문제설명[BOJ] 백준 17140. 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 ▶Hint 시뮬레이션 문제이다. - R 연산과 C 연산1. A배열의 해당 행이나 열에 존재하는 숫자의 개수를 센다. 2. 등장한 숫자와 그 숫자의 등장 횟수를 구조체로 저장하여 벡터에 push_back한다.push_back과 동시에 A배열의 해당 위치의 값을 0으로 바꿔주어야 원하는 결과를 얻을 수 있음 3. 문제의 조건에 맞게 구조체를 정렬한다.등장 횟수가 큰 순으로 정렬하되, 등장 횟수가 같은 경우 해당 숫자의 크기가 큰 순으로 정렬함 4. 정렬된 구조체를 A배열에 순차적으로 저장한다. 5. 연산 수행시 행이나 열의 크기가 다를 수 있는데, 가장 큰 index를 구해 행과 열의..
[BOJ] 백준 17142. 연구소 3 ▶문제설명[BOJ] 백준 17142. 연구소 3 https://www.acmicpc.net/problem/17142 ▶Hint 브루트 포스 & BFS & 시뮬레이션 문제이다. M개의 바이러스를 활성화 시켜서 활성/비활성 바이러스로 가득 채우기 위해 걸리는 최소 시간을 구하는 문제다. 모든 바이러스가 활성화 되어 있지 않아도 괜찮다는 조건이 문제를 까다롭게 만드는 것 같다. 가능한 모든 경우에 대해 시뮬레이션 해야 하므로, 기존의 map을 복사하여 활용한다. 벽은 -1, 바이러스는 -2, 빈 곳은 -3으로 표시하는 것이 핵심이다. - 입력으로 주어진 바이러스들 중 M개를 선택하는 모든 경우는 어떻게 구할 것인가?next_permutation()을 활용하면 쉽게 해결할 수 있다. - 활성/비활성 바이러스로 ..

티스토리툴바