✔ 최솟값 [백준 10868] 문제 분석하기 전형적인 세그먼트 트리 문제로, 데이터를 변경하는 부분이 없기 때문에 1차원 배열에 최솟값 기준으로 트리 데이터를 저장하고, 질의를 수행하는 함수까지만 구현 손으로 풀어보기 1차원 배열을 이용해 트리의 값을 초기화 트리 배열의 크기가 N = 10이므로 2^k >= N을 만족하는 k의 값은 4 배열의 크기는 2⁴ * 2 = 32 시작 인덱스는 2⁴ = 16 질의값 연산 함수를 수행하고, 결괏값을 출력 슈도코드 작성하기 tree(세그먼트 트리 배열) N(수의 개수) M(최솟값을 구하는 횟수) treeSize 구하기 (Math.pow(2, 트리의 높이 + 1)) leftNodeStartIndex 구하기 (treeSize / 2 - 1) 트리 초기화하기(모든 값을 M..
✔ 구간 합 구하기 [백준 2042] 문제 분석하기 중간에 수의 변경이 번번히 일어나는 상황이 존재하므로 합 배열 자료구조를 이용할 경우 데이터 변경에 시간이 오래 걸리므로 데이터 변경에도 시간이 비교적 적게 걸리는 세그먼트 트리 자료구조를 이용해 문제에 접근 손으로 풀어보기 1차원 배열을 이용해 트리의 값을 초기화 트리 배열의 크기가 N = 5이므로 2^k >= N을 만족하는 k의 값은 3 배열의 크기는 2³ * 2 = 16 시작 인덱스는 2³ = 8 질의값 연산 함수와 데이터 업데이트 함수를 수행하고, 질의와 관련된 결괏값을 출력 슈도코드 작성하기 tree(세그먼트 트리 배열) N(수의 개수) M(변경이 일어나는 개수) K(구간 합을 구하는 개수) treeSize 구하기 (Math.pow(2, 트리의..
✔ 트리 순회 [백준 1991] 문제 분석하기 주어진 입력값을 트리 형태의 자료구조에 적절하게 저장하고, 그 안에서 탐색을 수행하는 로직을 구현 손으로 풀어보기 2차원 배열에 트리 데이터를 저장 전위 순회 함수를 구현해 실행 현재 노드 - 왼쪽 노드 - 오른쪽 노드 순서로 탐색 중위 순회 함수를 구현해 실행 왼쪽 노드 - 현재 노드 - 오른쪽 노드 순서로 탐색 후위 순회 함수를 구현해 실행 왼쪽 노드 - 오른쪽 노드 - 현재 노드 순서로 탐색 슈도코드 작성하기 N(노드 개수) tree(tree 데이터 저장 2차원 배열) for(N의 개수만큼 반복하기) { if(왼쪽 자식 노드가 없을 때) tree 배열에 -1 저장하기 else tree 배열에 왼쪽 자식 노드 인덱스 저장하기 if(오른쪽 자식 노드가 없을..
✔ 문자열 집합 [백준 14425] 문제 분석하기 집합 S에 속해 있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트 손으로 풀어보기 트라이 자료구조를 생성 현재 문자열을 가리키는 위치의 노드가 공백 상태라면 신규 노드를 생성하고, 아니라면 이동 문자열의 마지막에 도달하면 리프 노드라고 표시 트라이 자료구조 검색으로 자료구조 S에 포함된 문자열을 셈 부모-자식 관계 구조를 이용해 대상 문자열을 검색했을 때 문자열이 끝날 때까지 공백 상태가 없고, 현재 문자의 마지막 노드가 트라이의 리프 노드라면 이 문자를 집합 S에 포함된 문자열로 셈 슈도코드 작성하기 N(집합 S의 문자열 개수) M(검사할 문자열 개수) while(N만큼 반복하기) { text(집합 S..
✔ 트리 [백준 1068] 문제 분석하기 리프 노드를 탐색하는 알고리즘을 수행할 때 제거하는 노드가 나온다면 탐색을 종료하도록 하는 아이디어로 접근 손으로 풀어보기 인접 리스트로 트리 데이터를 구현 DFS 또는 BFS 탐색을 수행하면서 리프 노드의 개수를 셈 단, 제거 대상 노드를 만났을 때는 그 아래 자식들과 관련된 탐색은 중지 이는 제거한 노드의 점위에서 리프 노드를 제거하는 효과 리프 노드의 개수를 출력 슈도코드 작성하기 N(노드 개수) tree(트리 데이터 저장 인접 리스트) visited(방문 기록 저장 배열) answer(리프 노드 개수 저장 변수) deleteNode(삭제 노드) for(N의 개수만큼 반복하기) { tree 인접 리스트의 각 ArrayList 초기화하기 } for(N개의 개수..
✔ 트리의 부모 찾기 [백준 11725] 문제 분석하기 주어지는 데이터가 단순하게 연결돼 있는 두 노드를 알려 주는 것이므로 데이터를 저장할 때 양방향 엣지로 간주하고 저장한 후 트리의 루트인 1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주는 것으로 문제에 접근 손으로 풀어보기 인접 리스트로 트리 데이터를 구현 DFS 탐색을 수행 수행할 때는 부모 노드의 값을 정답 배열에 저장 정답 배열의 2번 인덱스부터 값을 차례대로 출력 슈도코드 작성하기 N(노드 개수) tree(트리 데이터 저장 인접 리스트) visited(방문 기록 저장 배열) answer(부모 노드 저장 정답 배열) for(N의 개수만큼 반복하기) { tree 인접 리스트의 각 ArrayList 초기화하기 } for(N - 1개의 개수만..
✔ 불우이웃돕기 [백준 1414] 문제 분석하기 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장하고 나머지 위치의 값들을 i → j로 가는 엣지로 생성하고 엣지 리스트에 저장하여 최소 신장 트리 알고리즘으로 해결 손으로 풀어보기 입력으로 주어진 문자열을 숫자로 변환해 총합으로 저장 소문자는 '현재 문자 - 'a' + 1'로 변환 대문자는 '현재 문자 - 'A' + 27'로 변환 i와 j가 다른 경우에는 다른 컴퓨터를 연결하는 랜선이므로 엣지 리스트에 저장 저장된 엣지 리스트를 바탕으로 최소 신장 트리 알고리즘을 수행 최소 신장 트리의 결괏값이 최소한으로 필요한 랜선 길이이므로 처음 저장해둔 랜선의 총합에서 이를 빼 정답으로 출력 단, 최소 신장 트리에서 사용한 엣지 개수가 N - 1이 아..
✔ 다리 만들기 2 [백준 17472] 문제 분석하기 섬으로 표현된 값을 각각의 섬마다 다르게 표현한 후 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 엣지가 있는지 확인해 엣지 리스트를 만듦 이후에는 최소 신장 트리를 적용하면 문제를 해결할 수 있음 손으로 풀어보기 지도의 정보를 2차원 배열에 저장하고 섬으로 표시된 모든 점에서 BFS를 실행해 섬을 구분 방문한 적이 없고 바다가 아닐 때 같은 섬으로 인식 모든 섬에서 상화좌우로 다리를 지어 다른 섬으로 연결할 수 있는지 확인 연결할 곳이 현재 섬이면 탐색 중단, 바다라면 탐색을 계속 수행 다른 섬을 만났을 때 다리의 길이가 2 이상이면 이 다리를 엣지 리스트에 추가 예) 1번에서 2번 섬으로 다리 길이가 4일 경우 → 1 2 4 엣지 리스트에 추..
