728x90 Sketch (Programming Language)/Algorithm4 시뮬레이션 알고리즘(백준 #1966) Implementation / Simulation 시뮬레이션(Simulation) 알고리즘은 흔히 구현(Implementation) 알고리즘과 특별한 구분없이 쓰인다. 구현 알고리즘이란 문제를 봤을때 떠오르는 해결책은 단순한데 이를 코드로 구현하는 것의 복잡도가 높은 알고리즘을 말한다. 백준에서 시뮬레이션 문제로 구분되어있는 1966번 프린터 큐 문제를 통해 알아보고자 한다. #1966 프린터 큐 우선 FIFO 기반인 큐를 통해 우선 순위를 부여하여 우선순위 큐와 같은 구현을 하고자 하는 문제이다. # 3 -> 3번 테스트 할 것 # 1 0 -> 문서는 1개, 0번 인덱스 문서의 출력순서는? # 5 -> 중요도 = 5 # 4 2 -> 문서는 4개, 2번 인덱스 문서의 출력순서는? # 1 2 3 4 -> .. 2023. 2. 16. 브루트포스 알고리즘(Backtracking, DFS, BFS) Brute Force Algorithm 브루트 포스 알고리즘(Brute Force Algorithm)은 컴퓨터 과학에서 올바른 해결책이 발견될 때까지 가능한 모든 해결책을 시도하여 복잡한 문제를 해결하는 데 사용되는 기술이다. 브루트 포스 알고리즘은 암호학, 비밀번호 크래킹, 최적화 문제 등 다양한 분야에서 사용될 수 있다. 그러나 브루트 포스 알고리즘에서 사용되는 세 가지 일반적인 테크닉인 백트래킹, 깊이 우선 검색(DFS) 및 폭 우선 검색(BFS)을 중심으로 코딩에서 브루트 포스 알고리즘이 어떤식으로 이용되는지 간단한 파이썬 코드 예제를 이용하여 보고자 한다. Backtracking Algorithm 백트래킹 알고리즘은 브루트 포스 알고리즘에 포함된다고 할 수도 있지만 어떻게 보면 거의 같다고 할 .. 2023. 2. 12. 난수 생성 algorithm Psuedo Random 우선 컴퓨터가 난수를 생성하기 어렵다는 것을 알아야한다. 컴퓨터는 사람과 달리 무의식적인 선택, 또는 우연에 의한 선택을 할 수 없기에 기본적으로 정해진 입력에 따라 정해진 값을 낼 수 밖에 없기 때문이다. 이를 결정적 유한 오토마타(Deterministic Finite Automata)라고 한다. 이는 컴퓨터가 하나의 입력에 대해 무조건 하나의 전이만 가능하기 때문이다. 따라서 컴퓨터는 특정한 방법으로 계산하거나 계속해서 변하는 값을 초기값으로 잡고 계산과정을 거쳐서 사람이 보기에 난수처럼 보이도록 하는 의사 난수(psuedo random)을 이용한다. 흔히 난수표를 만들어두고 그를 이용하여 의사 난수를 생성한다. 그러나 난수표가 정해진 순간 같은 수로 다시 돌아온다는 것이 확.. 2022. 11. 17. Dijkstra Algorithm Dijkstra Algorithm 다익스트라(Dijkstra) 알고리즘은 graph 자료구조에서 우선순위큐(Priority Queue)를 사용하여 방문하지 않은 노드를 방문하는 방식으로 최단 거리를 계산하는 알고리즘이다. 이를 이해하기 위하여 graph와 Priority Queue의 기본적인 개념을 이해하고 가려고 한다. Graph 그래프는 연결되어있는 원소간의 관계를 표현한 자료구조이다. 아래와 같이 다양한 유형으로 그래프를 분류할 수 있다. Priority Queue 우선순위 큐(Priority Queue)는 들어오는 순서대로 나가는 FIFO(First In First Out)라는 특징을 갖고있는 일반적인 큐(Queue)와는 다르게 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 .. 2022. 11. 1. 이전 1 다음 728x90
