알고리즘/백준

뱀 문제는 큐를 활용해서 뱀의 길이를 가지고 자신의 몸에 닿는지의 여부를 확인하는 것이 키 포인트입니다. 또한, 방향 전환에 사용하는 dx, dy의 개념과 정해진 N x N 크기를 벗어나면 종료되는 코드를 활용하면 코드를 짜기 수월해집니다. 우선 N * N 의 크기 배열에 0으로 다 값을 넣어줍니다. 그리고 사과의 개수 K만큼 반복문을 돌려주면서 arr배열에 사과의 위치를 1로 업데이트 시켜줘서 사과의 위치를 찾기 쉽게 만들어줍니다. 위의 코드에서 dx, dy는 방향을 정해줄 때 중요한 방법입니다. 많은 문제에서 이 부분이 활용될 수 있으니 알아두면 좋을 것 같습니다! dx, dy를 위아래로 잘라서 봐야하는데 위아래로 잘라서 4등분을 할경우 처음 dx = [0] , dy = [1] 이됩니다. dy만 1이..

이 문제는 우선 순위 큐를 활용해서 푸는 문제입니다. 처음에는 어떤 방식으로 큐에 넣어서 가장 많이 포함하는 부분을 구하는지와 두번째 값 기준으로 오름차순 정렬을 하는 부분에서 시간을 많이 소요했습니다. 우선 list에 입력값을 받아 sorted함수를 통해서 첫번째 값을 기준으로 오름차순 정렬을 한다음, lambda함수를 사용해서 두번쨰 값 기준으로 정렬을 한번더 해줍니다. 아래 코드는 위에 정렬된 h_o 리스트에서 각 선분의 길이가 철로의 길이(d)보다 긴 값들을 제거해주는 코드입니다. 위의 코드는 파이썬에서 우선순위 큐에 자주사용하는 heapq 를 사용해서 heap 리스트에 h_o_list 리스트값을 하나씩 넣고 heap의 길이의 최대값을 answer에 저장해서 마지막에 최대 카운트를 가져올 수 있는..

이 문제는 이분탐색을 이용하여 새의 좌표가 사냥꾼 배열 arr=[1,4,6,9] 에서 잡을 수 있는 거리인지 확인하고 잡을 수 있으면 카운트하는 문제입니다. 우선 사냥꾼의 사정거리 L을 이용해서 사냥꾼이 새를 잡을 수 있는 범위를 구합니다. 사정거리의 범위는 L-Y(새의 Y좌표)를 X(새의 X좌표)에서 +, - 했을때가 범위입니다. 예를들어 첫번째 새의 경우 (7,2)니까 사정거리 4일경우 4-2의 값을 X값에 더하고 빼줍니다. 그러면 (5,2) ~ (9,2) 사이의 x좌표값에서는 해당 새를 잡을 수 있게됩니다. 이 부분을 활용해서 반복문으로 새를 호출해서 사냥꾼이 잡을 수 있는 새인지 아닌지 확인합니다. 이분 탐색과 반복문을 통해서 풀이한 코드입니다.

문제를 살펴보면 집의 개수 N, 공유기 개수 C가 있고 N개의 집의 개수가 주어졌을때 공유기 사이의 최대 거리를 구하는 문제입니다. 이 문제에서 중요한 점은 입력으로 받은 값들을 배열에 저장하고 오름차순으로 정렬시킨다음에 start와 end를 최소거리와 최대거리로 설정을하고 시작해야합니다. 우선 start는 시작점인 1로 설정하고 end는 가장큰 9에서 작은1사이의 거리이므로 8이됩니다. -> arr[-1] - arr[0] 위의 코드는 while문 코드인데 처음에 mid값을 start와 end의 중간값으로 설정합니다. 그리고 현재 위치를 의미하는 cur변수에 arr배열의 첫번째 값을 넣습니다. start가 1로 시작하므로 cnt도 1로 시작합니다. (1번집에 공유기를 이미 설치했다고 가정) 이제 for문..

위의 문제는 입력한 N의 개수만큼 N*N의 데이터를 입력하면 h 높이 (1~100)에 따라 물에 잠기지 않는 안전한 영역의 최댓값을 구하는 문제입니다. 우선 n을 입력하고 최대값을 넣어줄 ans라는 값과 2차원 배열로 데이터를 입력하는 방법입니다. h 높이에 따라서 최대값을 구해야하므로 범위를 1이상 101미만으로 for문을 돌려줍니다. for문을 돌려줄때 최대값을 return 받아서 ans로 넘겨줘서 반복할 때마다 가장 높은 max값을 뽑아주는 방식으로 구현합니다. 아래 코드는 위의 코드에서 호출한 solve(h) 함수입니다. 안전 영역 값을 카운트해줄 cnt 를 0으로 초기화해줍니다. 그리고 이중 for 문으로 전체 입력받은 행렬을 값으로 불러올 수 있도록 해줍니다. v[i][j] 값이 0 이라는 말..

위의 문제는 N개의 정수로 이루어진 배열 A의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 구하는 문제입니다. 우선 필요한 N개의 정수의 개수를 입력을 받고 N개의 정수를 리스트에 저장합니다. 그 다음 최댓값을 저장할 변수하나를 만들고 완전 탐색에서 각 노드에 대해 방문 여부를 저장하는 불리언 값의 배열 visited를 만들어 줍니다. 💡visited = [False] * N , visited 배열을 만들 때 입력받은 N개의 개수만큼 만들어 줘야합니다. 이제 완전 탐색의 기본 구조인 함수 부분을 코드로 보면서 설명하겠습니다. 위의 함수중에서 밑의 for문을 살펴보면 위에서 만들어준 visited 리스트가 비어있으면 값을 True로 넣어주고 리스트에 해당하는 값을 빈 리스트 li에 append시킨 후..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 위의 문제에서 우선적으로 생각해봐야하는 부분은 전체 배열의 크기의 패턴을 파악하고 4등분을 내서 1사분면, 2사분면, 3사분면 ,4사분면 형태로 나눠서 생각한다는 점이 key point같다. 알고리즘은 분할정복과 재귀함수를 사용하며 분할정복을 간..