본문 바로가기

🧑🏻‍💻 Dev/알고리즘

 (14)
[백준] 20210번 파일 탐색기 (Java) 20210번 파일 탐색기 문자열 유형을 혼내주고 있는 도중 내가 혼나버렸다. 문제를 골랐는데, 항상 정답률을 보고 적당한 문제들을 골랐었는데 하하 왜 안 보고 골랐을까. 일단 골라버렸고, 코드는 작성해버렸고 문제를 풀었다. 1. 문제 분석 문제를 처음 보고나서 조건이 되게 많다는 것을 느꼈다. 얼핏 보기에는 뭔가 간단하게 그냥 조건 따라서 정렬하면 되는 문제라고 판단됐다. 그래서 선택했을지도... 둘 다 숫자인 경우 둘 중 하나만 숫자인 경우 둘 다 숫자가 아닌 경우 크게 이렇게 3가지 경우로 나눌 수 있었다. 둘 다 숫자라면? 십진법으로 두 숫자의 크기를 비교한다. 더 작은 숫자가 우선순위가 더 높다. 만약 두 숫자의 크기가 같다면, 앞에 0의 개수가 적은 것이 우선순위가 더 높다. 두 숫자의 크기도..
[백준] 16934번 게임 닉네임 (Java) 오랜만에 알고리즘이다... 알고리즘은 꾸준히 해야 하는데, 이 꾸준히라는 게 너무 어려운 것 같다. 코딩 테스트를 몇 번 보면서 느낀점이 있었다. "문자열" 문제 진짜 많이 나오는데, 아슬아슬하게 맨날 못 풀고 있는 것 같았다. 그래서 문자열 유형을 한번 혼내주기로 했다. 16934번 게임 닉네임 1. 문제 분석 문자열의 Prefix를 확인해야 하고, 이미 포함되어 있는지에 대한 여부도 확인하면서 문제에 접근해야 했다. 여기서 생각났던 알고리즘은 "트라이" 알고리즘이다. (사실 써보고 싶었습니다.) 왜 "트라이"인가? 새롭게 추가되는 문자열을 이미 추가되어 있는 문자열의 prefix에 해당하는지 확인을 해야 한다. 문자열 접두어 확인을 할 때는 "트라이" 알고리즘을 선택하면 빠르게 해결할 수 있다. 트라..
[백준] 1918번 후위 표기식 (Java) 1918 후위 표기식 1. 문제 분석 연산자의 우선순위를 생각해야 하는 문제입니다. 주의해야 할 점은 A + B + C의 경우에는 앞에 있는 +가 우선순위가 더 높기 때문에 ABC++가 아닌 (A + B) + C로 묶어서 AB+C+가 나와야 합니다. 그리고 추가로 괄호로 묶여서 제공되는 연산자의 경우에는 가장 우선순위가 높기 때문에 가장 먼저 처리해줘야 합니다. 알파벳에 해당하는 (A ~ Z)는 바로 문자열에 추가하고, 연산자(+, -, *, /)는 Stack에 저장해야 합니다. 2. 핵심 아이디어 Stack에는 연산자 들이 저장됩니다. 즉 먼저 들어온 연산자들은 아래쪽에 쌓이게 됩니다. 첫 번째 아이디어는 "("가 스택에 들어왔을 때입니다. "("는 일단 스택에 넣어줍니다. 그다음 연산자를 받아주고, ..
[백준] 2206번 벽 부수고 이동하기 (Java) 2206번 벽 부수고 이동하기 1. 문제 분석 0은 이동할 수 있는 칸, 1은 벽이 있어서 이동할 수 없는 칸입니다. (1, 1)에서 시작해서 (N, M)까지 가는데 최단 경로를 구해야 합니다. 이동은 상, 하, 좌, 우로 가능하고, 이때 벽(1)을 최소 한번 부수고 지나갈 수 있습니다. 문제에서 주어진 사항을 보고, BFS로 접근해야겠다는 생각을 했습니다. 방향이 존재하기 때문에 재귀적으로 구현을 했고, 벽을 1번 이상 부순 경우는 더 이상 나아가지 못하도록 막는 방법을 생각했습니다. 계속 틀렸다는 말이 나와서 2차원 배열 visited를 이용하여 문제를 변경해서 풀어봤는데, 이때는 시간 초과가 났습니다. 2. 핵심 아이디어 특정한 지점 (x, y)에 도달하는 데 있어서 벽을 1번 부수고 가는 경우와 ..
[백준] 1967번 트리의 지름 (Java) 1967번 트리의 지름 1. 문제 접근 특정 노드 2개를 선택해서 쭉 늘렸을 때, 가장 길이가 긴 두 노드를 찾아야 한다. 이 길이를 문제에서는 트리의 지름이라고 칭합니다. 1번 노드부터 탐색해서 가장 가중치가 큰 노드 하나를 선택합니다. 가장 가중치가 큰 노드는 반드시 트리의 지름의 한 점이 된다고 생각했습니다. 가장 가중치가 큰 노드를 하나 선택했으면, 해당 노드부터 BFS로 다시 탐색을 시작해서 가장 길이가 긴 값(트리의 지름)을 반환합니다. 2. 접근 과정에서 실수했던 부분 문제에서 "간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다."라는 부분이 있었습니다. 이 부분을 잘못 이해해서 다음과 같이 문제 접근을 ..
[백준] 1238번 파티 (Java) 1238번 파티 문제 풀러 가기 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 문제 분석 N명의 학생들은 X번 마을까지 갔다가 다시 돌아와야 한다. 이때 갔다가 다시 돌아오는 최단 거리를 구해야 한다. 각 마을에서 마을로 이동하는 데는 양의 가중치(거리)가 존재한다. 2. 생각해 보기 양의 가중치가 존재하기 때문에 다익스트라 아니면 플로이드 와샬을 고려해 본다. 플로이드 와샬 알고리즘은 O(N^3)의 시간 복잡도가 필요하다. 마을의 개수(N)가 최대 10^3이기 때문에 플..
[백준] 1931번 회의실 배정 - Java 백준 1931번 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 📖 문제 그리디 알고리즘의 대표적인 예시 문제라고 해도 될 문제입니다. 그래서 풀이에 대해서 조금 정리해보려고 합니다. 🔎 접근 방법 회의 일정에는 시작 시간과 종료 시간이 존재합니다. 회의 일정은 겹치면 안되고, 최대한 많은 회의를 진행해야 합니다. 위 조건을 생각해봤을 때, 이전 회의 일정의 종료 시간과 겹치지 않아야 하고 이후 일정의 시작 시간과 겹치지 않아야 합니다. 즉, 회의 일정을 종료 시간 기준으로 오름차순 정렬하여 종료 시간이 빠른 일정부터 해결해나가면 정답에 접근할 수 있습니다. 1. 회의 일정을 저장할 수 있는 클래스 선언 후 Co..
[백준] 1260번 DFS와 BFS 자바 DFS 문제 따로 BFS 문제 따로 풀어본 적은 있는데 한 문제에서 동일한 그래프로 DFS와 BFS를 모두 사용해야 하는 문제였습니다. 🔗 문제 링크 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🔍 문제 분석 첫 째줄에 정점의 개수(N, 노드의 개수)와 간선의 개수(M) 그리고 탐색 시작 정점(V)이 공백으로 주어집니다. 그다음 간선의 개수(M)만큼의 입력이 주어지고, 각 입력 줄에는 연결되어 있는 No..

티스토리툴바