본문 바로가기

Algorithm/백준28

[백준]BOJ 18352 특정 거리의 도시 찾기(자바/다익스트라/메모리초과 해결) 한 정점에서 다른 정점으로 가는 최단 거리의 문제입니다. 다음과 같이 모든 도로의 거리는 1이라는 조건이 있습니다. 이를 통해 BFS나 다익스트라로 문제를 풀어볼 수 있음을 알 수 있었습니다. 어려웠던 점 처음에는 인접행렬로 이 문제를 풀이했습니다. 제출했더니 메모리 초과가 났습니다. 이후에, 인접 리스트로 다시 문제를 풀었고, 다행히 성공할 수 있었습니다. 인접리스트로 단방향에 대해 저장하였습니다. 구현 큐에는 정점들을 넣었고, 현재 정점에 대해 경유지로 삼는 인접한 정점들을 방문하고 갱신한 뒤 이 정점을 큐에 넣었습니다. public class Main_18352 { public static void main(String[] args) throws IOException { BufferedReader .. 2023. 2. 4.
[백준] BOJ 2504 괄호의 값(자바/스택) 문제 풀이 방법 분배 법칙을 통해 괄호에 대한 연산 처리를 해주어야 하는 문제였습니다. 다음과 같은 예시를 통해 설명드리겠습니다. 다음 조건과 같이 값 * ( XY )가 값 * X + 값 * Y로 계산됩니다. 이는 분배 법칙에서 a(b + c)가 a*b + a*c로 전개되었던 것과 같습니다. 다음과 같은 예시로 문제 설명을 드리겠습니다. 이 경우에는 분배법칙에 따라서 2 * ( 2 + 3 * 3) 가 4 + 2 * 9 = 22가 된다. 따라서, 여는 괄호 '(' , '['인 경우 스택에 넣고, temp = temp * 2 또는 temp = temp * 3을 진행한다. 분배 법칙에 따라 곱셈을 하기 위해서이다. 닫는 괄호 ')' , ']' 인 경우 먼저, 올바른 괄호인지 확인한다. 올바르지 못하면 brea.. 2023. 1. 26.
[백준]BOJ 10799 쇠막대기 문제 조건 어려웠던 점 문제를 풀면서 여는 괄호와 닫는 괄호가 인접한 레이저인 경우에는 stack의 size만큼 더해주는 것은 생각을 했었습니다. 그러나, 그다음에 대해 생각해주지 못했습니다. 문제 풀이 왼쪽 끝은 여는 괄호 ‘ ( ’는 스택에 넣어줍니다. 레이저인 경우에는 쇠막대기가 잘립니다. 즉, 오른쪽 닫는 괄호 ')'인 경우 스택의 Top을 pop하여 레이저인 경우에는 스택 사이즈만큼 더해주면 됩니다. 다음과 같이 레이저(빨갛게 칠해놓은 부분)를 만나는 경우 쇠막대기(노랗게 칠해놓은 부분)는 스택 사이즈만큼인 3개로 나뉘는 것을 확인할 수 있습니다. 닫힌 괄호가 레이저가 아닌 경우, 즉 쇠막대기인 경우 남은 잘린 부분을 더해주면 됩니다. 남은 잘린 부분은 +1 해주면 됩니다. 다음과 같이 쇠막대기.. 2023. 1. 19.
[백준] BOJ 1541 잃어버린 괄호(자바) 오늘의 문제는 문자열을 파싱 하는 게 가장 중요한 포인트인 문제입니다. 문제 해결 방안 1. "-"를 기준으로 문자열을 파싱 하기 2. 각 분리된 문자 안에 있는 숫자를 전부 더해준 다음 뺄샘 해주기 다음과 같은 예시로 설명드리겠습니다. 10 - 50 + 30 + 20 - 10 + 100 이 문제에서 요구하는 최소를 구하기 위해서는 뺄샘을 기준으로 덧셈을 통해 큰 수를 먼저 만든 다음 뺄샘을 연산하면 최소를 구할 수 있습니다. 10 - (50 + 30 + 20) - (10 + 100) = 10 - 100 - 110 = -200 이렇게 뺄샘을 기준으로 덧셈 연산을 위해 저는 split 메서드를 사용하였습니다. split("\\-")을 기준으로 분리된 문자열은 다음과 같습니다. 10 50+30+20 10+1.. 2023. 1. 11.

티스토리툴바