티스토리

이것저것

검색하기

블로그 홈

이것저것

j1-09.tistory.com/m

공부를 함 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

패턴 정리 Strategy pattern동적 가능성이 있는 알고리즘군을 객체에서 분리함 (interface, 서브 클래스 활용) 어떤 행동을 사용할지 서브클래스에 맡김 Observer pattern Subject에 observer리스트를 저장해두고 data의 변화가 생길 때 observer들에게 알림이 가도록 함 subject에서 data를 push하는 방법과 observer들이 알림을 받았을 때 data를 알아서 pull하는 방법이 있음 Decorator pattern 추상구성요소, 구상구성요소, 추상데코레이터, 구상데코레이터의 구조를 가짐 COP법칙, 변경에 닫혀있고 확장에 열려있어야 함 Factory pattern 인터페이스를 추상생산자에 의지하며 실제 객체 생성은 구상생산자인 서브클래스에 일임 함 인스턴스 .. 공감수 0 댓글수 0 2024. 12. 9.
프록시 패턴 Proxy pattern특정 객체로의 접근을 제어하는 대리인을 제공 Client 객체가 Client 보조객체 (RMI stub) 에게 로컬 메소드 호출하듯 호출하고, 스텁은 서비스 보조객체 (RMI skeleton) 에게 호출을 전달하며 실제 로직 수행은 서비스 객체에서 이뤄짐 공감수 0 댓글수 1 2024. 12. 9.
반복자 패턴, 컴포지트 패턴 Iterator pattern#region Menupublic class MenuItem{ public string Name { get; } public string Description { get; } public bool IsVegetarian { get; } public decimal Price { get; } public MenuItem(string name, string description, bool isVegetarian, decimal price) { Name = name; Description = description; IsVegetarian = isVegetarian; Price = price; .. 공감수 0 댓글수 0 2024. 12. 5.
템플릿 메소드 패턴 Template method patternpublic abstract class Prepare{ public abstract void PrepareRecipe();}public abstract class CaffeineBeverage : Prepare{ public sealed override void PrepareRecipe() { BoilWater(); Brew(); PourInCup(); if(CustomerWantsCondiments()) AddCondiments(); } public abstract void Brew(); public abstract void AddCondiments(); .. 공감수 0 댓글수 0 2024. 12. 5.
어댑터 패턴, 퍼사드 패턴 Adaptor patternpublic class Duck{ public void Quack() { } public void Fly() { }}public class Turkey{ public void Gobble() { } public void Fly() { }}public class TurkeyAdapter : Duck{ private Turkey turkey; public TurkeyAdapter(Turkey turkey) { this.turkey = turkey; } public void Quack() { turkey.Gobble(); } public void Fly() { turkey.Fly(); }} Pacade patternpubli.. 공감수 0 댓글수 1 2024. 12. 4.
커맨드 패턴 Command pattern using System.Text;#region Basepublic interface Command{ public void Execute() { } public void Undo() { }}public class Light{ public void On() { Console.WriteLine("Light is on"); } public void Off() { Console.WriteLine("Light is off"); }}public class GarageDoor{ public void Up() { Console.WriteLine("Garage door is up"); } public void Down() { Console.WriteLine("G.. 공감수 0 댓글수 0 2024. 12. 4.
팩토리 패턴 Factory Pattern #region Pizzapublic class Pizza{ public void Prepare() { } public void Bake() { } public void Cut() { } public void Box() { }}public class VeggiePizza : Pizza{}public class ClamPizza : Pizza{}public class PepperoniPizza : Pizza{}public class CheesePizza : Pizza{}#endregionpublic class SimplePizzaFactory{ public Pizza CreatePizza(string type) { Pizza p.. 공감수 0 댓글수 0 2024. 12. 3.
데코레이터 패턴 Decorator Pattern#region Basepublic abstract class Beverage{ public string Description { get; set; } public abstract double Cost();}public abstract class CondimentDecorator : Beverage{ protected Beverage beverage;}#endregion#region Baveragepublic class Espresso : Beverage{ public Espresso() { Description = "Espresso"; } public override double Cost() { return 1.99; }}public class H.. 공감수 0 댓글수 0 2024. 12. 3.
옵저버 패턴 Observer Pattern#region Interfacespublic interface ISubject{ public void RegisterOb(IObserver o); public void RemoveOb(IObserver o); public void NotifyOb();}public interface IObserver{ public void Update(WeatherData wd);}public interface IDisplay{ public void Display();}#endregion#region BaseClassespublic struct WeatherData{ private float temp; private float humidity; pri.. 공감수 0 댓글수 0 2024. 12. 3.
전략 패턴 Strategy Pattern객체 클래스에서 동적인 알고리즘군을 분리함 공감수 0 댓글수 1 2024. 12. 3.
정렬 급한 상황이기에 이론은 뒤로 미루고 일단 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.. 공감수 0 댓글수 0 2024. 10. 21.
백트래킹 백트래킹?현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 연습 문제 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 백트래킹의 핵심이라 주석을 작성해둔 .. 공감수 0 댓글수 0 2024. 10. 18.
재귀 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다. '제일 앞의 도미노를 쓰러트리게 되면 모든 도미노가 쓰러진다'는 전제가 존재할 때, 수학적 귀납법을 통하여 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'는 생각을 한다면 문제를 재귀적으로 접근한 것이다. 아무튼 특정 메소드 내부에 메소드 자신을 호출하는 방식의 메소드가 곧 재귀 메소드인 듯 하다. 재귀 메소드의 조건특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. 이러한 특정 입력을 Base condition 내지는 Base case라고 부른다. 모든 입력은 Base condition으로 수렴해야 한다.해당 조건이 없을 시 재귀 메소드는 결과를 내지 못하고 무한히 돌아가게 될 것이다. 참고 사항메소드.. 공감수 1 댓글수 1 2024. 10. 15.
DFS Depth First Search (DFS)다차원 배열에서 각 칸을 방문(순회)할 때 깊이를 우선으로 방문하는 알고리즘이다. 반면 BFS는 너비 우선 방문 알고리즘이다.시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다.해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다.스택이 빌 때까지 2번을 반복한다.모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. DFS / BFS 차이점DFS도 BFS처럼 Flood Fill 기능이 필요할 때 사용할 수 있다. BFS와 최종적인 방문 결과는 똑같지만, 방문 순서에 차이가 존재한다.BFS의 경우.. 공감수 0 댓글수 0 2024. 10. 13.
BFS Flood Fill그림판의 페인트 기능 마냥 외부 윤곽선을 따라 구분되는 영역의 색을 한번에 바꾸는 등의 기능을 뜻한다. BFS 알고리즘을 사용한 대표적인 기능이다. Breadth First Search (BFS)다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 이때 그래프는 정점과 간선으로 이루어진 자료구조이다.시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.큐에서 원소를 꺼내어 상하좌우로 인접한 칸에 대해 3번을 진행한다.해당 칸에 이미 방문한 상태라면 아무것도 하지 않고, 방문하지 않은 상태라면 방문했다는 기록을 남기고 해당 칸을 큐에 넣는다.큐가 빌 때까지 2번을 반복한다.모든 칸이 큐에 한번씩 들어가므로 시간복.. 공감수 1 댓글수 0 2024. 10. 13.
스택 활용 스택의 대표적인 활용으로 수식의 괄호 쌍, 전위/중위/후위 표기법, DFS, Flood fill등이 존재한다. 수식의 괄호 쌍?주어진 괄호 문자열이 올바른지 판단하는 문제이다.여는 괄호가 나올 시 스택에 추가닫는 괄호가 나올 시,스택이 비어있으면 올바르지 않은 괄호 쌍스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍스택의 top이 짝이 맞는 괄호일 경우 pop모든 과정을 마친 후 스택에 남아있는 요소가 있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍연습 문제 1. 백준 4949 : https://www.acmicpc.net/problem/4949 while(true){ var input = Console.ReadLine(); if (input == ".") b.. 공감수 0 댓글수 0 2024. 10. 12.
덱 Double ended queue 원소의 추가 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 .. 공감수 0 댓글수 0 2024. 10. 11.
큐 queue 큐?한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 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 공감수 0 댓글수 0 2024. 10. 11.
스택 Stack 스택?먼저 들어간 원소가 가장 나중에 나오는 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 공감수 0 댓글수 0 2024. 10. 11.
연결 리스트 연결 리스트?원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.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)메모리 상의 배치연속불연속추가적.. 공감수 1 댓글수 0 2024. 10. 11.
배열 메모리 상에 원소를 연속하게 배치한 자료구조. 시간복잡도 O(1)으로 k번째 원소의 위치를 바로 계산 (확인 및 변경 등) 할 수 있다.타 자료구조와는 다르게 추가적으로 소모되는 메모리의 양이 거의 없다.메모리 상에 데이터들이 붙어있으므로 Cache hit rate가 높다.Cache hit rate란 캐시 적중률을 의미하며 명령이나 자료를 찾기 위해 캐시 메모리에 접근했을 때 자료가 존재하면 적중 Hit 되었다 하고 없다면 실패했다고 한다. 적중률은 적중횟수/총 접근횟수 이며 컴퓨터의 성능을 나타내는 척도로 사용된다.메모리 상 연속한 구간을 잡아야 하므로 할당에 다소 제약이 존재한다. 기능원소를 확인/변경 : O(1)배열 끝에 원소를 추가 : O(1)배열 끝 원소를 제거 : O(1)임의의 위치에 원소를 .. 공감수 0 댓글수 0 2024. 10. 11.
시간복잡도, 공간복잡도 시간복잡도 컴퓨터는 1초에 대략 3-5억 개의 연산을 처리할 수 있다. 따라서 시간 제한이 1초라고 한다면 3-5억 번의 연산 안에 답을 내고 종료되는 프로그램을 짜야 한다는 뜻으로 이해하면 된다. 입력의 범위를 보고 문제에서 요구하는 시간복잡도를 대략적으로 유추가 가능하다.N의 크기허용 시간복잡도N O(N!)N 25O(2^N)N 100O(N^4)N 500O(N^3)N 3000O(N^2logN)N 5000O(N^2) N 1,000,000O(NlogN)N 10,000,000O(N)그 이상O(logN), O(1) 문제 1N 이하의 자연수 중 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 프로그램을 작성하라. N은 5만 이하의 자연수이다.var n = int.Parse(C.. 공감수 0 댓글수 0 2024. 10. 9.
알고리즘 인덱싱 알고리즘을 공부하는 목적?코딩 테스트의 출제 의도 파악을 분명히 함'최적화'에 대한 이해개인 프로젝트의 퀄리티를 높임포트폴리오의 어필 방향을 확실히 함종류빅오 표기법 Big-O notation - 시간복잡도, 공간복잡도완전 탐색 Brute-force search탐욕적 기법 Greedy Algorithm분할 정복 Divide and conquer동적 계획법 Dynamic programming이진 탐색 Binary search파라메트릭 탐색 Parametric search깊이 우선 탐색 Depth-First search (DFS)너비 우선 탐색 Breadth-First search (BFS)백트래킹 Backtracking비트마스킹 Bit masking구간합 배열 Prefix sum에라토스테네스의 체 Siev.. 공감수 2 댓글수 2 2024. 10. 8.
자료구조 인덱싱 자료구조를 공부하는 목적?알고리즘 학습에 선행함 종류리스트 List배열 Array연결 리스트 Linked list스택 Stack큐 Queue덱 Double Ended Queue (Dequeue)그래프 Graph트리 Tree이진 검색 트리 Binary search tree우선순위 큐 Priority queue (PQ)유니온 파인드 Union-Find (Disjoint-set)세그먼트 트리 Segment tree (ST)최소 스패닝 트리 Minimum spanning tree (MST)머지 소트 트리 Merge sort tree퍼시스턴트 세그먼트 트리 Persistent segment tree 공감수 0 댓글수 0 2024. 10. 8.
(백준/C#) 약수, 배수와 소수 //5086두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.첫 번째 숫자가 두 번째 숫자의 약수이다.첫 번째 숫자가 두 번째 숫자의 배수이다.첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.using System.Diagnostics;int[] input() => Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);int[] i;while(true){ i = input(); if (i[0] == 0 && i[1] == 0) return; else { if ((i[0] % i[1] == 0)) Console.WriteLine("multiple"); el.. 공감수 0 댓글수 0 2024. 10. 4.
(백준/C#) 2차원 배열 //2738N*M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.int[] xy = Array.ConvertAll(Console.ReadLine().Split(), i => int.Parse(i));int x = xy[0];int y = xy[1];int[,] matrixA = new int[x, y] ;int[,] matrixB = new int [x, y];for (int k = 0; k int[] F() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);int[] nm = F();int[][] n = new int[nm[0]][];for (int i = 0; i //25669×9 격자판에 쓰여진 81개의 자연.. 공감수 0 댓글수 0 2024. 9. 30.
(백준/C#) 일반 수학 1 //2745B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35**진법 B가 15이고, N이 BAA라고 가정했을때.BAA = 11, 10, 10이므로 11 * (15^2) + 10 * (15^1) + 10 * (15^0) 이 되어서 2635가 정답이다.string[] input = Console.ReadLine().Split(' ');string num = input[0];int baseValue = int.Parse(input[1]);long answer = 0;for (int i.. 공감수 2 댓글수 0 2024. 9. 24.
(백준/C#) 심화 1 //25083Console.WriteLine(" ,r'\"7");Console.WriteLine("r`-_ ,' ,/");Console.WriteLine(" \\. \". L_r'");Console.WriteLine(" `~\\/");Console.WriteLine(" |");Console.WriteLine(" |"); //3003첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.int[] chessOrigin = { 1, 1, 2, 2, 2, 8 };int[] inputs = Array.ConvertAll(Console.Re.. 공감수 1 댓글수 0 2024. 9. 23.
(백준/C#) 문자열 //27866using static System.Console;string s = ReadLine();int i = int.Parse(ReadLine());WriteLine(s[i-1]); //2743using static System.Console;string s = ReadLine();WriteLine(s.Length); //9086using static System.Console;int count = int.Parse(ReadLine());string s = "";for (int i = 0; i using static System.Console;string x() => ReadLine();var s = x();while ((s = x()) != null) WriteLine($"{s[0]}".. 공감수 0 댓글수 0 2024. 9. 9.
(백준/C#) 1차원 배열 //10807using System;namespace TEST{ class Test { static void Main(string[] args) { int num = int.Parse(Console.ReadLine()); string[] v = Console.ReadLine().Split(); int key = int.Parse(Console.ReadLine()); int answer = 0; for (int i = 0; i //10871using System;namespace TEST{ class Test { static void Main(st.. 공감수 0 댓글수 0 2024. 8. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.