본문 바로가기

백준 문제 풀이

 (134)
백준 15686번 - 치킨 배달(C++) - 삼성 SW 역량 테스트 기출문제 - 골드V 처음엔 또 그래프? 라고 생각한 문제. 그러나 그래프 문제가 아니다. 가장 먼저 생각한 풀이는 1. BFS로 집과 치킨집의 거리를 넣어둠 2. DFS조합 3. 최소값 출력 그러나 BFS시에는 이쁘게 테이블 형태로 떨어지지 않는다. 너무 어렵게 생각했다. 그냥 각 좌표 받고 거리 구해서 순서대로 벡터에 넣어두면 된다. 문제의 핵심은 "조합" 이다. 즉 모든 경우의 수를 따져야하는 완전탐색 문제이다. 조합은 DFS로 구현하는 것이 가장 일반적이다. 예전에 공부해뒀는데 또 까먹어서 다시공부했다. 어휴 #include #include #include #define MAX 51 #define INT_MAX 10000000 using namespace std; int ..
백준 16236번 아기 상어 (C++) 예전엔 못풀었는데 드디어 풀었다! 이 문제는 BFS인데도 각 노드(칸)에서 따져줘야할 것이 많고 그저 먹이까지의 최소거리가 아닌 중간에 이동할 수 없는 칸도 존재하고 게다가 먹이들한테는 우선순위까지 있다.. 내 풀이는 이렇다. 1. 현재 지점에서 bfs 하며 먹을 수 있는 칸의 거리와 좌표를 모아 벡터에 담는다. 2. 모은 벡터를 거리가 짧은 순, 가장 위에 있으며 가장 왼쪽에 있는 순서대로 정렬한다. comp를 직접 만들어서 쓰면 된다. 3. 이후 먹을수있는 칸에서 다시 bfs를 시도한다. 내 코드는 bfs임에도 재귀의 성질을 갖고 있다. 매우 거부감 들었지만 size가 20x20이라 통과한 건가 싶다.. 속도가 다른 코드들에 비해 좀 느린편이다. #include #include #include #in..
백준 12865번 평범한 배낭 (C++) 전형적인 DP memoization 문제이다. 배낭 문제는 NP-hard 문제로 그리디 알고리즘으로 해결할 수 없음이 증명되어있다. 그러므로 주어진 N번만큼을 메모이제이션을 통해 DP 행렬을 갱신해가며 최적의 답을 구하는 수 밖에 없다. 주어진 예를 들었을 경우다. 6 13 이 들어오면 처음이니 그냥 써주고 4 8이 들어오면 이전과 비교해서 갱신해준다. 이때 DP[2][4] 는 이전이 0이었는데 8로 바뀌었다. -> DP[2][4] = max(DP[1][4], DP[1][0] + 8) 그러므로 점화식을 구하면 DP[i][j] = max(DP[i - 1][j - w] + value, DP[i -1][j]) #include #include #define endl '\n' using namespace std;..
백준 14891번 톱니바퀴 (C++) 얼핏 봤을때 삼성 문제 답게 그래프인가? 싶었는데 그냥 쌩구현이었다. 난 백준을 풀 때 웬만하면 100줄을 넘는 코드는 좋지않은 코드라고 생각하는데 무려 200줄이다. 허허,,, 반복을 잘 하면 줄일 수 있을 것 같은데 일단 내 최선이다. 아마 이 문제를 틀린 사람들의 이유는 다음과 같을 것이다. "톱니바퀴가 움직인 후" 옆의 톱니바퀴와 비교하는 것이 아니라 "톱니바퀴가 움직이기 전" 옆의 톱니바퀴와 비교하여 움직일지 말지 정하는 문제이다. 이 문제는 톱니바퀴가 고작 4개여서 노가다로 풀 수 있었지만 톱니바퀴가 5개만 되어도 힘들것이다. 뭔가 일반화된 식이 있을까 고민된다. 1. 시계방향이동 함수 구현 2. 반시계방향이동 함수 구현 3. 톱니들의 규칙에 맞는 함수 구현 #include using name..
백준 2293번 동전 1 (C++) 다이나믹 프로그래밍 문제는 정말 어려운 것 같다. 일단 모든 문제를 거의 O(N)으로 처리해야하는 엄청난 부담감과 아이디어.. 어쨌든 이 문제는 제한시간 0.5초로 매우 빡빡하다. 먼저 생각해볼 수 있는 DP 갱신은 두가지가 있다. 주어진 예제를 들면 3 10 1 2 5 먼저 DP[N] 에서 주어진 동전들로 N을 만들 수 있는 경우의 수를 저장하는 방법이 있을 것이다. DP[1] = 1 DP[2] = 2 DP[3] = 2 . . . DP[10] = 10 이 방법이 가능하다면 O(N)의 방법으로 해결이된다. 그러나 이 방법은 완벽한 점화식을 찾아낼 수 없었다. 왜냐하면 계속해서 입력값이 달라지기 때문이다. 그러니 이 방법은 틀렸다. 두번째 DP 갱신은 DP[N] 에서 N까지의 동전을 사용했을 때 몇번의 방..
백준 14499번 주사위 굴리기 (C++) 맞왜틀 때문에 정말 고생한 문제.. 사람들이 x,y 어쩌구 하는데 난 그게 문제가 아니었고 (그게 무슨 소리인지도 모르겠더라) 문제를 해석하는게 가장 중요했다. 1. 주사위가 기본적으로 어떻게 세팅되어있는지 확인해야한다. 2. 타일과 닿아있는 부분이 바뀌는데 출력은 주사위 윗부분임을 주의해야한다. 3. 주사위를 보드 바깥으로 보내면 반드시 아무 작업도 이루어지지 않아야한다. 난 3번을 그냥 출력만 안나오게 짰다가 맞왜틀의 늪에 빠져서 몇시간을 낭비했다 ㅠㅠ 가장 중요한 로직은 주사위를 동서남북으로 돌릴때 어떻게 돌려줘야할지가 문제이다. 다른 사람들은 모르겠지만 나는 전개도를 4x4 로 구성해 전개도를 계속 갱신해주었다. 이런식으로 주사위의 전개도를 갱신한다. 위는 예로 북쪽으로 이동했을 시이고 동서남북 ..
백준 11054 가장 긴 바이토닉 부분 수열 (C++) 부분 수열 시리즈 3번째이다. https://tigerfrom2.tistory.com/33 먼저 이 문제를 풀고 왜 dp를 쓰는지 알고 오는 것이 좋다. 백준 11053 가장 긴 증가하는 수열(C++) 처음 봤을 땐 "엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다. 그런데 정답률이 낮아서 의아했다. 그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중 tigerfrom2.tistory.com 매우 비슷한 문제이지만 dp의 갱신 조건이 더 까다로워졌다. 위 문제는 증가하기만 하면 +1로 갱신이 편리했지만 바이토닉 수열은 따질 것이많다. 우선 바이토닉 수열이 무엇인지 알아야한다. 바이토닉은 증가하다가 감소하는 수열이다. 여기서 순증가나 순감소 수열도 바이토닉 수열에 ..
백준 11055 가장 큰 증가 부분 수열(C++) https://tigerfrom2.tistory.com/33 백준 11053 가장 긴 증가하는 수열(C++) 처음 봤을 땐 "엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다. 그런데 정답률이 낮아서 의아했다. 그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중 tigerfrom2.tistory.com 수열 시리즈 문제이다. 이번에는 합을 DP에 담아서 갱신하면 된다. 코드가 매우 유사하므로 먼저 위 문제를 풀어보는게 좋다. 1 3 2 4 를 예로 들어보자. 모든 DP[N] = N 으로 갱신되어있다. 왜? 본인은 언제나 합에 포함되니까 1. 1이 들어오면 -> DP[1] = 1 2. 3이 들어오면 -> DP[3] = max(DP[1] + DP[3] , DP[3]) ..

티스토리툴바