Algorithm
-
[BOJ-JAVA] 2206 : 벽 부수고 이동하기Algorithm/Baekjoon Online Judge 2023. 7. 27. 17:51
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제에 대해 간략하게 설명해보자면 이동할 수 있는 위치 0과 벽으로 막힌 위치 1로 만들어진 N*M 크기의 맵에서 (1,1)에서 출발해 (N,M)에 도착하는 최단 경로를 구해야 한다 중요한 점은 한 칸에서 이동할 수 있는 곳은 상하좌우이며 최단 경로는 시작과 도착 칸을 포함한 칸의 개수 기준 이때, 경로상에서 딱 한번 벽을 부수고 지나갈 수 있음 문제풀이 💡 초기 접..
-
[BOJ-JAVA] 1918번: 후위 표기식Algorithm/Baekjoon Online Judge 2023. 4. 18. 21:13
문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 우리가 보통 수식을 쓸 때 사용하는 중위 표기법을 후위 표기법으로 변환하는 문제이다. 문제풀이 백준 문제 설명을 보면 중위 표기법을 후기표기법으로 변환할 때 괄호를 통해 우선 순위를 표시하고 계산하고 있다. 괄호를 이용한 문제의 경우 stack을 통해 해결할 수 있는 경우가 많다. 다만 stack을 어떻게 적용해서 풀 수 있는지 생각하는게 쉽지 않았다. 우선 괄호로 표시하는게 연산자의 우..
-
[BOJ-JAVA] 17299번: 오등큰수Algorithm/Baekjoon Online Judge 2023. 4. 17. 17:32
문제 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 수열이 주어질 때 각각 인덱스의 수에서 오른쪽에 있는 수 중 가장 개수가 많은 최좌측 수를 구하는 문제이다. https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.n..
-
[BOJ-JAVA] 17298번: 오큰수Algorithm/Baekjoon Online Judge 2023. 4. 17. 16:57
문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 수열에 주어질 때 각 인덱스를 기준으로 가장 오른쪽에 있는 인덱스의 수보다 큰 수를 찾는 문제이다. 문제 풀이 2차원 배열을 사용해서 푸는게 가장 쉬운 방식이지만 시간초과가 날 것이기 때문에 자료구조를 적절히 활용해야한다. stack을 사용해 문제를 해결하는 것까지는 확인을 했지만 stack을 어떻게 활용해야하는지 고민했던 문제이다. 초반에는 수열의 뒤에서부터 확인하며 오큰수를 찾는 방법을 구하려 했지..
-
[BOJ-JAVA] 10799번: 쇠막대기Algorithm/Baekjoon Online Judge 2023. 4. 17. 15:07
문제 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 다음과 같이 괄호로 이루어진 문장이 주어질 때 막대기의 개수를 세는 문제이다. 괄호는 레이저를 나타낸다. 괄호 안에 포함된 가장 안쪽 괄호가 레이저가 된다. 모든 막대기는 괄호를 포함한다. 막대기에 대해 가장 안쪽 괄호 기준으로 나누었을 때 막대기 개수를 구해야한다. 문제 풀이 보통의 괄호를 이용한 문제는 stack을 이용해 해결할 수 있다. "("가 나올 경우 stack에 push ")"가 나올 경우..
-
[BOJ-JAVA] 1158번: 요세푸스 문제Algorithm/Baekjoon Online Judge 2023. 4. 12. 20:48
문제 해결 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 큐를 이용해 쉽게 구현할 수 있는 문제지만, 초기에는 연결리스트만을 사용하여 구현하였고, 이후에 다시 큐를 사용해 구현하였다. 연결리스트 사용 iterator를 사용하여 K번째 마다 remove iterator가 끝을 가르킬 때 다시 정의해줘야 하는 번거로움이 있음 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Iterator; ..
-
[BOJ-JAVA] 1406번: 에디터Algorithm/Baekjoon Online Judge 2023. 4. 7. 15:48
문제 해결 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 연결리스트 사용 커서를 사용하여 이동하며 삽입, 삭제 등의 행동을 하기 때문에 연결리스트로 초기 구현했다. 하지만 시간초과가 발생! System.out.print 부분을 StringBuilder로 변경해줬지만 역시나 시간초과 cursor라는 변수를 두어 삽입, 삭제를 진행하는데 연결리스트는 처음부터 노드를 하나씩 살피기 때문에 시간이 오래걸리는 것 같아, iterator를 사용해보기로함 ..
-
[BOJ-JAVA] 10828번: 스택Algorithm/Baekjoon Online Judge 2023. 4. 6. 14:21
문제풀이 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택 개념만 알고있다면 문제 자체는 어렵지 않지만 초기 작성한 코드와 이를 개선시키면서 어떻게 작성해야 효율적인지 고민했다. 초기 Java 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; class ..