알고리즘&자료구조 (16) 썸네일형 리스트형 BFS 기본 문제 1012. 유기농배추 배추 지렁이는 인접한 배추들을 이동하며 해충을 잡아 먹는다 밭 군데군데 배추를 심어뒀기 때문에 배추 벌레가 이동할 수 없는 공간이 존재한다 배추밭 전체를 보호하기 위해 필요한 배추 지렁이는 몇마리인가? -> BFS 기본 유형 가로 세로 바꿔 풀어서 약간 헷갈렸다 import java.io.* import java.util.* lateinit var graph: Array lateinit var visited: Array fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val t = readLine().toInt() val bw = BufferedWriter(OutputStreamWriter(System.out).. BFS Breadth First Search 인접한 노드를 먼저 탐색하는 방법 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 최단 경로, 임의의 경로를 찾고 싶을 때 사용한다 큐를 이용하여 구현할 수 있다 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다 2. 큐에서 원소를 꺼내어 그 칸에 인접한 칸(상,하,좌,우)에 대해 3번을 진행한다 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다 4. 큐가 빌 때까지 2번을 반복한다 모든 칸이 큐에 한번씩 들어가므로 시간복잡도는 칸이 N개일 때, O(N)이고, 행이 R개 열이 C개라면 O(RC) ->bfs를 돌 때 큐에 쌓이는 순서는 거리순이다 구현 시 주의할 점 .. 스택의 활용 : 수식의 괄호쌍 수식의 괄호 쌍 주어진 괄호 문자열이 올바른지 판단하는 문제 해결방법 문자열을 앞에서부터 읽어나가며, 닫는 괄호가 나올 경우 가장 최근에 나왔던 여는 괄호와 짝을 지어본다 이때 짝이 지어지지 않는 괄호가 있다면 바르지 않은 괄호쌍이다 가장 나중에 입력된 괄호가 가장 먼저 나오기 때문에 스택구조를 응용하면 해결이 가능하다 여는 괄호가 나오면 스택에 저장하고 닫는 괄호를 만나면 스택 top 값과 비교한다 짝이 지어진다면 pop으로 없애고, 짝이 지어지지 않는 괄호가 있다면 바르지 않은 괄호쌍이다 BOJ 4949. 균형잡힌 세상 조건 (), [] 2종류의 괄호로 이루어진 문자열이 올바른 괄호쌍을 이루고 있는지 판단한다 해결 1. 여는 괄호가 나오면 스택에 넣는다 2. 닫는 괄호가 나오면 스택 top에 있는 값.. 덱 : Deque double ended queue 양쪽 끝에서 삽입 삭제가 가능한 자료구조로 스택과 큐의 특성을 모두 가지고 있다 push, pop 연산이 빈번한 경우 list보다 빠르다 동작에 따른 시간복잡도 원소의 추가/제거 O(1) 제일 앞/뒤 원소 확인 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 배열, 연결리스트로 구현 가능 구조 원소를 담을 배열 head : 가장 앞에 있는 원소 인덱스 tail: 가장 뒤에 있는 원소 인덱스 기능 add() vs offer() add : 값 추가 성공 시 true 반환 / 실패 시 IllegalStateException 에러 발생 offer : 값 추가 성공 시 true 반환 / 실패 시 false 반환 remove() vs poll() r.. Stack Stack 한 쪽 끝에서만 입출력이 가능한 자료구조 Last In First Out 구조다 push x index 3 2 1 top 0 x pop index 3 2 top 1 13 0 12 index 3 2 1 top 0 12 동작에 따른 시간 복잡도 원소 추가 / 제거 O(1) 제일 상단 원소 확인 O(1) 제일 상단이 아닌 나머지 원소들의 확인 / 변경은 원칙적으로 불가능하다 구현 배열, 연결리스트로 구현이 가능하다 [구성] 원소들을 담을 배열 다음 원소가 삽입될 위치의 인덱스 값 push : 배열 사이즈를 넘어가지 않도록 유의 data[top++] = x pop : 원소가 하나도 없을 때 호출하지 않도록 한다 top-- top : pop과 마찬가지로 원소가 하나도 없을 때 호출하지 않도록 한다 da.. 최대공약수, 최소공배수 찾기 : 유클리드 호제법 최대공약수를 찾아야 하는 알고리즘 문제를 만났다 2부터 하나 하나 나눠보다간 시간초과 나올게 뻔했다 그렇다면 몰러요ㅠ 검색해보니 최대공약수를 구하는 알고리즘이 존재했다 이름도 멋져 유클리드 호제법 호제법은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘이다 유클리드씨께 최대공약수 찾는 비법 전수 받겠습니다 최대공약수(GCD) 구하기 : 유클리드 알고리즘 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 나머지가 0이 될 때까지 mod 연산을 반복하도록 구현하면 된다 O(logN)의 시간복잡도를 갖는다 반복문 구현 fun gcd(num1: Int, num2: Int): Int { var .. 연결리스트 자료구조 원소 저장 시 다음 원소가 있는 위치를 포함하여 저장하는 자료구조 특성 1. K번째 원소를 확인/변경하기 위해 O(n)이 필요함 (다음 원소가 무엇인지 하나 하나 확인 필요) 2. 임의의 위치에 원소를 추가/제거 O(1) : 연결리스트의 장점 종류 단일 연결 리스트 각 원소가 다음 원소의 주소를 가지고 있는 리스트 이중 연결 리스트 각 원소가 이전 원소와 다음 원소의 주소를 가지고 있는 리스트 (단일 연결 리스트보다 메모리를 많이 씀) 원형 연결 리스트 끝과 처음이 연결되어 있음 각 원소가 이전 원소 다음 원소의 주소를 둘다 가지거나 하나만 가져도 상관없음 연산별 시간 복잡도 임의의 위치에 있는 원소를 확인/변경 : O(n) 첫번째 원소의 주소만 알고 있기 때문에 n번째 원소를 보기 위해선 순차.. 배열 메모리 상에 원소를 연속적으로 배치한 자료구조 특성 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 overhead가 거의 없음 연산과 시간 복잡도 1. 임의의 위치에 있는 원소를 확인/변경 O(1) 2. 원소를 끝에 추가 O(1) 3. 마지막 원소를 제거 O(1) 4. 임의의 위치에 원소를 추가 O(N) 추가하는 위치 뒤에 있는 원소들을 한칸씩 뒤로 밀어야 하기 때문에 O(N) 소모 추가하는 위치가 뒤쪽에 가까울 수록 소요되는 시간은 줄어듬 5. 임의의 위치에 원소를 제거 O(N) 지운 원소 뒤에 있는 원소들을 앞으로 한칸씩 당겨 와야하기 때문에 O(N) 소모 BOJ 문제 풀기 문제 문제집: 0x03강 - 배열 (BaaaaaaaaaaarkingDog) www.acmicpc.net.. 이전 1 2 다음
