알고리즘/문제풀이 - 백준

백준 14503 로봇 청소기

문제 : https://www.acmicpc.net/problem/14503 서론 시뮬레이션 문제. 풀이 시뮬레이션 문제이므로 문제가 시키는대로 잘 따라간다. 편의를 위해서 문제를 한가지 수정한다. 문제에서는 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽이라고 하는데 0은 북, 1은 서, 2는 남, 3은 동으로 수정했다. 청소기가 오로지 왼쪽으로만 회전을 하는데 왼쪽으로 회전하면 d가 1 증가하므로 (d+1)%4 를 쓰기 위해서다. (d+1)%4 는 d가 0, 1, 2, 3, 0, 1, 2 ...로 0~3만 가지도록 한다. 문제를 수정했으므로 방향을 입력받을 때도 수정해줘야한다. dy[4] = { -1, 0, 1, 0 } dx[4] = { 0, -1, 0,..

2019. 10. 17. 21:51
알고리즘/문제풀이 - 백준

백준 14888 연산자 끼워넣기

문제 : https://www.acmicpc.net/problem/14888 서론 완전탐색 문제. 풀이 연산자를 끼워넣을 수 있는 모든 경우의 수를 만들기 위해 재귀를 이용한 완전탐색을 이용한다. 이를 위해 n-1개의 연산자 모두를 순서 상관없이 연산자 배열에 넣는다. 그리고 재귀가 깊어질때마다 연산자를 하나씩 선택하고 선택된 연산자로 값을 연산한 후 연산된 값을 재귀로 계속 넘겨준다. 재귀가 끝에 다다르면 최대값과 최소값을 갱신한다. void dfs(int idx, int opIdx, int sum){ if(visited[opIdx] == 1) return; // 이미 선택된 연산자면 중복선택해선 안되므로 리턴 else visited[opIdx] = 0; if(idx == n-1) { // n-1개의 ..

2019. 10. 17. 19:47
알고리즘/문제풀이 - 백준

백준 14890 경사로

문제 : https://www.acmicpc.net/problem/14890 서론 정말 오래 걸린 문제. 3시간 넘게 푼것 같다. 시뮬레이션 문제라서 문제에서 시킨대로 풀면 된다. 버그 하나 뜨면 반복문과 조건문이 정말 많은데 중간에 나눌 수 있는 부분들도 아니라서 마치 엉킨 실타래 푸는 느낌이었다. 풀이 지도의 모든 열과 행을 조사해서 통과하는지 확인시켜주면 된다. 아래의 코드는 단 하나의 행이나 열이 통과하는지 확인하는 코드다. 이 코드에서 반복문이 얼마나 반복해야할지, 배열 인덱스의 정확한 위치 등 많은 조정이 필요하다. 이부분이 상당히 오래걸린다. void 확인(){ for(int i=0;i> n >> l; for (int i = 0; i < n; i++) { for (int j = 0; j < ..

2019. 10. 16. 22:32
알고리즘/문제풀이 - 백준

백준 14891 톱니바퀴

문제 : https://www.acmicpc.net/problem/14891 서론 시뮬레이션 문제. 시뮬레이션 문제는 정확한 문제 이해와 실수를 하지 않는게 정말 중요한데, 문제를 잘 못 이해했다. 모든 톱니바퀴가 돌기 전 상태에서 각각의 톱니바퀴 조건을 비교해야하는데, 1번 톱니바퀴가 회전하면 회전한 후의 상태로 조건을 비교해서 2번 톱니바퀴를 회전시키는 방식으로 이해했었다. 아이디어 회전할 톱니바퀴와 회전방향을 입력받으면 톱니바퀴들의 회전상태를 저장할 배열을 만든다. 회전할 톱니바퀴가 2번 톱니바퀴이고 회전방향이 오른쪽이라면 1 위와 같이 저장하고 오른쪽 톱니바퀴로 한칸씩 이동하며 회전가능한지 확인한다. 회전 가능하면 왼쪽 톱니바퀴의 -1을 곱한값을 입력한다. 회전할 수 없을때까지 반복한다. 1 -1..

2019. 10. 16. 14:03
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 디스크 컨트롤러

문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 서론 운영체제의 SJF(Shortest Job First)에서 착안한 문제인것 같다. 풀이 예제를 통해 작업시간이 짧은것부터 우선적으로 처리하는게 효율적이라는걸 유추할 수 있다. 그러나 작업시간이 짧은것을 먼저 처리하기 위해 하드디스크가 쉬고 있는데 이미 요청을 받은 다른 작업을 기다리게 하고 작업시간이 짧은것을 요청받을때까지 기다리지는 않는다. 요청을 받은 작업들 중 작업시간이 짧은것을 먼저 처리하기 위해 min-heap의 우선순위 큐를 이용한다. 시간이 0초부터 1초씩 증가하면서 jobs에 요청을 받은 작업이 있는지 확인한다. 아직 없다면 시간을 계속 증가시켜주고 있다면 요청받은 작업을 우선..

2019. 10. 11. 21:08
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 네트워크

문제 : https://programmers.co.kr/learn/courses/30/lessons/43162 서론 문제를 보고 연결된 네트워크 따라 탐색시키면 되겠다 생각하고 코드를 완성한 후 분류를 봤더니 DFS/BFS문제다. 그리고 다시 내 코드를 봤더니 BFS였다. BFS는 생각하지도 않았는데 자연스럽게 BFS로 풀이된게 뿌듯하다. 조금은 체화된것같다. 풀이 DFS/BFS문제 answer를 1 증가시키면서 1번 노드에 방문하면 방문표시를 한다. 그리고 방문한 노드와 연결된 노드가 있고 아직 방문을 안했으면 방문하고 방문표시를 한다. 더이상 연결된 노드가 없을때까지 탐색하면 하나의 네트워크를 만들 수 있다. 그리고 위의 과정 전체를 아직 방문하지 않은 노드가 남아있을 때까지 반복한다. 구현 // c..

2019. 10. 10. 23:15