본문 바로가기

알고리즘

 (56)
백준 4811 <알약> 오랜만에 DP문제를 풀어보았다. 딱 봐도 총길이가 2N이면 30개를 한다고 치면 3814986502092304번... 당연히 시간 초과가 나는 문제 이런 문제는 일반적으로 DP라고 보면된다. 이 문제의 dp는 언제가 끝나는 조건인가? 당연히 한 조각 전체 알약이 없거나 한 조각이 하나와 반 조각이 없을 경우이다! 그리고 차곡차곡 dp에 값을 저장해서 값이 있다면 그 값을 return~하는 그런 문제이다! 문제 풀이 dp [][] 배열을 생성하고 현재 find 함수에 (알약-1,1)
백준 1938 <통나무 옮기기> 시뮬레이션 중에 삼성 A형에 나올만한 시뮬레이션이었다. 이문제의 중점을 어떤 것을 기준으로 어떻게 방문 처리를 하냐인 것이다. 해결 방법은 중점을 가지고 가로,세로,를 방문처리로 판단해주는 것이다. 풀이 방법 통나무 중앙을 기준으로 가로 세로를 판정 가로, 세로 각각 위,아래,좌,우 갈 수 있는지 확인 후 이동 후 큐에 넣기 가로, 세로 각각 중앙점을 기준으로 8방향 즉 대각선 까지 검사 후 회전 가능하면 회전 후 큐에 넣기 계속해서 시뮬레이션 진행~ 중앙점과 이동횟수 가로, 세로인지 판단할 변수를 class에 지정 그림처럼 맨끝의 지점을 찾은 뒤 가운뎃점을 찾는 과정 BFS에서 통나무가 위치할 통나무와 일치한지 찾으면 return~ 그림처럼 통나무가 세로로 되어있다면 중앙점에서 2위로 이동한 지점 검사..
백준 14466 <소가 길을 건너간 이유 6> 문제를 이해하는데 시간이 오래 걸렸던 문제 기본적으로 이렇게 소와 다리가 위치하고 있다. 주황색 소에서 하늘색 소로 가는 경우는 다리를 이용하지 않고 이렇게 이동할 수 있다. 그러나 주황색 소에서 초록색 소를 가려면 무조건 다리를 건너야 한다 파란색 소에서 초록색 소도 마찬가지이다. 이렇게 되면 다리를 건너야 하는 소들은 총 2쌍이다. 그러므로 이 문제는 각각의 소에서 다리를 이용하지 않고 다른 소들을 방문 할 수 있냐? 하는 문제이다. 결과적으로 쌍을 구하는 것이기 때문에 자기보다 뒤에 있는 소들만 계산해주고 앞에 있는 소들은 계산할 필요가 없다. 문제 풀이 각각의 소에서 BFS를 해서 다리를 이용하지 않은 완전 탐색을 한다. 자신보다 이후에 위치한 소들이 방문 되지 않았다면 count를 증가시킨다. ..
백준 6087 <레이저 통신> 우선순위 큐를 사용해봤다면 생각보다 어렵지 않았던 문제 우선순위 큐를 사용하여 거울을 작게 설치한 것부터 큐에서 꺼낼 수 있도록 한다! 문제 주의사항! 90도로 회전하거나 직선으로 가는 총 3가지 경우만 생각해준다.--> 즉 뒤로 반사되는 경우는 없음! 문제 해결 순서 시작점을 정해서 우선순위 큐에 넣어준다. 90도로 회전하게 되면 count를 1 증가시켜주고 직선으로 가게 되면 증가시켜주지 않는다. 큐에서 꺼낸 점이 종료점이면 result에 count값을 넣고 return 한다 현재의 좌표와 거울을 세운 갯수와 이전의 방향을 나타내기 위한 변수를 who라는 클래스에 선언! BFS를 돌면서 90도로 회전하게 되면 count를 1 증가시켜주고 직선으로 가게 되면 증가 X 이 부분에서 특이한 점이 있다면 중..
백준 2174 <로봇 시뮬레이션> 가장 기본적인 시뮬레이션.. 골드 5여서 쉽게 문제 읽다가는 틀렸습니다! 뜨는 그런 문제.. 문제는 간단하다 각자의 위치에서 명령대로 수행하다 벽을 만나거나 다른 로봇과 부딪히면 종료하는 문제! 이문제에서 주의해야 할 점은 !! 맵과 방향!! 이렇게 뒤집어서 보게되면 N이 동쪽을 가리키게 되고 일반적으로 생각했던 방향과 다르게 된다는 점!! 기존에는 dir [][] = {{ -1 , 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; 이렇게 동 서 남 북이었다면 dir [][] = {{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 이렇게 구성을 하는 것이다. 물론 첫 번째처럼 하려면 N이 방향 1이라고 줘도 되긴 한다! 나머지는 간단하다. 로봇의 위치와 방향..
백준 11000 <강의실 배정> 알고리즘 중 내가 어렵다고 생각한 그리디 부분의 문제이다. 이 문제에서 생각할 것은 얼마나 많은 수업이 겹치냐!이다. 그리디로 밖에 풀 수 없는 이유는 S와 T의 범위가 10의 9승으로 모든 N개 범위가 0부터 10의 9승이라면 10의 9승 곱하기 20만= 즉 엄청난 숫자가 되므로 당연히 X 다른 방법으로 N을 종료 시간 순으로 정렬해서 계속 비교해주게 된다면 N의 제곱! 20만의 제곱으로 시간을 마찬가지 로 터지게 된다. X 이 문제가 다른 문제에 비해 까다로웠던 이유는! 두 가지 단계를 거쳐 판단해야 했기 때문이다. 이 문제의 순서는 두 단계이다. 시작시간으로 정렬 우선순위 큐를 사용하여 종료시간이 짧은 순으로 나올 수 있게 한다!! 여기서 2번의 우선순위 큐를 사용한다고 생각을 하게 되는 것이 가장..
백준 17472 <다리 만들기 2 > 섬을 연결하는 최소 거리를 찾는 게 가장 어려웠던 문제... 알고리즘 순서를 말하자면 BFS를 이용해서 각지점마다 연결돼있는 섬을 만들어주고 섬의 개수 파악 각 지점에서 다른 섬 까지 이동할 수 있는 2를 넘는 최소거리 구해주기 크루스칼 또는 프림 알고리즘을 이용하여 총길이 구하기 (미니엄 스패닝 트리 MST)! 이렇게 총 3단계로 구성이 된다. 여러 알고리즘을 혼합했기 때문에 생각하기 좀 까다로웠던 시뮬레이션 문제! 1번을 구하는데 N*M 의 시간 총 100 2번을 구하는데 N*M*많이 해도 N*M을 한 번 더 곱한 수 3번을 하는데 섬의 개수가 최대 6이기 때문에 21... 절대 시간 초과는 날 수 없는 문제... 1번 구성 맵을 1에서 바꿔줬기 때문에 visit 배열을 따로 선언할 필요가 없다. 2..
정올 1681 <해밀턴 순환회로> www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 정 올의 해밀턴 순환 회로이다. 이문제는 기본적으로 백트래킹 문제이기 때문에 최대 12개의 배달 지를 순열로 놓으면서 거리를 계산하는 문제이다. 그러나 나는 새롭게 접근하기 위해 다익스트라 알고리즘을 응용하면서 비트 연산자를 더해 BFS로 문제를 접근해보았다. dis 클래스는 next는 다음 좌표이고 d는 다음 좌표까지의 총 이동거리를 나타내고 f는 비트 연산자로 visit을 나타낸다고 보면 된다. 이렇게 총 3가지로 구성된다고 보면 된다. 모든 곳을 다 탐색하고 다시 1로 돌아온 경우이고 최소의 거리를 출력하기 때문에 답을 입력하고 return을..
백준 2933 <미네랄> 조건이 많아서 처리해야 될 부분이 많은 시뮬레이션 문제였다. 문제의 단계는 왼,오 순서대로 그 위치에 가장 가까운 미네랄을 사라지게 하는 것. 제거한 위치를 중심으로 4 방형을 검사해 미네랄 이 있으면 그 부분이 떨어져 있는 것인지 확인! 떨어져 있다면 얼마나 내려갈 수 있는지 체크! 이 순서로 진행되는 것이다. 이 부분에서 내가 헷갈렸던 부분이 2번에서 왜 4방향으로 해야 하는가 였다. 위 , 오른쪽, 왼쪽 이렇게 해주면 된다고 생각했는데 예외인 부분이 있었다. 그림처럼 화살표 부분을 부수게 되면 아래의 미네랄 뭉치가 동 떨어져 자유 낙하하게 되는 것이다. 이러한 실수를 고쳐야 문제를 빨리 풀 수 있을 텐데 ㅠㅠ 문제에 수행되는 총 시간 복잡도는 부수는 횟수를 수행하는 게 최대 100*총 BFS를 하기..
백준 1753 <최단 경로> 더보기 이 문제를 풀면서 두 가지 방법으로 문제를 풀어 볼 것이다. 우선순위 큐를 사용하지 않은 최단 경로 우선순위 큐를 사용한 최단 경로 이렇게 두가지 방법으로 풀어 본 이유는 우선순위 큐를 사용하는 것이 과연 빠른가? 하는 마음에서 사용하기로 했다. 차이가 있는 부분은 가장 작은 최소를 어떻게 찾을 수 있을까 부분이다. 전체 정점을 돌면서 방문하지 않았고 최소 거리인 점을 찾는 부분이다. 우선 순위 큐를 사용하게 되면 방문했던 곳이면 넘어가 주면 되고 그렇지 않은 경우에 가장 작은 경로를 반환해 주기 때문에 쉽게 구현을 할 수 있다. 즉 우선 순위큐를 사용하지 않으면 v^2를 요구하게 된다면 사용하게 된다면 vlogv+ elogv 시간이 걸려 시간을 단축할 수 있다. 이런 식으로 흐름이 진행되게 된다..

티스토리툴바