본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 2665번 : 미로만들기 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net bfs로 해결한 문제였습니다. 풀이방법 1. 최소로 벽을 부수는게 0일 수 있으므로 정답을 확인할 배열 ck를 -1로 초기화해줍니다. 2. 입력을 받은 후 bfs를 시행합니다. 2-1. 시작점 0,0을 queue에 push한 후 ck를 0으로 갱신해줍니다. 2-2. q가 빌 때까지 수행하는데 주의할 것은 최단거리로 이동했을 때 바꿔준 방의 개수가 최소임을 보장할 수 없는 점입니다. 갱신해줘야하는 시점을 ..
(C++) - 백준(BOJ) 16195번 : 1, 2, 3 더하기 9 https://www.acmicpc.net/problem/16195 16195번: 1, 2, 3 더하기 9 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이하 이어야 한다. www.acmicpc.net dp로 해결한 문제였습니다. 풀이방법 1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다. d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1] 1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다. Code(Bottom Up..
(C++) - 백준(BOJ) 15592번 : 1, 2, 3 더하기 7 https://www.acmicpc.net/problem/15992 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net dp 문제였습니다. top-down으로 해결했습니다. 풀이방법 1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다. d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1] 1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다. Cod..
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 스티커 모으기(2) https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr dp문제였습니다. 풀이방법 greedy하게 띄엄띄엄 최대한으로 스티커를 떼어나면 최대일 것 같으나 그렇지 않습니다. 특정한 스티커가 점수가 나머지보다 월등히 높은 경우 그 스티커를 무조건 1개씩 건너뛰면서 떼어낼 경우 그 스티커를 떼지 못할 수 있습니다. 따라서 dp를 사용해야 합니다. 1. sticker의 size가 1인경우엔 바로 점수를 반환..
(C++) - 프로그래머스(2019 카카오 개발자 겨울 인턴십) : 징검다리 건너기 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 이분탐색으로 푼 문제입니다. 풀이방법 최대로 건널 수 있는 인원을 찾아야합니다. 1. 인원을 mid라고 생각했을 때 최대한으로 건넌 후의 각 돌들의 높이는 밟을 때마다 1씩줄어들기 때문에 결과적으로 돌높이 - 인원 수가 됩니다. 이 (돌높이 - 인원 수) 값이 0이하라면 건너뛰어야 하는 돌이 됩니다. 2. 모든 stones에 대해 연속되는 0이하의 구간들 중 최장구간의 길이를 cnt변수에 저장합니다. 3. cnt >= k라면 너무 많은 인원이 건넌 것이므로 right = mi..
(C++) - 프로그래머스(연습문제) : 줄 서는 방법 https://programmers.co.kr/learn/courses/30/lessons/12936# 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 조합의 속성을 파악하는 문제였습니다. 풀이방법 n이 최대 20까지이므로 모든 조합을 backtracking을 사용한다거나 next_permutation내장함수를 사용하게 되면 시간초과가 나게 됩니다. 이를 해결하기 위해서는 n과 k의 특정한 규칙을 찾아야 합니다. 나와 있는 예시로 설명하겠습니다. n은 3일 때 나올 수 있는 조합의 수는 3!이므..
(C++) - 백준(BOJ) 19238번 : 스타트 택시 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현 + bfs 문제였습니다. 풀이방법 1. 입력 받은 후 손님의 데이터를 구조체를 이용해 벡터 형태로 저장합니다. 구조체는 손님의 출발 행,열 그리고 도착 행,열 그리고 택시까지의 거리로 이루어져 있습니다. 2. 택시의 위치에서 각 지점의 거리를 계산해줍니다. 계산된 배열 dist를 확인하며 손님과 택시사이의 거리를 모두 갱신해줍니다. 최단 거리의 손님을 ..
(C++) - 백준(BOJ) 15591번 : MooTube(Silver) https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net bfs문제였습니다. 풀이방법 모든 정점을 bfs를 통해 확인하며 현재 정점에서 다음정점으로 가는데 USADO 즉, cost가 기존에 저장된 다음정점의 cost보다 작다면 dist배열을 최솟값으로 갱신해주면 됩니다. 그 후 모든 dist를 확인하며 k값 이상인 개수를 세준 후 반환한 뒤 출력합니다. Code #include #define ll lo..

티스토리툴바