본문 바로가기

알고리즘

 (56)
백준 18513 <샘터> 치킨 집의 위치에서부터 BFS를 하는 문제! 생각보다 어렵지는 않았지만.. 그놈의 실수.. 실수.. ㅠ 접근 방법만 알게된다면 쉽게 풀 수 있는 문제였다. 문제를 먼저 이해하자고 하면 치킨집에서 가까운 순서대로 집을 놓고 개수를 구하는 것이다. 즉 가까운 곳부터 집을 놓는다 --> 너비 탐색 이렇게 되는 것이다. 이 문제에서 주요하게 생각해야 하는 점은 범위!! 총 거리의 합이 int형이 아니고 long 형의 범위가 된다는 것을 주의해야 한다! 이것 이외에도.. 메모리... 초과를 주의하자.. 이놈의 습관 때문에 방문처리를 해주는 visit함수를 boolean 형이 아닌 int 형으로 사용한다면... 메모리 펑... 펑... 초과를 하게 된다. 위에 num을 저렇게 크게 잡아준 이유는 음수에도 위치가 놓..
백준 2206 <벽 부수고 이동하기> 이전의 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net 이 문제를 풀기 전에 추천했던 문제이다. 이 문제의 중점은 1번 뚫은 지점과 그렇지 않은 지점 방문처리를 어떻게 해주냐?이다. 이 중점의 답은 방문처리하는 vistit 2차원 배열을 안 뚫은 것을 체크하기 위한 하나, 뚫은 것을 체크하기 위한 하나 총 2개로 3차원 배열을 만드는 것이다. 이 클래스는 x,y 좌표와 시간을 담은 t , 벽을 뚫은 횟수를 담은 num으로 구..
백준 2615 <오목> DFS를 사용하는 완전 탐색이다. 5목이 아닌 6목 그 이상이 되는 예외 상항만 처리해주면 되기 때문에 생각보다 어려운 문제는 아니었다. 다만 문제를 해결하면서 시간 복잡도를 최소화하는 방법을 찾는데에 집중했던 문제였다. 시간을 줄이기 위해 이문제에서 사용된 방법은 바둑돌이 놓인 지점에서 이렇게 8방향을 탐색하는 것이 아닌 5목이 된다면 출력을 하게될 바둑돌의 좌표는 가장 왼쪽 그리고 가장 위쪽에 있는 좌표이기 때문에 이렇게 4방향만 검사를 해주게 되면 출력할 좌표를 쉽게 구할 수 있고 시간을 간편화 할 수 있다. 총 20*20의 맵이기 때문에 2중 for문을 사용해주었고 그 지점이 흑돌 또는 백 돌일 때 탐색을 실행시켜주었다. 각 돌의 지점에서 시작점을 포함해 5번을 이동하면서 이동한 지점의 돌이 같을..
백준 15961 <회전초밥> 일반적으로 알고 있는 투 포인터 문제이다. 물론 투 포인터라는 개념을 알고 있지 않으면 풀 수 없는 문제이다. 투 포인터라고 생각하게 된 이유는 접시의 수가 3000000으로 300만 개 연속으로 먹는 접시의 수가 3000으로 각각을 시작점으로 두고 3000번간다고 치면 300만*3000 90억이라는 어마어마한 수가 나오기 때문에 당연히 안 될 것이라고 생각했기 때문이다. 문제의 알고리즘을 이해하자면 이렇다 총 30가지 종류의 초밥이 있기때문에 체크를 해줄 배열을 만들고 시작점으로부터 연속해서 뽑을 때까지 체크를 해준다 현재는 4개까지 고를 수 있기 때문에 이렇게 3가지 종류의 초밥을 먹을 수 있게 된다. 이 이후에는 시작점으로부터 한 개씩 줄이고 끝점인 30의 위치부터는 증가시키면서 계속 이런 식으로 ..
백준 3109 <빵집> 이 문제는 DFS 문제임과 동시에 어떻게 하면 갔던 곳을 방문하지 않게 할까? 가 주요한 문제이다. 이 문제를 해결하기위해서는 두 가지 신경 써줘야 하는 부분이 있었다. 길을 연결 하고 나서 돌아갈 때 처리 방법 길을 연결 하지 못했다면 돌아갈 때 처리 방법 첫 번째 방법은 return 값을 boolean형으로 선언해서 true로 리턴하게 하면 된다. 다른 방법은 flag를 한 개 선언해서 이용해주면 된다. 이렇게 처리해 주지 않으면 이렇게 다음 빈 공간으로 이동하기 때문에 원래 값은 1이 되어야 하는데 2가 출력되게 됩니다. 두 번째 방법은 이미 방문했던 곳을 다시 방문할 수 없게 방문처리를 계속하는 것입니다. 그렇지 않으면 이전에 방문했지만 방문 표시를 제거해줬기 때문에 그 지점을 다시 방문하게 되어..
백준 1194 <달이 차오른다,가자> 우선 문제에서 이동 횟수의 최솟값을 구하라고 했기 때문에 BFS를 이용해야 하는 문제이다. 그리고 한가지 더 주의해야 할 점은 각각의 이동 시마다 가지고 있는 키를 알고 있어야 하는 문제이다. 각각의 가지고 있는 키의 정보를 저장하기 위해 key[] 배열을 가지고 있어도 되지만 크기를 줄이기 위해 비트 연산을 사용하도록 하는 문제이다. 비트 연산을 알지 못하면 어려운 문제이다. 전체적인 맵에서 각각의 키를 가지고 있는지 표시하기위해 1
비트 연산자를 이용한 순열과 부분집합 비트 연산자의 기본을 이해하기 위한 설명 및 사용법 비트 연산자를 사용하는 이유가 무엇인가? 일반적으로 비트 연산자는 이미 자신이 방문한 곳을 체크해주기 위한 boolean배열을 이용해서 나타내는 곳에 사용한다. 하지만 단순히 비트연산자를 방문한 곳을 체크해주기 위한 용도로 사용된다는 것은 이해가 어렵다. 예를 들어 총 10곳의 방문체크를 해줘야 하는 곳을 만들게 된다면 boolean visit [10]; 이렇게 하면 쉽게 해결될 것이다. 그렇다면 이것을 비트 연산자로 나타내게 되면 0000000000 이렇게 총 10자리가 되어 int형으로 나타나게 될 것이다. 이렇게 하면 int형은 4바이트 boolean은 10바이트 6바이트 밖에 차이가 나지 않는다. 그렇다면 굳이 이 6바이트 차이 때문에 비트 연산..
백준 17142 <연구소 3> 이전에 풀었던 연구소 1 보다 어려워진 문제이다. https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 이 문제를 풀기 전에 위의 링크의 연구소를 풀지 않았다면 먼저 풀고 이 문제를 풀기를 바란다. 위 문제와 유사하게 바이러스의 개수는 최대 10개이기 때문에 M개가 주어지면 10 C M 조합을 이용하여 확산할 바이러스를 구하고 해당 바이러스를 Queue에 넣고 BFS를 해서 최소 시간을 구하는 문제이다. 이 문제를 풀면서 가장 중요하다고 느꼈던 건 예외사항을 ..
백준 1600 <말이 되고픈 원숭이> 기존의 BFS 방법에서 조금 어려워진 탐색 문제이다. 고려해야 할 점은 BFS탐색을 하면서 말처럼 이동하는 횟수가 K번 이내, 나머지는 원숭이처럼 이동해서 목적지로 이동할 수 있는지 체크를 하는 문제이다. https://skygood95.tistory.com/2 백준 2206 단순하게 생각하고 구현하면 되는 전형적인 BFS, DFS문제!! 벽을 한 번까지 부수고 종점까지 가면 되는 문제 생각했던 방법은 총 2 가지 방문한 배열을 visit [][][] 이렇게 구현해서 3차원 배열을 만 skygood95.tistory.com 이전의 이 문제에서 조금 더 업그레이드 된 문제라고 보면 되겠다. 전체 맵의 범위가 200*200 총 40000번 그리고 k가 최대 20이기 때문에 800000 즉 80만 번 이기 때..
백준 19535 <ㄷㄷㄷㅈ> 문제에서부터 이해도가 필요한 문제이다 골드 3이라고 하지만 골드 1 수준이라고 느껴질 만큼 어려웠던 문제이다. 이 문제를 풀면서 다시 한번 중요하게 생각했던 것은 범위를 확실하게 봐야 한다는 것이다. 다음은 ㄷ의 경우를 고려해보자. ㄷ의 경우는 어떤 점과 어떤 점이 연결되어 있을 경우 각각의 점에서 다른 점에 연결될 수 있는 경우들을 고려해주면 된다. 이렇게 기본적인 이해를 하고 난 뒤 다음 문제를 풀 수 있다. 물론 ㅈ같은 경우는 자신이 연결되어 있는 개수만 알면 되지만 ㄷ같은 경우는 어떻게 처리를 해야 될지에 대해 많은 고려사항이 있었다. 그래서 선택한 방법이 다음 이동할 노드와 이전 노드를 동시에 큐에 담는 것이 좋다고 생각했다. bfs를 할 때 시작점을 큐에 넣어줄 때 이전 노드가 존재하지 않기 ..

티스토리툴바