자바40 [BOJ] 백준 1697번 - 숨바꼭질(with Java) 알고리즘 N에서 BFS를 시작한다. 가장 빨리 찾은 시간을 게산하기 위해서 idx와 time을 원소로 가지는 Node 클래스를 생성한다. 총 3가지의 행동 X-1, X+1, X*2을 할 수 있으므로 각각의 경우에 대해서 이동할 수 있는지 확인한 후에 방문 처리 및 time을 1 증가시켜서 큐에 넣어준다. 큐에서 꺼낸 node.idx의 값이 K와 일치하면 answer에 값을 저장하고 반복문을 탈출한다. 소스코드 문제링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2022. 6. 28. [BOJ] 백준 2644번 - 촌수계산(with Java) 알고리즘 1. BFS를 할 때마다 특정 번호의 촌수를 계산하기 위해서 Node 클래스를 선언한다. 2. 먼저 주어지는 사람의 번호를 src, 나중에 주어지는 번호를 dsc라고 정의한다. 3. 주어진 값들을 입력받을 때 아직 촌수를 알 수 없기 때문에 각 번호에 대한 촌수를 0으로 초기화한다. 4. BFS로 dst를 찾을 때까지 각각의 Node를 탐색하면서 cur.degree를 1씩 더하는 방식으로 번호들의 촌수를 초기화한다. 5. 큐에서 꺼낸 Node의 번호가 dst와 같으면 cur.degree를 반환한다. 6. 만약에 모든 Node를 탐색할 때까지 dst를 찾지 못하면 -1을 반환한다. 소스코드 문제링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각.. 2022. 6. 26. [BOJ] 백준 1260번 - DFS와 BFS(with Java) 알고리즘 1. DFS와 BFS로 탐색한 결과를 저장하기 위해서 'dfsAnswer', 'bfsAnswer'를 각각 리스트로 만든다. 2. 방문할 정점이 여러 개인 경우, 값이 작은 정점을 먼저 방문하므로 각각의 인접리스트를 오름차순으로 정럴현다. 3. DFS, BFS를 통해서 도출된 결과들을 각각 'dfsAnswer', 'bfsAnswer'에 넣어주고 탐색이 모두 끝나면 한번에 출력한다. 소스코드 문제링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2022. 6. 26. [프로그래머스] Level 1 - 신고 결과 받기(with Java) 문제 느낀점 Level1을 1시간 30~40분 간 풀면서 현타가 쎄게 옴 소스코드 출처 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 2022. 3. 22. [BOJ] 백준 16637번 - 괄호 추가하기(with Java) 알고리즘 브루트포스로 접근해서 풀어보다가 못풀고 시간만 보낼것 같아서 결국 구글링했다. 문제 분류에는 브루트포스만 적혀있지만 DFS + 재귀 조합을 통해서도 풀 수 있었다. '괄호를 채워넣지 않는 경우(1)'와 '괄호를 채워넣는 경우(2)' 2가지로 나눠볼 수 있겠다. (1)의 경우에는 total로 넘겨준 값을 유지하면서 오른쪽의 숫자들을 계속 연산해준다. (2)의 경우에는 total의 바로 뒤에 오는 숫자들에 대해서 먼저 연산해주고, total을 유지한채 다음 DFS를 수행한다. 만약에 주어진 연산자들을 모두 사용하면 total과 max값을 갱신시켜준다. 이후에 다음 DFS를 수행하지 않고 함수를 빠져나오면 된다. 예시 예제로 주어진 입력1의 '3+8*7-9*2'를 살펴보자. 괄호를 추가하지 않고 이 .. 2022. 1. 5. [BOJ] 백준 9205번 - 맥주 마시면서 걸어가기(with Java) 알고리즘 아이디어를 떠올릴 수 있다면, Floyd-Warshall 알고리즘을 이용해서 간단하게 BFS로 풀 수 있는 문제이다. 설계를 잘했다면 문제를 푸는 방법은 매우 간단하다. 우선, 각각의 위치를 정의해줘야만 하는데 좌표가 음수가 될 수도 있으므로 배열을 이용한 풀이는 어렵다. 따라서 현재 위치 x, y 좌표와 해당 위치의 방문 여부 정보 및 시작점과의 거리 정보를 담고 있는 클래스를 만들어준다. 또한, 모든 편의점과 목적지는 시작점과의 거리 정보를 무한대로 설정해주고 각각의 객체들을 리스트에 넣어준다. 이제부터 각각의 정점들에 대해서 BFS를 수행하면 되지만, 여기서 고려해줘야할 사항이 하나 있다. 문제에서 주어진 '맥주 한 박스에는 맥주가 20개 들어있다', '50미터를 가려면 그 직전에 맥주 한.. 2021. 12. 15. [BOJ] 백준 18310번 - 안테나(with Java) 알고리즘 잘못된 아이디어를 떠올려서 시간초과가 난 이유에 대해서 고민하다가 결국 풀지 못하고 구글링을 통해서 해결하였다. 처음에는 각각의 집에 대해서 다른 집들과의 거리의 합을 비교해서 합이 최소인 집을 구하는 방식으로 접근하였다. 하지만 입력이 최대 20만에 도달했기 때문에 시간복잡도는 O(N^2)로 시간초과가 나게 돼서 풀이에 실패하였다. 구글링을 통해서 다른 사람들이 푼 코드를 참고해보니 풀이가 의외로 간단하였다. 집들을 전부 오름차순으로 정렬시킨 후에 중간에 위치한 집을 찾는 것이 전부였다. 알고리즘을 위와 같이 짜게 되면, 어떤 테스트케이스가 주어져도 각각의 집에 대한 합이 최소값을 이루게 된다. 소스코드 문제링크 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200.. 2021. 12. 14. [BOJ] 백준 1874번 - 스택 수열(with Java) 알고리즘 풀이 시간이 상당히 오래걸렸다. 우선 리스트를 만들어서 입력받은 스택 수열을 하나씩 집어넣는 것으로 시작하였다. 처음에는 스택에 push, pop하는 과정을 통해서 연산을 뽑아놓고, 그 연산으로 다시 스택 수열을 만들어서 입력을 받은 리스트와 비교를 했기 때문에 과정도 번거롭고 시간복잡도가 크게 나왔다. 어떤 부분을 생략해서 시간복잡도를 줄일 수 있을까 고민한 끝에 비교하는 방식이 문제지 않을까하는 생각을 하게 됐다. 따라서 비교하는 방식을 과감하게 삭제하고 1부터 N까지의 숫자에 대해서 스택에 푸시를 하는데, 스택에 쌓인 모든 숫자에 대해서 맨 위에 있는 숫자가 현재 리스트가 가리키는 숫자와 일치하는 경우에만 스택으로부터 팝을 해주었고 리스트가 가리키는 숫자를 바꿔줘서 조건을 만족할 때까지 계.. 2021. 12. 14. [BOJ] 백준 14916번 - 거스름돈(with Java) 알고리즘 문제에서 궁극적으로 구하고자 하는 답은 거스름돈 N이 주어질 때, 거슬러주는 동전의 최소 개수이다. 따라서 다른 DP 문제들과 마찬가지로 N 이하에서의 DP 값을 모두 알아야만 한다. 이 문제에서 알아둬야할 부분은 '손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다' 이다. 다시 말해서 2원 또는 5원으로 거슬러줄 수 없는 경우가 존재한다는 뜻이며, 이 경우에는 -1을 넣어줘야만 한다. dp[0]을 구해보자. dp[0]은 거스름돈 0이 주어질 때, 거슬러주는 동전의 최소 개수이다. 하지만 거스름돈이 0이라면 거슬러줄 필요가 없으므로 거슬러주는 동전의 최소 개수는 0, 즉 dp[0] = 0이다. dp[1]은 거스름돈 1이 주어질 때, 거슬러주는 동전의 최소 개수이다. 거스름돈이 1인 경우에는 .. 2021. 12. 5. [Collection Framework] 자바(Java) LinkedList(연결 리스트)의 사용법 & 예제 정리 코딩 테스트 문제풀이에 자주 사용하는 컬렉션 프레임워크 중 하나인 'Linked List'에 대해 정리해보려고 한다. 개념 LinkedList는 'List' 인터페이스를 구현한 클래스이며 알고리즘 풀이에 자주 사용되는 컬렉션 프레임워크의 일종이다. 각 노드는 '데이터'와 다음 노드를 가리키는 '포인터'로 구성되며, 마지막 노드의 포인터는 'Null'을 가리키게 된다. 이러한 구성 때문에 아래 그림과 같이 각각의 노드들이 연쇄적으로 이어지는 구조를 이루게 된다. 선언 & 생성 import java.util.List // List 라이브러리 import java.util.LinkedList; // LinkedList 라이브러리 List list = new LinkedList(); // List 인터페이스를 .. 2021. 9. 15. 이전 1 2 3 4 다음
