전체 글71

• [Algorithm] 백준온라인저지 2357번 최솟값과 최댓값 Java로 문제풀이!! (BOJ-2357) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 2357번 최솟값과 최댓값 문제를 풀어보겠습니다. 1. 문제 설명 문제에 대한 링크는 아래에 있으니 먼저 읽고 와주시면 감사하겠습니다. https://www.acmicpc.net/problem/2357 하나의 배열이 주어지고 해당 배열의 특정 구간에 대해서 최솟값과 최댓값이 무엇인지 출력하는 문제입니다. 이번 문제는 세그먼트 트리를 이용해서 접근하면 어렵지 않게 풀 수 있습니다. 세그먼트 트리에 대해서 모르신다면 문제풀이가 생각보다 어려워지므로 아직 세그먼트 트리에 대해서 모르신다면 제가 작성한 포스팅의 코드를 보시거나 다른 블로그에 세그먼트 트리에 대해서 학습하고 오시길 바랍니다. 아래는 제가 포스팅한 게시물입니다. [Algo.. Algorithm & Data Structure/문제풀이 2021. 6. 19.

• [Algorithm] 백준온라인저지 1016번 Java로 문제 풀이! (BOJ-1016) 안녕하세요 Coding-Knowjam입니다. 오늘은 에라토스테네스의 체를 응용한 문제를 한번 풀어보겠습니다. 1. 문제 설명 백준 온라인 저지에 있는 1016번 문제 링크는 아래에 있습니다. (문제 : https://www.acmicpc.net/problem/1016) 해당 문제는 에라토스테네스의 체를 사용해서 접근을 해야 합니다. 에라토스테네스의 체 알고리즘은 소수 판별에 많이 사용되는데요~ 현재 풀려고 하는 문제는 소수를 판별하는 것이 아니라 "제곱ㄴㄴ수"를 판별해야 하기 때문에 에라토스테네스의 체 알고리즘을 소수 판별이 아닌 제곱수를 판별하는 형태로 응용해서 사용해야 합니다. 또한 문제에서 주어지는 수의 범위가 1조 1백만까지 나타나므로 주의해야 합니다 그러면 문제를 한번 풀어보겠습니다. 2. Ja.. Algorithm & Data Structure/문제풀이 2021. 6. 17.

• [Algorithm] 세그먼트 트리(Segment Tree)를 Java로 구현해보자! !(with BOJ-2042 Java로 문제풀이) 안녕하세요 Coding-Knowjam입니다. 오늘은 세그먼트 트리를 Java로 구현해보도록 하겠습니다. 1. 세그먼트 트리 (Segment Tree) 세그먼트 트리는 이름에서도 나타나듯이 트리 형태의 자료구조를 사용합니다. 숫자가 저장된 배열이 존재할 때 해당 배열의 구간 합을 구하거나, 배열의 특정 인덱스의 값을 변경한 후에 다시 구간합을 구해야 한다면 세그먼트 트리를 사용하는 것이 시간 복잡도 측면에서 적합합니다. 세그먼트 트리에 대한 이론적인 설명은 백준 온라인 저지에 있는 게시물에 명쾌하게 정리가 되어있습니다. 그러므로 해당 게시글을 꼭 읽어보시길 바라며 세그먼트 트리가 무엇인지는 대충 아신다는 전제하에 Java로 코드를 구현해보겠습니다. 구현 코드는 예제를 들어서 해도 되지만 백준 온라인 저지에.. Algorithm & Data Structure/이론 2021. 6. 13.

• [Algorithm] BOJ-14890 Java로 문제풀이 (구현) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다. 문제의 링크는 아래에 있으니 문제를 먼저 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/14890 1. 문제 해설 난이도 : 골드 3 문제 접근 키워드 : 구현 사실 이번 문제는 이렇다 할 알고리즘보다는 문제에서 요구하는 제약조건에 맞게 동작하도록 구현을 하면 되는 문제입니다. 구현 문제는 개발자마다 코드가 다르기 때문에 얘는 이렇게 풀었구나 정도로 참고하시면 될 것 같습니다. 알고리즘이 특별하게 필요한 문제가 아니라서 본인의 스타일에 맞게 구현만 하시면 됩니다. 그럼 코드를 작성해보겠습니다. 2. Java 코드로 구현 package study.blog.codingnoja.. Algorithm & Data Structure/문제풀이 2021. 4. 24.

• [Algorithm] BOJ-1987 Java로 문제풀이 (Backtracking) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다. 문제 링크는 아래에 있으니 문제를 먼저 읽고 오시길 바라겠습니다. https://www.acmicpc.net/problem/1987 1. 문제 해설 난이도 : 골드 4 문제 해결 키워드 : DFS, Backtracking, 완전 탐색, 재귀, 스택 문제를 읽어보시면 결국 답을 찾기 위해서는 모든 경우의 수를 탐색해봐야 합니다. BFS와 DFS 둘 중 어떤 알고리즘을 선택해서 코드를 구현해도 답을 찾아낼 수는 있지만, BFS는 조금 더 깊게 생각해봐야 합니다. BFS의 경우 Queue 자료구조를 통해서 보통 구현을 하는데 모든 경우의 수를 탐색할 때, Queue의 메모리가 초과될 수도 있기 때문입니다. 현재.. Algorithm & Data Structure/문제풀이 2021. 4. 24.

• 

  [Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로) 안녕하세요 Coding-Knowjam입니다. 오늘은 다익스트라(Dijkstra) 알고리즘을 알아보겠습니다. 이론과 더불어 실제 구현을 백준 온라인 저지에 있는 문제풀이와 함께 할 예정이므로 문제를 미리 읽고 오시길 바라겠습니다. https://www.acmicpc.net/problem/1753 1. 다익스트라(Dikstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 방향성을 가지는 그래프에서 최단거리를 구할 때 자주 쓰입니다. 방향성을 가지는 그래프란 A에서 B노드로 이동은 가능하지만, B노드에서 A노드로는 이동할 수 없는 경우가 있는 그래프를 말합니다. 즉, 노드 간의 연결된 간선이 방향과 거리 비용을 가지고 있고, 시작 노드에서 다른 노드들까지의 최단거리 비용을 구할 때 사용할 수 있습니.. Algorithm & Data Structure/이론 2021. 4. 20.

• [Algorithm] BOJ-14502 Java로 문제풀이 (완전탐색) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다. 문제에 대한 설명은 따로 하지 않으니, 문제를 직접 보고 오시길 바랍니다. https://www.acmicpc.net/problem/14502 1. 문제 해설 난이도 : 골드 5 문제풀이 키워드 : 완전 탐색, BFS, 순열, 조합, 재귀 문제를 읽어보셔서 아시겠지만 목적은 기둥 3개를 빈 곳에 새로 심고 나서 바이러스가 퍼지지 않은 안전한 영역이 최대일 때의 값을 출력하는 것입니다. 그러면 우선 기둥 3개를 어떻게 심어야 안전한 영역의 개수가 최대가 될지를 고민해야 하는데, 문제의 조건 중 전체 영역의 크기가 최대 8 X 8 이므로 완전 탐색으로 해결해 볼 수 있습니다. 완전 탐색을 수행하기 위해 기둥이.. Algorithm & Data Structure/문제풀이 2021. 4. 18.

• 

  [Algorithm] DFS (Depth-first Search)를 Java로 구현해보자! 안녕하세요 Coding-Knowjam입니다. 오늘은 그래프와 트리를 탐색할 때 사용되는 DFS알고리즘에 대해서 알아보겠습니다. 1. DFS (Depth-first Search)란? DFS는 번역하면 깊이 우선 탐색이라고 합니다. 이름에서도 알 수 있듯이 연결된 노드를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들을 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색을 합니다. 사실 글로 설명하기는 좀 애매해서 그림과 같이 설명을 드리겠습니다. 위와 같은 그래프가 존재한다고 하고, 1번 노드부터 DFS탐색을 시작해보겠습니다. 1번 노드 방문처리 후 출력 (탐색 순서 : 1) 1번 노드에 인접한 노드 2번, 3번, 8번 중 하나를 방문해야 하는데 오름차순으로 방문하기로 가정하겠습니다. 2.. Algorithm & Data Structure/이론 2021. 4. 16.