Algorithm & Data Structure/문제풀이47

• [Algorithm] 백준온라인저지(BOJ) 14888번 연산자 끼워넣기 Java로 문제풀이!! (Backtracking) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 14888번 연산자 끼워넣기 문제를 풀어보겠습니다. 1. 문제 설명 문제에 대한 링크는 아래에 있으니 문제를 먼저 꼭 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/14888 문제를 읽어보시면 아시겠지만 주어진 숫자와 연산자를 통해서 얻을 수 있는 최댓값과 최솟값을 구하면 되는 문제입니다. 주어진 숫자의 순서를 바꿀 수는 없으므로, 연산자의 조합을 통해서 문제를 해결하면 됩니다. 어떤 조합이 최댓값인지 최솟값인지 판단을 하는 게 중요한데, 애초에 주어진 숫자와 연산자의 개수가 많지 않기 때문에 모든 경우의 수를 확인해서 해결할 수 있습니다. (백트래킹, 브루트 포스 등등) 저는 연산자를 나열하는.. Algorithm & Data Structure/문제풀이 2021. 7. 15.

• [Algorithm] 백준온라인저지 13460번 구슬 탈출2 Java로 문제풀이!! (BOJ-13460) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 13460번 구슬 탈출 2 문제를 풀어보겠습니다. 해당 문제는 백준 온라인 저지 삼성 SW 역량테스트 기출문제집에 들어있는 문제입니다. 1. 문제 설명 설명에 앞서 아래에 있는 링크를 통해서 풀어볼 문제를 읽어보고 오시길 바라겠습니다. https://www.acmicpc.net/problem/13460 해당 문제는 빨간 구슬이 탈출하는데 보드판을 몇 번 움직였는지를 구하는 문제입니다. 기본적으로 이런 문제는 BFS알고리즘을 통해서 접근을 하는 것이 좋다고 생각합니다. BFS알고리즘을 통해서 보통의 탈출 문제는 문제에서 요구하는 객체에 대한 이동 횟수를 구하기 마련인데 해당 문제는 빨간 구슬과 파란 구슬이 동시에 움직여야 하므로 .. Algorithm & Data Structure/문제풀이 2021. 7. 12.

• [Algorithm] 백준온라인저지 1759번 암호 만들기 Java로 문제풀이!! (BOJ-1759) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지 1759번 암호 만들기 문제를 풀어보겠습니다. 1. 문제 설명 해당 문제의 링크는 아래에 있으니 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/1759 문제 레벨 : 골드 5 문제 키워드 : 백트래킹, 순열 조합 문제에서 요구하는 조건은 2가지입니다. 1. 패스워드는 사전 순서로 정렬되어있을 것 2. 모음 1개 이상, 자음 2개 이상으로 구성되어있을 것 문제를 풀기 위해서는 제시하는 조건을 만족하는 경우의 수를 모두 출력해야 합니다. 경우의 수를 모두 구하는 방법은 여러 가지가 있겠지만, 저는 순열을 구하는 방법을 조금 응용해서 구현하였습니다. 정답처리를 받고 나서 다른 사람들의 정답을 보니까 조합을 .. Algorithm & Data Structure/문제풀이 2021. 6. 24.

• [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] 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] 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] BOJ-14503 Java로 문제풀이 (구현) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다. 문제 링크는 아래에 있으니 먼저 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/14503 1. 문제 해설 문제 난이도 : 골드 5 알고리즘 분류 : 구현 문제 난이도는 골드 5로 어렵지 않은 편이며, 풀이 또한 문제에서 제시한 조건에 따라 구현만 하면 됩니다. 구현할 때 생각을 좀 해야 하는 부분이 로봇청소기가 방향성을 가지고 있다는 점입니다. 이 부분을 제외하고는 BFS에서 상하좌우로 움직이면서 최단거리 세는 것과 비슷했던 것 같습니다. 그러면 코드를 살펴보겠습니다. 2. Java 코드로 구현 우선은 다음과 같이 로봇청소기 클래스를 하나 만들어주겠습니다. // main .. Algorithm & Data Structure/문제풀이 2021. 4. 14.

• [Algorithm] BOJ-7562 Java로 문제풀이 (BFS) 안녕하세요 Coding-Knowjam입니다. 오늘은 BFS알고리즘을 이용해서 문제를 풀어보겠습니다. 백준 온라인 저지에 있는 문제를 풀어볼 예정이며 문제와 관련한 내용은 링크를 참조하시면 되겠습니다. https://www.acmicpc.net/problem/7562 1. 해결 아이디어 문제 자체는 기본적인 BFS를 구현할 수 있다면 어렵지 않게 풀 수 있습니다. 문제를 풀기 위한 아이디어는 다음과 같습니다. 나이트가 이동하는 좌표를 계산할 수 있도록 move배열 선언 나이트가 방문한 좌표는 다시 방문하지 않음 2. Java 코드로 구현 우선 코드로 구현할 때 아마 개발자마다 성향이 다르겠지만 저는 2차원 배열 안에서 움직이는 좌표를 계산할 때 클래스를 따로 선언해주는 것이 편해서 이번에도 클래스를 하나 .. Algorithm & Data Structure/문제풀이 2021. 4. 13.

• 

  [Algorithm] BOJ 2206번 - 벽 부수고 이동하기 (Java) 안녕하세요 coding-knowjam입니다. 오늘은 알고리즘 문제를 풀어보겠습니다. 문제는 백준 온라인 저지에 있는 2206번 문제입니다. 문제에 대한 내용은 아래 링크를 통해서 읽어보시길 바라겠습니다. https://www.acmicpc.net/problem/2206 1. 문제 파악 및 해결 방법 1.1 목적 (1,1) -> (N, M)까지 이동할 때의 최단거리 구하기 1.2 조건 1. 맵에서 0으로 된 곳은 이동 가능 2. 맵에서 1로 된 곳은 벽이 있어서 이동 불가능 3. 이동하면서 벽을 1번은 부술 수 있음 4. 이동 가능한 범위는 상하좌우로 인접한 칸으로만 이동 가능 5. (1,1)과 (N, M)은 항상 0이고, 최단거리에 포함해서 계산하며 이동거리는 칸마다 1 임 6. (N, M) 지점에 도착.. Algorithm & Data Structure/문제풀이 2021. 2. 7.