백준
-
[ 알고리즘 ] 백준 3078번 좋은친구프로그래밍/알고리즘 2019. 5. 3. 13:20
백준 3078번 좋은 친구 문제 링크 문제 접근 처음에는 단순히 큐를 이용해서 일일히 계산을 하면 되는 쉬운 문제라고 생각하고 시작했다. 정답이 나오는 단순한 코드는 금방 짤 수 있었지만, 제출결과 시간초과...... 결국 계속해서 다른 방법을 도전하다가 다른 분의 코드를 봤는데, 어떻게 이런 생각을 하시고 풀었는 지 놀라울 따름.......... 🤭 먼저 문자열의 길이는 2~20으로 주어졌으므로, 길이 20짜리 Queue 배열을 선언했다. 이 후 문자열의 입력이 들어오는데 이 때, 문자열의 내용은 중요하지 않으므로 바로 길이를 계산한다. 계산한 길이를 이용하여 앞에 선언한 큐 배열의 인덱스로 각 큐를 불러온다. 불러온 큐가 Empty 이면 바로 큐에 넣어주고, 그렇지 않다면 큐 안의 원소들을 앞에서부터..
-
[ 알고리즘 ] 백준 1935번 후위표기식 2프로그래밍/알고리즘 2019. 5. 2. 16:17
백준 1935번 후위표기식 2 문제 링크 아래 1918번 후위표기식을 풀고 바로 풀어서 그런 지, 바로 풀 수 있었다. 문제는 크게 어려움 없이, 두가지 경우로 나눠서 해결했다. 알파벳인 경우에는 해당하는 숫자를 바로 스택에 push해주었다. 연산자인 경우에는 스택에서 두 피연산자를 pop해준 뒤 ( 두번 ) 이를 연산자를 이용하여 계산하고, 이를 다시 스택에 push해주었다. 위의 두가지를 반복하여 답을 구하였고, System.out.format()함수를 이용하여 소수점 두자리 까지 표현하였다. 코드 package Algorithms; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; i..
-
[ 알고리즘 ] 백준 1918번 후위표기식프로그래밍/알고리즘 2019. 5. 2. 15:52
백준 1918번 후위표기식 문제 링크 이 문제는 Stack을 이용하는 문제로 평소 학교 공부에서도 많이 풀어보았다고, 생각해서 쉽게 풀 수 있을 것이라 생각했는데 쉽지 않았다. 결국은 다른 사람의 답을 참고하여 해결하였다. 생각해보니 평소에는 후위표기식으로 표현된 식을 계산하는 문제를 많이 풀어보았지, 주어진 식을 후위표기식으로 변환을 시키는 코드를 짜본 적은 없는 것 같다. 문제 풀이 입력받은 문자열을 차례로 비교하는데 총 네가지의 경우가 있다. 알파벳 연산자 열린 괄호 닫힌 괄호 각 경우에 따라서 출력하거나 스택에 넣거나, 스택에 있는 것을 꺼내주는 식으로 해결한다. 먼저 알파벳인 경우에는 그냥 바로 출력해준다. 나는 그냥 StringBuilder를 하나 만들어서 거기다 계속 append해줬다. 연산..
-
[알고리즘] 백준 2667번 단지번호붙이기 ( BFS )프로그래밍/알고리즘 2019. 3. 26. 18:11
백준 2667번 단지번호붙이기 문제 바로가기 오늘은 단지번호붙이기 문제를 풀어보았다. 원래 그림이나 이차원배열이 나오는 문제는 보기만해도 풀기 싫어서 넘기곤 했는데, BFS, DFS를 연습하면서 이제 그나마 거부감이 많이 줄었다. 문제는 2차원배열내에서 서로 이어진 단지가 몇개 있는지 찾는 문제로, 이와 비슷한 문제를 이전에 풀어본 경험이 있어서 쉽게 풀 수 있었다. 먼저 2차원배열을 잘 입력받아서 map이라는 배열에 넣어줬고, visited라는 2차원 boolean배열을 만들어 주었다. 이 후, 1이 있는 위치를 돌면서 bfs 함수에 넣어준다. 이 때 visited 값이 true이면 이미 다른 이어진 부분에서 체크를 했다는 뜻이므로 bfs함수를 돌지 않는다. for (int i = 0; i < N; i..