젠의 전공공부

[C++] 이진 트리 순회 완벽 정리: 재귀(포인터) vs 배열(인덱스) 구현 비교

코딩 테스트나 알고리즘 공부를 하다 보면 이진 트리를 구현하는 방법이 크게 두 가지로 나뉩니다. 가장 정석적인 구조체와 포인터를 이용한 방법, 그리고 코딩 테스트에서 힙(Heap)이나 세그먼트 트리 등을 다룰 때 자주 쓰는 배열(인덱스)을 이용한 방법입니다.오늘은 이 두 가지 방식으로 전위(Pre), 중위(In), 후위(Post) 순회를 구현하는 코드를 비교해 보겠습니다.1. 핵심 개념 비교트리 순회의 핵심은 "루트(나 자신)를 언제 방문(출력)하느냐"입니다.(L: 왼쪽 자식, R: 오른쪽 자식, N: 나 자신)전위 순회 (Preorder): N → L → R (나를 먼저)중위 순회 (Inorder): L → N → R (나를 중간에)후위 순회 (Postorder): L → R → N (나를 마지막에)방..

[C++] 유기농 배추

문제 - 유기농 배추 (BOJ 1012)https://www.acmicpc.net/problem/1012문제 설명배추밭에 배추가 심어져 있다.배추가 상, 하, 좌, 우로 연결되어 있으면 하나의 배추 묶음으로 본다.각 배추 묶음마다 지렁이 1마리가 필요하다.배추밭의 크기와 배추가 심어진 위치가 주어질 때,필요한 최소 지렁이 수를 구하는 문제이다.목표배추밭에서서로 연결된 배추 묶음의 개수를 구하라.즉, 그래프 관점에서 보면연결 요소(Connected Component)의 개수를 구하는 문제이다.접근 방법배추밭을 2차원 배열로 표현한다.모든 칸을 하나씩 탐색한다.아직 방문하지 않은 배추(1)를 발견하면:지렁이 수 +1DFS를 이용해 해당 배추와 연결된 모든 배추를 방문 처리방문한 배추는 다시 세지 않도록 0으..

[C++] DFS & BFS

그래프 탐색은 크게 두 가지 방식이 있다.DFS (Depth First Search) : 깊이 우선 탐색BFS (Breadth First Search) : 너비 우선 탐색그래프란?정점(Vertex)과 간선(Edge)으로 이루어진 구조정점: 노드간선: 노드와 노드를 연결하는 선🔍 DFS (깊이 우선 탐색)✔ 개념한 방향으로 갈 수 있을 때까지 끝까지 내려갔다가, 막히면 되돌아오는 방식 마치 미로 탐색처럼 동작한다.✔ DFS 탐색 순서 예시1 → 2 → 4 → (더 못 감) → 3 → 5 ✔ DFS 특징재귀 또는 스택으로 구현한 경로를 깊게 탐색백트래킹 문제에서 자주 사용✔ DFS 사용 예경로 존재 여부조합, 순열미로 탐색트리 순회DFS 구현 (재귀)vector> graph;vector visited;vo..

[C++] 로프

문제 - 로프 (BOJ 2217)https://www.acmicpc.net/problem/2217문제 설명N개의 로프가 있고, 각 로프는 최대 중량이 정해져 있다.여러 개의 로프를 선택해 하나의 물체를 들어 올릴 수 있으며, 이때 로프들은 같은 무게를 나눠서 들게 된다.즉, 로프들을 이용해 들어 올릴 수 있는 최대 중량은 다음과 같다.(선택한 로프의 개수) × (선택한 로프들 중 가장 약한 로프의 중량)목표로프들을 적절히 선택했을 때 들 수 있는 최대 중량을 구하라.접근 방법로프를 내림차순으로 정렬한다[가장 튼튼한 로프 → 가장 약한 로프]이렇게 정렬하면,앞에서부터 i개를 선택했을 때 가장 약한 로프는 항상 i번째 로프가 된다. i번째 로프까지 사용했을 때의 최대 중량 계산선택한 로프 개수: i + 1최..

[C++] 정수 삼각형

문제 - 프로그래머스 43105: 정수 삼각형최대 경로 합을 구하는 DP 문제삼각형 형태로 숫자가 주어질 때,위에서부터 아래로 내려가는 경로 중 합이 가장 큰 값을 찾는 문제입니다.문제 설명 [7] [3] [8] [8] [1] [0] [2] [7] [4] [4]각 칸에서는 바로 아래 또는 오른쪽 아래 칸으로만 이동할 수 있다.즉, (i, j)에 있을 때 이동할 수 있는 위치는:(i+1, j)(i+1, j+1)문제는 가장 큰 합을 만들 수 있는 경로를 구하는 것이다.해결 전략: Bottom-Up DP✔ Bottom-Up이란?탑다운은 “문제를 나눠 해결 → 메모이제이션” 방식이라면,바텀업은 반대로 가장 작은 문제를 먼저 해결하면서 올라오는 방식입니다.이 문제의 경우..

[C++] Find the Difference of Two Arrays

문제 - LeetCode 2215. Find the Difference of Two Arrays이번 문제는 두 정수 배열 nums1, nums2가 주어졌을 때,answer[0] : nums1에는 있지만 nums2에는 없는 중복 제거된 값들의 리스트answer[1] : nums2에는 있지만 nums1에는 없는 중복 제거된 값들의 리스트를 구하는 문제입니다.배열의 길이는 최대 1000이고 값의 범위는 -1000 ~ 1000입니다.문제 요약입력:nums1 = [1,2,3], nums2 = [2,4,6]출력:[[1,3],[4,6]]nums1에서 1, 3은 nums2에 없고nums2에서 4, 6은 nums1에 없기 때문입니다.풀이 아이디어두 배열의 숫자들을 map 또는 배열 형태로 등장 여부 체크값의 범위가 -1..

[C++] Product of Array Except Self

문제 - LeetCode 238. Product of Array Except Selfhttps://leetcode.com/problems/product-of-array-except-self/submissions/1851830377/?envType=study-plan-v2&envId=leetcode-75문제 설명정수 배열 nums가 주어졌을 때,배열 answer을 만들어 answer[i]에 nums[i]를 제외한 모든 원소의 곱을 넣어야 한다.조건나눗셈 사용 금지O(n) 시간에 해결prefix / suffix 곱은 32비트 정수 범위 안에 들어옴예시 1Input: nums = [1,2,3,4]Output: [24,12,8,6]예시 2Input: nums = [-1,1,0,-3,3]Output: [0,0..

[C++] Maximum Number of Vowels in a Substring of Given Length

문제 - LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length문자열 s와 정수 k가 주어졌을 때,길이가 k인 모든 부분 문자열 중에서 가장 많은 모음(a, e, i, o, u) 을 포함하는 개수를 구하는 문제다.예를 들어,s = "abciiidef", k = 3 이면부분 문자열 "iii"가 가장 많은 모음 3개를 포함한다.문제 접근이 문제는 겉보기에는 문자열 전체를 순회하며 부분 문자열을 매번 새로 검사해야 할 것처럼 보이지만,그렇게 하면 시간 복잡도는 **O(n × k)**가 되어 s.length가 10⁵까지 가능하다는 조건에서 시간 초과가 난다.그래서 필요한 기법이 바로 슬라이딩 윈도우(Sliding Window) 방식이다.Sl..