이것저것

급한 상황이기에 이론은 뒤로 미루고 일단 Linq를 적극 활용하기로 했다. 연습 문제1. 백준 1431 : https://www.acmicpc.net/problem/1431 using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main(string[] args) { int N = int.Parse(Console.ReadLine()); List serials = new List(); for (int i = 0; i { if (a.Length != b.Length) return a.Length..

백트래킹?현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.  연습 문제 1. 백준 15649 : https://www.acmicpc.net/problem/15649using System.Text;var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);int n = input[0], m = input[1];int[] arr = new int[10];bool[] isUsed = new bool[10];StringBuilder sb = new StringBuilder();void method(int k){ if(k == m) { for (int i = 0; i  백트래킹의 핵심이라 주석을 작성해둔 ..

어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다. '제일 앞의 도미노를 쓰러트리게 되면 모든 도미노가 쓰러진다'는 전제가 존재할 때, 수학적 귀납법을 통하여 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'는 생각을 한다면 문제를 재귀적으로 접근한 것이다. 아무튼 특정 메소드 내부에 메소드 자신을 호출하는 방식의 메소드가 곧 재귀 메소드인 듯 하다. 재귀 메소드의 조건특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. 이러한 특정 입력을 Base condition 내지는 Base case라고 부른다. 모든 입력은 Base condition으로 수렴해야 한다.해당 조건이 없을 시 재귀 메소드는 결과를 내지 못하고 무한히 돌아가게 될 것이다. 참고 사항메소드..

Depth First Search (DFS)다차원 배열에서 각 칸을 방문(순회)할 때 깊이를 우선으로 방문하는 알고리즘이다. 반면 BFS는 너비 우선 방문 알고리즘이다.시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다.해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다.스택이 빌 때까지 2번을 반복한다.모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. DFS / BFS 차이점DFS도 BFS처럼 Flood Fill 기능이 필요할 때 사용할 수 있다. BFS와 최종적인 방문 결과는 똑같지만, 방문 순서에 차이가 존재한다.BFS의 경우..

Flood Fill그림판의 페인트 기능 마냥 외부 윤곽선을 따라 구분되는 영역의 색을 한번에 바꾸는 등의 기능을 뜻한다. BFS 알고리즘을 사용한 대표적인 기능이다. Breadth First Search (BFS)다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 이때 그래프는 정점과 간선으로 이루어진 자료구조이다.시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.큐에서 원소를 꺼내어 상하좌우로 인접한 칸에 대해 3번을 진행한다.해당 칸에 이미 방문한 상태라면 아무것도 하지 않고, 방문하지 않은 상태라면 방문했다는 기록을 남기고 해당 칸을 큐에 넣는다.큐가 빌 때까지 2번을 반복한다.모든 칸이 큐에 한번씩 들어가므로 시간복..

스택의 대표적인 활용으로 수식의 괄호 쌍, 전위/중위/후위 표기법, DFS, Flood fill등이 존재한다. 수식의 괄호 쌍?주어진 괄호 문자열이 올바른지 판단하는 문제이다.여는 괄호가 나올 시 스택에 추가닫는 괄호가 나올 시,스택이 비어있으면 올바르지 않은 괄호 쌍스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍스택의 top이 짝이 맞는 괄호일 경우 pop모든 과정을 마친 후 스택에 남아있는 요소가 있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍연습 문제 1. 백준 4949 : https://www.acmicpc.net/problem/4949 while(true){ var input = Console.ReadLine(); if (input == ".") b..

원소의 추가 O(1)원소의 제거 O(1)제일 앞/뒤 원소 확인 O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 연습 문제 1. 백준 10866 : https://www.acmicpc.net/problem/10866StreamReader sr = new StreamReader(Console.OpenStandardInput());StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());int n = int.Parse(sr.ReadLine());LinkedList deque = new LinkedList();for (int i = 0; i = 2) { b = int.Parse(s[1]); } if ..

큐?한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. First in first out (FIFO)의 특징을 가지고 있다. 원소의 추가 O(1)원소의 제거 O(1)제일 앞/뒤의 원소 검색 O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인/변경의 경우 원칙적으로 불가능 연습 문제 1. 백준 10845 : https://www.acmicpc.net/problem/10845 using System.Text;var count = int.Parse(Console.ReadLine());Queue queue = new Queue();for (int i = 0; i

스택?먼저 들어간 원소가 가장 나중에 나오는 First in last out (FILO) 자료구조이다. 스택, 큐, 덱은 모두 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있어 Restricted structure라고 부르기도 한다. 원소의 추가 O(1)원소의 제거 O(1)최상단의 원소 확인 O(1)최상단이 아닌 원소들의 확인/변경이 원칙적으로 불가능 연습 문제1. 백준 10828 : https://www.acmicpc.net/problem/10828using System.Text;var count = int.Parse(Console.ReadLine());Stack stack = new Stack();for (int i = 0; i

연결 리스트?원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.k번째 원소를 찾기 위해 O(k)의 시간이 필요하다.임의의 위치에 원소를 추가/제거는 O(1)이다.메모리 상에 원소들이 연속해 있지 않으므로 Cache hit rate가 낮지만 할당이 쉬운 편이다. 종류단일 연결 리스트 Singly linked list : 한방향 연결이중 연결 리스트 Doubly linked list : 양방향 연결원형 연결 리스트 Circular linked list : 처음과 끝 연결 (양방향, 한방향 둘 다 가능) 대표적 선형자료구조인 배열과 연결 리스트의 차이점 배열연결 리스트k번째 원소의 접근O(1)O(k)임의 위치에 원소 추가/제거O(N)O(1)메모리 상의 배치연속불연속추가적..