PLOD

1. 최장 맨해튼 거리 맨해튼 거리는 x,y 평면의 두개의 점에서 거리를 최단 거리로 구하는 문제이다. 맨해튼 거리 문제의 의미는 결국 좌표평면 위헤서의 어떤 구현이라는 걸 보여주는 단어이기 때문에 맨해튼 거리로 거리를 측정하라는 표현에 우리는 문제를 풀면서 좌표평면의 개념을 떠올려야 한다 완전 탐색 주어지는 수는 4개이기 때문에 좌표는 두개 밖에 생성이 안된다. 실제로 가능한 경우의 수는 24가지 정도이다. a,b,c,d를 무작위로 배열 한뒤 중복되지 않도록 for ~ if ~ continue로 처리 하여 각 점의 x,y 값을 정하고, distance 값을 구하기 위해 abs 함수를 이용한다. 나온 dist 값들 중 최대값을 구하기 위해 max 함수를 사용한다. S = list(map(int, inpu..

자료구조란? - 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체를 의미 - 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러가지 구현방법들 - 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨 - 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음 - 데이터 정돈 목적은 프로그램에서 저장하는 데이터에 대해 탐색 , 삽입 , 삭제 등의 연산을 효율적으로 수행하기 위해서 이다. 알고리즘이란? - 문제를 해결하는 방법을 순서대로 명확하게 기술한 것 - 알고리즘의 각 단계는 정확히 한가지 의미로 해석되어야 한다.(명확성) - 알고리즘의 모든 유효한 입력에 대해 올바른 해를 출력해야 한다.(정확성) - 유효한 입력이 주어지면 반드시 유한한 시간 내에 종료되어야 한다.(정지성) - ..

Stack : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료구조(Last In First Out)스택은 데이터를 일시적으로 쌓아 놓은 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)이다. 스택에 데이터를 넣는 작업을 push라 하고 스택에서 데이터를 꺼내는 작업을 pop이라고 한다. 스택은 push와 pop이 일어나는 곳이 한 군데 인데 이곳을 top 이라고 한다. 맨 아래 가장 먼저 push한 원소가 있는 곳을 bottom이라고 한다. push: 스택의 맨 위에 새로운 요소를 추가pop: 스택의 맨 위에 있는 요소를 제거하고 반환peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환isEmpty: 스택이 비어 있는지 확인package ch03_stack;import java.ut..

Graph그래프는 정점(데이터)과 간선(데이터 간의 거리)으로 이루어진 자료구조이다. 그래프는 BFS,DFS 같은 순회 알고리즘과 Djikstra 같은 최소경로알고리즘을 구현할 때 알아야 될 필수 자료구조이다.그래프는 정점(vertex,node)와 노선인 간선(edge)으로 이루어져 있다. 그래프는 간선의 방향성을 기준으로 나뉜다.그래프는 방향 그래프(Directed graph)와 무방향 그래프(Undirected graph : 양방향 그래프)가 있다. 그래프는 순환성을 기준으로 나눌 수도 있다. 순환 그래프와 비순환 그래프가 있다.인접 행렬을 통해서 그래프를 만들기인접 행렬2차원 배열을 사용하여 그래프의 정점들 간의 연결 관계를 표현행렬의 (i, j)위치에 간선의 유무를 나타내며,무방향 그래프의 경우 ..

1. BFS(Breadth - First -Search) : 너비우선탐색https://www.codecademy.com/article/tree-traversal Tree Traversal: Breadth-First Search vs Depth-First Search | CodecademyLearn about two standard tree traversal algorithms: breadth-first search and depth-first search.www.codecademy.com  시작 노드에서 인접 노드를 모두 방문하고 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복하게 된다.  BFS를 이용하게 되면 가중치가 없다는 가정 하에 처음 방문한 노드들의 집합이 최단 경로가 없다.최대한 넓게 ..