본문 바로가기
백준 #11047. 동전 0 그리디 알고리즘을 이용해 풀었다. K원을 만드는 데 필요한 동전들은 K원보다 작은 동전들이다. coin 배열을 n-1번째 인덱스부터 0번째 인덱스로 거꾸로 받고, 0번째 인덱스부터 차례대로 K원을 만족시킬 수 있는지 알아본다. 만약 i번째 인덱스가 K원보다 크다면, 다음 인덱스를 탐색한다. 만족하는 인덱스의 숫자(동전 숫자)는 K원보다 작을 때까지 더해준다. 가령, K원을 4200원이라고 했을 때, 50000원, 10000원, 5000원으로는 절대 4200원을 만들 수 없다. 그러니 스킵하고, 1000원을 만나면 그걸 4만큼 반복해서 더해준다. 그럼 4000원이 된다. 그 다음 500원을 더하면 4500원이 되므로, 500원을 낄 수 없다. 얘도 스킵! 그 다음은 100원이다. 4100원 n >> res..
백준 #2178. 미로 탐색 (1, 1)에서 (n, m)까지의 최단 경로를 구하면 된다. 4 6 110110 110110 111111 111101 이런 input이 들어왔을 때, (1, 2)와 (2, 1)까지의 경로는 아래처럼 2가 되는 것을 알 수 있다. (1번 index부터 시작) 120110 210110 111111 111101 즉, 현재 있는 칸에서 +1 한 값이 인접 칸까지의 최단경로이다. 나의 인접 칸들을 모두 훑고 인접 칸들의 인접 칸을 훑어보는 방식이므로, BFS를 이용해 풀어보았다. 현재 있는 칸을 큐에 넣어주고, 방문처리한다. 그리고 큐가 빌 때까지 인접 노드들을 탐색하며 큐에 넣는다. 단, 인접 노드 값이 0이면 그 칸을 지나갈 수 없으므로 탐색하지 않는다. 더 이상 방문할 인접노드가 없다면 큐에서 pop해주고,..
백준 #1463. 1로 만들기 몇 번의 시도 끝에 성공했다.ㅠㅠ 다이나믹 프로그래밍 방법으로 풀었는데, 혼자 이런저런 패턴을 연구해서 적용해도 "틀렸습니다."가 떴다. 마음을 비우고 문제에서 원하는 조건 그대로 코드를 작성했더니 맞았다. 기본적으로 result[i]의 값은 result[i-1] + 1이다. 1을 뺀다는 조건이 있으므로 이전 result[i]의 값에서 1을 더하면 된다. 단, 이건 result[i]가 가지는 최댓값이 된다. 그래서 3으로 나눠 떨어지는 경우, 2로 나눠 떨어지는 경우는 result[i-1] + 1과 각각 result[i/3] + 1, result[i/2] + 1을 비교해 더 작은 값으로 설정한다. 다음은 소스코드이다. #include #include using namespace std; int main(..
백준 #1904. 01타일 00과 1의 조합으로 특정 숫자를 만들 수 있는 가짓수를 묻고 있다. 이런 문제는 세부적인 데이터에 집중하기보다, 패턴을 찾으면 쉽게 풀 수 있다. n 결과 1 1 2 2 3 3 4 5 5 8 보면, 피보나치 수열의 형태를 띄고 있다. 따라서, 입력된 n까지의 결과를 구한 다음, 문제에서 요구하는 대로 15746으로 나눠 주면 된다. 재귀적으로 풀면 n이 커졌을 때 연산량이 급속도로 증가하기 때문에, 배열(arr)에 구해둔 값을 저장해서 가져다 쓰는 Dynamic Programming 방식을 택했다. 다음은 소스코드이다. #include using namespace std; int main() { int n; cin >> n; int* arr = new int[n + 1] {0, 1, 2, }; //sa..
백준 #7576. 토마토 BFS를 이용해 풀 수 있는 문제이다! 입력받을 때, 토마토가 있는 위치를 큐에 넣어주고, 큐를 pop하면서 큐가 빌 때까지 큐의 원소를 하나씩 검사한다. BFS를 수행하는 인덱스 y, x를 인자로 넣어주고, box[y][x]의 상, 하, 좌, 우를 탐색한다. 영향을 미칠 수 있는 토마토가 있으면, 현재(box[y][x])의 숫자보다 1만큼 큰 숫자를 넣어준다. 이렇게 하면 날짜 변수를 따로 만들지 않아도, 함께 셀 수 있다! 주의할 점은, 농장의 사이즈 m, n이 들어올 때 가로줄 개수 -> 세로줄 개수 순서로 들어온다. 보통 2 3이 차례로 입력되면, (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) 이렇게 세로줄 먼저 입력되는 것이 일반적인데, 이 문제는 반대이다. 나는 기존 방식이 ..
백준 #1057. 토너먼트 김지민과 임한수가 몇 번째 라운드에서 만날지 카운팅하는 문제이다. 한 번 라운드가 진행될 때마다 참가자 수가 반으로 줄어드니 그에 따라 n, kim, lim 변수를 반으로 줄여준다. (홀수일 경우는 +1한 뒤, 반으로 나눔.) 그리고 토너먼트는 1과 2, 3과 4 등 바로 옆 인덱스끼리, 그리고 (홀수, 짝수) 이렇게 진행된다. 부전승일 경우도 마찬가지로, 바로 전 인덱스가 홀수일 때, 그 인덱스와 짝꿍이 될 경우에 경기를 치를 수 있다. 따라서, kim과 lim 중 더 작은 수(minIndex)가 홀수일 때, 그리고 서로 바로 옆의 수가 될 때까지 round를 1씩 증가시키며 loop을 돌린다. 조건에 일치하는 경우, break를 하고 바로 round를 출력해준다. 다음은 소스코드이다. #include..
백준 #1260. DFS와 BFS DFS는 재귀로, BFS는 큐로 풀어보았다. 우선 문제에서 방문 가능한 노드가 여러 개일 경우, 숫자가 작은 노드부터 방문하라고 했으므로 linked 안의 연결 정보를 sorting해줄 필요가 있다. linked[i][j]에서 j부분을 sorting해주면 되므로, sort의 시작 주소를 linked[i].begin(), 끝 주소를 linked[i].end()로 설정한다. DFS : 호출된 노드 x를 방문 처리(visited)하고, 출력한다. x의 인접 노드 중 아직 방문되지 않은 것이 있다면 해당 노드에 대해 DFS()를 호출해준다. BFS : 호출된 노드 x를 큐에 넣고, 방문 처리(visited) 후 출력한다. 큐가 빌 때 까지 x의 인접 노드 중 아직 방문되지 않은 노드를 큐에 넣고, 방문 처리 후..
백준 #2667. 단지 번호 붙이기 모든 집을 다 탐색해봐야 하므로 완전 탐색이라고 할 수 있다. DFS를 활용해 완전 탐색을 해 보았다. stack에 탐색한 집(x, y 좌표)을 넣고, 방문을 완료했으므로 visited[x][y]를 true로 바꿔준다. (방문 처리) 현재 있는 집부터 상하좌우를 탐색하며 집이 있으면 1을 추가하고, 방문 처리한 다음, 단지(group)에 속하는 집의 수를 1씩 증가해준다. 이것을 stack이 빌 때까지 반복한다. 주의할 점은 상하좌우로만 방문을 해야 한다는 것이다. newX와 newY의 범위를 x-1

티스토리툴바