알고리즘
-
BOJ) 평범한 배낭알고리즘/백준 2020. 8. 28. 16:49
평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 짐의 개수 n, 버틸 수 있는 무게 k, n개 만큼의 짐의 정보 (무게 w, 가치 v)가 주어진다. 최대한 k에 맞추어, 최대 가치(max v)를 찾는 문제다. dp의 크기를 최대 가치 k까지 입력받을 수 있도록, k+1만큼 생성해준다. 짐의 정보를 순회하면서 w와 v를 가져온다. 그리고 k 부터 w까지 무게를 줄여나가면서, 현재 무게 ( i )의 dp값(가치) 과 dp[i-w] ..
-
BOJ) 한 줄로 서기알고리즘/백준 2020. 8. 28. 16:33
한 줄로 서기 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 � www.acmicpc.net 풀이 고민하는 시간에 비해 코드가 짧은 문제였다. 처음에는 우선순위 큐에 담아서, 적절한 sorting을 통해 출력하려고 했다. 하지만, 메모리 초과가 떴고 다시 고민했다. 주어진 정보들을 우선적으로 배열에 담고, 마지막부터(키가 제일 큰 사람부터) 자신의 왼쪽에 몇명이 있는지를 인덱스로 그 사람을 추가하면 된다는 것을 알았다. 문제의 예시를 통해 설명하면 더 쉽게 이해가 될 것 같다. 1 2 3 4 2 1 1 0 1~4의 값을 담은 배..
-
BOJ) 톱니바퀴알고리즘/백준 2020. 8. 28. 16:27
톱니바퀴 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 풀이 생각보다 많이 까다로워서 푸는데 한시간정도 걸렸다. 가장 오래걸렸던 부분은 회전하기 전에 각 톱니바퀴들의 좌측과 우측의 극을 확인해야한다는 부분이다. 회전하면서 극을 새롭게 찾으면서 코드를 작성했어서, sholdTurn이라는 boolean 함수를 만들어 움직여야하는지 판별해줬다. 또한, 처음 입력받는 톱니바퀴의 상태는 가장 처음 인덱스가 문제의 설명처럼 좌측부터 있는 것이 아니라, 12시이 가장 맨 처음으로 주어진다는 것이 왜 이렇게 꼬아놓..
-
BOJ) 토너먼트알고리즘/백준 2020. 8. 27. 15:43
토너먼트 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 프로그래머스에서 풀었던 문제와 유사한(? 혹은 똑같은) 문제다. 그 당시 엄청 어렵게 풀었었기 때문에, 이번에는 쉽게 푼 분들의 풀이를 익히면서 풀었다. 먼저, 첫번째 방법은 left와 right의 숫자가 같아질 때 까지 /2를 해주는 것(경기를 진행하는 것) left와 right에 +1을 해주는 이유는 첫번째 경기는 1번부터 시작하기 때문이다. (1번 2번 경기 => (1+1)/2 === (2+1)/2 === 1) 두번째 방법은 XOR 연산 후, 2진수..
-
BOJ) 누울 자리를 찾아라알고리즘/백준 2020. 8. 26. 15:46
누울 자리를 찾아라 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 세로와 가로를 직접 검증하는 메소드 두 개를 만들어서 쉽게 풀었다. 하지만, 기준점이 되는 좌표를 정하는 메소드로 만들었으면, 코드를 더 줄이고 중복을 줄일 수 있었을텐데 아쉽다. 확실히 문제 풀 때는 거기까지 생각하기는 힘든 것 같다. 아무튼, 내가 푼 방법은 가로와 세로 좌표를 각각 순차적으로 돌면서 다음 좌표가 빈칸인지 확인하며, 빈칸일 때까지 쭉 이어나가는? 방법이다. map에 직접 하는게 편하겠지만, 가로와 세로 각각 ..
-
BOJ) 섬의 개수알고리즘/백준 2020. 8. 26. 15:38
섬의 개수 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 풀이 섬의 개수를 찾는 문제로, 인접한 8구역이 땅이면 이동할 수 있다는 조건을 가지고 있다. 제약 조건이 기존 4곳에서 대각선들만 추가됐을뿐, 일반적인 grouping 문제다. grouping 문제는 이전 문제들에서 많이 다뤘기 때문에 큰 풀이는 남기지 않으려고 한다. 다만, 좌 우의 상/하 대각선을 예외처리 없이 검사하기 위해 map의 크기를 입력받은 n,m값 +2로 설정해줬다는 점이 특이하다 정도는 주의할만 하다. 그리고, 한 메소드 당 하나의 기능만 ..
-
BOJ) 수 찾기알고리즘/백준 2020. 8. 26. 15:31
수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 풀이 binary search인 것을 몰랐으면, 아마 시간 초과가 뜨고 나서야 시도했을 것 같다. 하지만, binary search라는 것을 알고 문제를 풀 때는 어렵지 않은 문제다. binary search에서 가장 중요한 것은 여러번 언급했듯, 기준점이다. 이 문제에서는 기준점이 명확하게 특정 숫자다. 특정 숫자를 담고있는 배열의 index를 찾는 문제라고 생각하면되겠다. 기준이 되는 배열은 Arrays...
-
BOJ) 가장 큰 정사각형알고리즘/백준 2020. 8. 26. 15:22
가장 큰 정사각형 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전에 푼 적이 있는 문제여서, 비교적 쉽게 풀 수 있었다. 당시에는 어떻게 풀어야하는지 막막했었는데, 그때 봤던 풀이가 아직 머릿속에 남아있었다. 우선, 맵을 돌면서 1인 경우에 좌측 상단, 좌측, 상단 세 군데를 확인한다. 세 곳의 최소값 +1(자기자신)이 dp의 값이 된다. dp[y][[x] += min(dp[y-1[[x-1], dp[y-1][x], dp[y][x-1]) 이 된다는 소리다. 변이 2인 사각형은 2로, 3을 만족하는 사각형은 3으로 값이 정해지는 것이다. (손으로 위의 식을 풀어가다보면 쉽게..