프로그래밍/알고리즘
-
[ 알고리즘 ] 백준 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..
-
[알고리즘] 알고스팟 소풍 PICNIC프로그래밍/알고리즘 2019. 3. 22. 15:24
알고스팟 소풍 PICNIC 문제 바로가기 백트래킹으로 문제를 해결하였다. 보통 이런식으로 모든 방법의 수를 구하는 방법은 백트래킹으로 구하는 경우가 많은 것 같다. 이와 반대로 가장 먼저 도달하는 방법을 구하는 경우는 BFS가 많은 것 같은데... 이것도 더 익숙해져서 문제를 바로바로 어떤식으로 풀지 머릿 속에 나올 정도가 됐으면 좋겠다.... 먼저 친구관계를 저장해줄 friends 라는 이차원 boolean배열을 만들어서 친구관계를 저장하였고, 짝이 정해졌는 지 확인해줄 visited라는 boolean 배열도 만들어 주었다. 이 후 재귀함수를 만들어서 아직 짝이 없는 친구들을 짝을 주어지는 식으로 백트래킹을 해줬다. 구현 코드는 아래와 같다. /** * https://algospot.com/judge/..
-
[알고리즘] 알고스팟 BOARDCOVER 게임판 덮기 문제프로그래밍/알고리즘 2019. 3. 22. 14:26
알고스팟 BOARDCOVER 문제 바로가기 최근 취업준비로 알고리즘 공부를 꾸준히 하려고 노력하고 있다. DFS, BFS, 백트래킹 문제들을 위주로 풀어보려고 하고 있는데 생각보다 쉽지 않은 것 같다. 한 문제를 푸는데 한시간 이상 걸리는 경우가 다반사인데 실제 코딩테스트에서는 한문제를 30~1시간이내에 풀어야 하기때문에 주의해야겠다. 이번 문제는 알고스팟에서 문제를 보다가 _난이도 하 _ 라는 말에 덥석 문제를 풀기 시작했는데.... 나에게는 난이도 하가 하가 아니었다는 사실...ㅠㅠ 문제를 읽어보고 처음엔 백트래킹을 이용하여 금세 풀 수 있을 것이라 생각했는데 생각보다 일일히 바꿔주는 부분을 구현하는 데 오래 걸려서 결국 남들의 풀이를 참고하여 풀었다. 다행히 백트래킹을 사용하여 푸는 것이 맞았다 하..
-
[알고리즘] DP 다이내믹 프로그래밍 Dynamic Programming프로그래밍/알고리즘 2019. 1. 9. 16:42
동적 프로그래밍 DP(Dynamic Programming) 는 예전에 학교 알고리즘 시간에도 배웠지만, 잘 이해가 가지않아서 따로 다시 공부를 하려고 알고리즘 강의를 보게되었다. 이 글은 을 보면서 혼자 정리한 글이다. 문제 해결 방법 Brute-Force Approach Divide And Conquer Approach Dynamic Programming Approach Greedy Approach => 특별히 어떤 알고리즘이 좋다고 할 수는 없다. 상황에 맞는 접근 방법을 사용하자! DP 특징 주어진 문제를 하위로 나누어서 해결 문제를 작은 단위로 쪼개어서 생각한다는 것은 Divide and Conquer랑 비슷하지만 문제간의 관계가 다름. (하위 문제 끼리 종속성을 가지면 DP를 사용하는 것이 좋다..
-
[알고스팟] RUNNING MEDIAN 알고리즘 풀이(?)프로그래밍/알고리즘 2018. 12. 31. 11:17
최근 취업 준비를 하면서 알고리즘 문제를 공부할 필요성을 느껴서 문제를 풀어보고 있다. 몇몇 문제는 내가 상상조차 불가능해서 손도 못대는 경우도 있지만... 일단 노력해보고 있다...허허 너무 간단히 푼 문제말고, 어렵게 느껴졌던 문제나... 새롭게 알게된 경우는 블로그에 풀이?를 올려서 나중에 다시 볼 수 있도록 올려볼 생각이다. 오늘 푼 문제는... 문제 한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다. 한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 ..