CS/Alogrithm
-
3. Eratosthenes' Sieve (에라토스테네스의 체)CS/Alogrithm 2019. 3. 26. 21:03
소수 판별 알고리즘은 정말 많은데요.그 중에서도 가장 많이 쓰이고 간편한 '에라토스테네스의 체'입니다. 어떤 수 N에 대하여, 소수 판별하는 코드를 만들때 가장 나이브한 방법은 2부터 N까지 하나씩 다 나눠 보는 방법이 있습니다. 소수판별.java(Naive)12345678910111213141516171819import java.io.BufferedReader;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = I..
-
2 - 3. DFS 예제 (1260번: DFS와 BFS), DFS 응용CS/Alogrithm 2019. 3. 9. 21:14
백준 1260번(DFS와 BFS) 후.. 몇일 전에 작계 훈련 갔다오고, 또 지원서 쓰느라 이제야 포스팅 합니다. ㅠㅠ 이 문제는 한창 DFS를 잘 모르고 문제를 막 풀어댈 때 겁나 털린 문제입니다.정말 기본기만 할 줄 안다면, 바로 풀 수 있는 문제이고, DFS 연습 및 구조 파악하기 좋습니다.이 문제 말고도 N과 M이라는 문제 시리즈가 있는데, 저는 그 문제를 통해서 DFS 및 Back Tracking에 대해 제대로 알게 되었어요. 어쨌든 각설하고 문제부터 읽어 봅시다. 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정..
-
2. Breadth/Depth First Search (BFS/DFS: 너비/깊이 우선 탐색)CS/Alogrithm 2019. 2. 20. 21:14
정말 기본적으로 많이쓰이는 탐색 알고리즘 BFS, DFS 입니다. 제가 처음 알고리즘을 시작한것도 이 두 알고리즘으로 했습니다.개념이나 기본 코드 자체는 간단한 편이에요.저 같은 경우엔 초창기 이 알고리즘을 공부 할 때 조금만 난이도만 있어도 손도 못댄 기억이 납니다. 알고리즘도 수학과 마찬가지로 정확한 정의 또는 개념에서 시작한다고 생각이 됩니다.(사실 잘 알고 있다 생각했음에도 상당히 문제를 풀지 못했고.. 현재도 많이 부족하다고 느낍니다. ㅠㅠ) 부족한 저를 위해서라도 다시한번 개념을 잡고 가보겠습니다. ^____^; BFS DFS 완전 탐색 알고리즘그래프, 트리, 행렬 등에서 주로 사용이미 순서가 정해진 데이터를 탐색해 나가는 방법. BFS (Breadth First Search)너비 우선 탐색 ..
-
1. Binary SearchCS/Alogrithm 2019. 2. 10. 18:40
저는 원래 알고리즘을 탐색부터 시작했었는데... 이제와서 생각해보면 사실 그건 조금 안좋은 순서라고 생각이 됩니다.되도록이면 알고리즘 강의를 들으면서 그 커리큘럼에 맞춰 시작하시는게 좋지 않나 싶습니다.물론 현재도 완벽하게 탐색쪽을 잘 푼다 이런건아니지만, 그런 이유를 떠나서 기본기가 가장 중요한 것 같아요. 개인 적으론 DP, 수학 쪽을 주로 공부하면서 생각하는 폭을 넓히고탐색이나 그래프 파트에선 BFS, DFS 등을 접해보시는게 좋을거 같습니다. 그래서 수학이나 DP 부분을 먼저 건드려 보고싶습니다만제가 잘 알지 못하고 또 이해 못한 부분도 많아 이는 나중에 정리하고탐색과 그래프에서 그래도 꽤나 많이 쓰이는 알고리즘부터 정리를 해볼까 합니다. Binary Search 이분 탐색, 이진 탐색 두 부분으..