알고리즘

[그래프 탐색] DFS와 BFS

그래프 탐색 📌 개념 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종 그래프를 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. → 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 DFS (Depth First Search) : 깊이 우선 탐색 📌 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. - 스택이나 재귀를 사용하여 구현 📌 그림으로 보기 STEP 1: A를 시작노드로 하겠습니다. STEP 2: A에 인접한 B, C가 스택에 저장됩니다. STEP 3: 스택의 맨 위에 있는 C를 꺼내서 Visited 배열에 넣습니다. ..

자료구조 기초 - 스택(Stack)과 큐(Que)

탐색 (Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다루게 된다. 대표적인 탐색 알고리즘으로 DFS(Depth-First Search)와 BFS(Breadth First Search)를 꼽을 수 있는데, 이 둘을 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 하므로 사전 학습으로 스택과 큐, 재귀 함수를 간단히 정리하고자 한다. 자료구조 (Data Structure) 란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그 중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심 적인 함수로 구성된다. 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : ..

[Python] 백준 14888번 : 연산자 끼워넣기

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5,..

[Python] 백준 9663번 : N-Queen

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. ✔ Solution - PyPy3 소스코드 n, ans = int(input()), 0 a, b, c = [False] * n, [False] * (2 * n - 1),..