목록알고리즘 (30)
대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/15684 오늘 문제는 사다리 조작이다. 사다리 타기 게임을 시뮬레이션 하는 문제이다. 내가 임의로 몇 개의 가로 선을 추가해서 i번 째 사다리를 i번 사다리로 통과하게 만들어야 한다. 만약 추가해야하는 가로 선이 3개가 넘어가거나 어떻게 가로 선을 놓아도 i번 째 사다리가 i번 사다리로 통과하지 못한다면 -1를 출력하고 가로 선을 추가해 위 조건을 만족시킬 수 있다면 그 가로 선의 개수의 최소 값을 출력하는 문제이다. (0개도 가능하다) 문제 해결 아이디어는 이전의 문제들 처럼 완전 탐색을 통해 풀었다. 가로 선은 최대 3개만 설치해야하고 사다리의 최대 개수와 높이가 각각 10, 30이므로 완전탐색을 이용해도 시간내에 충분히 가능하다. 먼..
문제: https://programmers.co.kr/learn/courses/30/lessons/42585 오늘은 프로그래머스 [스택/큐] 문제 중 쇠막대기를 소개할까 한다. 사실 이건 백준에서도 풀었었던 문제인데 여기에도 있어서 반가워서 포스팅 할려고 한다. 문제는 '(' 와 ')' 로 이루어진 문자열이 주어졌을 때 최종적으로 쇠막대기가 몇 개로 나누어 지는지 물어보는 문제이다. 만약 '( )' 처럼 괄호의 열림과 닫힘이 연속적으로 주어진다면 레이저를 쏘아서 현재 놓여져 있는 쇠막대기를 나눌 수 있다. 문제푸는 아이디어는 스택/큐 문제이지만 굳이 스택/큐를 사용할 필요는 없다. 간단한 규칙찾기로도 이 문제를 해결할 수 있다. 문제에도 있는 예제인 ( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ..
문제: https://programmers.co.kr/learn/courses/30/lessons/42579 오늘은 프로그래머스 [해시] 문제들을 풀어봤다. 그 중 베스트앨범이라는 문제를 포스팅 해볼까 한다. [해시] 문제인 만큼 map이나 set을 최대한 활용해 보려고 노력했다. 문제 설명을 간단히 하자면 스트리밍 사이트에서 가장 유명한 노래들을 모아 베스트앨범을 만들고자 한다. 앨범에는 장르당 두 노래씩 넣는다.(여기 때문에 조금 헤맸다) 1. 가장 많이 재생된 장르부터 앨범에 넣는다.2. 두 곡의 순서는 더 많이 재생된 노래 먼저 넣는다.3. 만약 두 곡의 재생횟수가 같으면 고유번호(인덱스)가 더 낮은 것 부터 넣는다. 그 후 최종적으로 answer 벡터에 값을 넣어 반환하면 된다. 그런데 제한사항..
문제: https://www.acmicpc.net/problem/15683 최대 8 x 8 크기의 사무실에 설치된 감시 카메라와 벽의 위치가 주어진다. 감시 카메라는 모두 5종류가 있고 최대 8 대 까지 설치 할 수 있다. 각 감시 카메라는 상 하 좌 우 방향으로 감시가 가능하다. 감시 카메라를 모두 작동시켰을 때 감시하지 못하는 최소한의 사각 지대 크기를 출력하는 문제이다. 문제에서 물어 보는 것은 최소한의 사각 지대 크기 이므로 각 감시 카메라의 방향에 따라 달라지는 사각 지대의 크기를 모두 구해야된다. 이전의 문제들 처럼 완전 탐색을 하면 된다. 백트레킹으로 각 카메라의 방향을 가지는 배열을 구해주고 방향과 감시 카메라 종류에 따라 감시 가능 지역을 칠해주고 최종적으로 남아있는 0(빈 칸)의 개수를..
문제: https://www.acmicpc.net/problem/2473 KOI 고등부 문제이다. 주어진 배열에서 세 숫자를 더했을 때 0과 가장 가까운 숫자들을 출력하는 문제이다. 처음엔 단순하게 생각해서 정렬된 배열 arr에서 arr[i] + arr[j] = k 라고 했을 때 lower_bound로 i+1 ~ j-1 구간에서 -k와 가장 가까운 수를 찾아 i, j, -k와 가장 가까운 수의 합으로 최소값을 갱신해 갈려고 했다. 하지만 계산해보면 O(N^2 * lg N) 이므로 5000*5000*12 = 3억이 나온다. 즉, 시간 초과다. 다른 방법을 찾다가 O(N^2)에 해결하는 방법을 찾아서 소개한다. 3-SUM이라는 알고리즘이다. 출처 위키: 3SUM 영어는 잘 모르겠고 간단하게 정렬된 배열 ar..
문제: https://www.acmicpc.net/problem/14891 4개의 톱니바퀴와 각 톱니바퀴의 8 개의 볼록 부분의 상태가 주어진다. 그 후 쿼리가 최대 100번 까지 들어오면서 톱니바퀴의 번호와 회전 방향이 주어졌을 때 쿼리를 모두 수행한 후 톱니바퀴의 상태를 묻는 문제이다. 문제의 주제는 시뮬레이션이다. 각 쿼리 수행 후 톱니바퀴의 상태를 틀리지 않고 잘 가지고 갈 수 있으면 어렵지 않다. 문제 해결 아이디어는 쿼리가 들어왔을 때 먼저 해당 번호의 톱니바퀴를 방향에 맞게 회전 한다. 그 후 해당 번호부터 오른쪽의 톱니바퀴를 전부 회전 시켜주고 끝나면 나머지 왼쪽의 톱니바퀴를 회전하면 된다. 톱니바퀴를 회전할 때 만약 극이 같아 회전하지 않았다면 그 쪽 방향은 더 이상 진행하지 않아도 된다..
문제: https://www.acmicpc.net/problem/14890 지도가 주어졌을 때 행이나 열로 이루어진 길 중 지나갈 수 있는 길은 모두 몇 개인지 묻는 문제이다. 우리는 경사진 곳에 길이가 L인 경사로를 설치해 길을 지나갈 수 있도록 만들 수 있다. 경사로 설치에는 조건이 필요하다. 1. 경사로는 높이가 1 이기 때문에 높이가 2 이상인 곳은 경사로를 설치할 수 없다. 2. 길이가 L인 평평한 땅이 필요하다. 3. 경사로를 겹쳐서 설치할 수 없다. 이 조건들만 조심해서 코드를 작성하면 된다. 먼저 첫 번째 조건은 간단하다. 경사로가 차이가 났을 때 둘의 차이가 2 이상 나는지 확인해주면 된다. 두 번째 조건은 생각보다 복잡하다. 먼저 경사로를 설치할 땅이 남아있는지 확인한다. 오르막 경사와..
문제: https://www.acmicpc.net/problem/14889 N명의 사람들이 스타트와 링크 팀으로 나누어 축구를 한다. (N은 2의 배수) 각 팀원들은 서로간의 시너지가 발생한다. 이것을 나타낸 능력치 표가 주어졌을 때 스타트 팀의 시너지 합과 링크 팀의 시너지 합이 최소가 되도록 했을 때 최소 값을 구하는 문제이다. N이 최대 20이므로 완전 탐색을 이용하면 되고 백트레킹으로 N/2명씩 두 팀을 계속 선택해가며 최소 값을 비교하면 된다. 끝. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#includeusing namespace std;int n, arr[22][2..