생각하는 아져씨

트리의 순회(Tree Traversal)트리 순회 예시전위 순회(pre-order traverse): 루트를 먼저 방문한다.중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문한다.후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문한다.트리 순회 구현하기참조트리의 순회(Tree Traversal)트리 자료구조에 포함된 노드를 특정한 방법으로 한번씩 방문하는 방법이다.트리의 정보를 시각적으로 확인할 수 있다. 대표적인 트리 순회 방법은 다음과 같다.전위 순회(pre-order traverse)중위 순회(in-order traverse)후위 순회(post-order traverse) 트리 순회 예시 전위 순회(pre-order travers..

그래프 이론의 기초정점과 간선→ 정점과 간선들로 이루어진 집합을 “그래프(Graph)” 라고 한다.트리트리의 특징이진트리(Binary Tree)정 이진 트리(Full Binary Tree)완전 이진 트리(Complete Binary Tree)포화 이진 트리(Perfect Binary Tree)이진탐색트리(Binary Search Tree)이진탐색트리의 시간 복잡도는?그래프 구현과 탐색인접행렬간선 정보로부터 인접행렬 구현하기 (무향 그래프 == 양방향 그래프)인접 리스트간선 정보로부터 인접리스트 구현하기(무향 그래프)인접행렬 VS 인접리스트공간복잡도시간복잡도그래프가 희소할 때는 인접리스트, 조밀할 때는 인접행렬!맵과 방향벡터코딩테스트 문제에서 맵으로 표현된 그래프!상하좌우(4방향) 탐색과 방향 벡터방향 벡..

https://school.programmers.co.kr/learn/courses/30/lessons/42840문제 정의수포자는 어떤 패턴으로 정답을 찍는데 3명의 수포자 중 정답을 가장 많이 맞힌 사람이 누구인지 출력하는 문제이다. 접근 방법시험 문제가 최대 10,000문제로 완전 탐색을 해도 시간 초과는 걱정 없을 것 같아서 완전 탐색으로 접근했다. 문제 해설1번, 2번, 3번의 수포자의 찍기 패턴을 정의한다.1번부터 주어진 answers의 길이까지 1번, 2번, 3번이 정답을 맞췄는지 확인한다.1,2,3번의 패턴의 길이는 다르기때문에 각 패턴의 길이만큼 나눠주면 순서를 반복할 수 있다.즉, 1번 수포자의 6번 답은 6 & len(1번 패턴 길이) 로 접근할 수 있다. 풀이# 시험 최대 10,000..

4485번: 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485문제 정의주인공 링크는 현재 도둑루피가 가득한 N*N 크기의 동굴안에 젤 안쪽에 있다. ([0][0]에 위치)동굴의 반대편으로 가야하는데, 도둑루피를 지나면 도둑루피의 크기만큼 소지금을 잃게된다.한번에 상하좌우 1칸씩 이동할 수 있다.이 때 잃는 금액을 최소로 하여 동굴을 이동하려고 한다. 링크가 잃을 수 밖에 없는 최소 금액을 구하면 된다. 접근 방법‘잃을 수 밖에 없는 최소 금액’ = 동굴의 마지막 [N-1][N-1] 로 가는데 드는 비용을 최소화하는 경로로 가야한다.따라서 최단경로, 다익스트라로 풀 수 있다.다익스트라는 노드와 간선의 정보가 있어야 하는데, 이 문제에서는 다음과 같다.노드: 도둑루..

다익스트라(Dijkstra)다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 특정한 하나의 정점 → 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선은 포함할 수 없다. (현실세계에 사용하기 매우 적합한 알고리즘 중 하나이다.) 👉 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는?최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제가 큰 문제의 부분집합에 속해있다. 👉 그리디 알고리즘의 일종인 이유는?매번 ‘가장 비용이 적은 노드’를 선택하기 때문이다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다음의 그래프에서 노드 1에서 2,3,4 ..

개요누적합누적합 예제 문제 살펴보기2차원 배열에서 누적합구현간단한 구현 예제구현 시 고려해야 할 메모리 제약 사항 (Python)채점 환경 (Python)문제를 푸는 방법참조 개요오늘은 알고리즘의 가장 첫번째인 누적합과 구현에 대해서 공부한다. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다. 공부를 할 때 마다 새로운 지식을 계속해서 정리할 예정이다.누적합누적합이란 요소들의 누적한 합을 의미한다.어떤 배열을 기반으로 앞에서 부터 요소들의 누적한 합을 저장해서 새로운 배열을 만들고 이를 활용하는 방식이다. 누적합의 종류에는prefix sum: 앞에서부터 더하는 것 → 코딩테스트에 나오는 것suffix sum: 뒤에서부터 ..