본문 바로가기

알고리즘/BOJ

 (19)
[백준] 12865번 평범한 배낭 문제 제목처럼 평범한 Knapsack 문제 입니다. 하지만, 너무 간만에 봐서 다 까먹고 쉽게 풀지 못한 문제이기도 합니다...ㅠㅠ backtracking으로 풀어도 봤습니다. dfs로 재귀방식으로 모든 경우를 따져봤지만 역시나 시간초과가 뜹니다. 결국 DP로 풀어야 하는 문제입니다! DP 변수의 각 index(물건) 마다 0~k까지의 무게에 대해 최대값을 넣어주면 됩니다. 2가지 경우로 나눠서 풀어주기만 하면 간단합니다. 1) i 번째 물건을 안넣는 경우 2) i 번째 물건을 넣는 경우 1번의 경우는 그냥 i-1의 무게를 유지해주면 되는 문제고, 2번의 경우는 현재 무게( j ) - 넣고자 하는 물건의 무게에 해당하는 v값을 더해주면 됩니다. 대신 넣을 때는 주의해야 할것이, 넣는 것이 오히려 안넣을 ..
[백준] 9251번 LCS 단순히 LIS(Longest Increasing Subsequence) 처럼 풀려고 하다가 엄청 헤멘 문제 입니다.. LCS를 해결하는 방식이 있습니다. 우선 표를 통해서 먼저 설명하겠습니다. (문제에서 주어진 것 처럼 ACAYKP, CAPCAK를 활용합니다) A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 최종적인 표의 모습입니다. 알면 쉽게 풀리는.. 2가지 규칙만 적용하면 끝나는 문제입니다. 1) 같은 문자가 나오면 대각 왼쪽 상단 + 1 2) 다른 문자가 나오면 max(상, 좌) 먼저, 각 문자 배열 + 1만큼 DP(Dynamic..
[백준] 2206번 벽 부수고 이동하기 벽 부수는 것을 처음에 너무 간단하게만 생각했다가 여러번 틀린 문제입니다. queue에 넣는 조건을 잘 나누지 않으면 메모리 초과가 나오기 십상이니 명확하게 구분해야만 해결할 수 있는 문제였습니다. 먼저, 현재 좌표의 방문 여부를 벽을 부순적이 있는 경우와 없는 경우로 나눠서 진행해야 합니다. 안그러면 아래 예시와 같은 경우에 -1이 나오게 됩니다. 4 4 0000 0 1 1 1 00 1 1 00 10 한번 방문해서 실패했다고 무조건 visited를 true로 바꿔주면..! 아래처럼 되버려서 실패하고 맙니다. (0,0)->(0,1)->(1,1)->(2,1)->(3,1) 경로로 이동해서 한번 실패했다면, 해당 경로는 전부 visited = true가 되버립니다. 그러면, (0,0)->(1,0)->(2,0)..
[백준] 1707번 이분 그래프 [풀이] 백준 사이트의 정답률은 작성 당시 22퍼센트 밖에 안되서 지레 겁먹을수 있으나! 이분 그래프의 개념만 알면 bfs 혹은 dfs로 쉽게 풀수 있는 문제 입니다!! 문제의 설명만 보면 뭐가 이분그래프인지 잘 모르겠는데요, 그림을 보면 바로 알 수 있습니다! 위 그림 처럼 색이 서로 다르게 칠해질 수 있어야 이분 그래프 입니다. 쉽게 말해 니편 내편 가를 수 있어야 한다는 것입니다 ㅎㅎ 저는 bfs로 풀이 했는데요, 현재 노드가 1번 팀이라면 다음 노드는 2번 팀 이런식으로 팀을 구분 했고, 만약 팀이 겹치게 된다면 바로 false를 리턴했습니다. 아래는 풀이한 코드입니다 :) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..
[백준] 13460번 구슬 탈출 2 [풀이] 고려해야될 케이스가 많아서 생각보다 애를 먹었던 문제입니다.. ㅠ 우선 제가 풀이한 방식은 다음과 같습니다. 1. 각 지점별로 사방으로 이동을 합니다. 2. 빨강, 파랑 둘다 '#'를 만나거나 서로 겹치게 되면 멈추고 그 자리를 기억합니다. 만약 그 중 'O'가 있다면 가능한지 불가능한지 구분해줍니다. 가능하다면 바로 그 횟수를 출력하면 되고, 불가능하다면 그 위치에서는 더이상 이동 하지 않습니다. 여기에서 주의해야 할 부분은 visited를 빨강과 파랑 둘다 기록해줘야 한다는 것입니다. 처음에는 어짜피 빨간색만 구멍에 들어가면 되니까 빨간공만 기록해주면 되지 않을까 하였지만, 빨간색은 같은 위치인데 파란색의 위치가 달라 결과가 달라지는 경우가 생기더군요.. ! 어떻게 보면 BFS로 간단히 풀 ..
[백준] 2583번 영역 구하기 [풀이] 쉬운 문제인데 처음에 좀 헷갈렸습니다.. 저 색칠된 부분이 좌표라고 생각했는데 그게 아니어서 당황했던거죠..ㅠ 그렇지만 주어진 좌표를 토대로 제 입맛에 맞게 (위 그림처럼) 새로운 2D array를 만들고 해결하면 간단하게 풀리는 문제였습니다! 새로운 배열로 비어있는 부분을 BFS 탐색하였습니다. 아래는 풀이한 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #include u..
[백준] 14502번 연구소 [풀이] 처음에는 벽을 어떻게 세울까 엄청 고민을 했는데, 조건을 보니 N, M이 최대 8밖에 안되더군요! 전부 0이라고 하더라도 총 가짓수가 64*63*62 = 249984개밖에 안되서 완전탐색을 진행했습니다. 풀이 순서는 1. 일단 재귀를 활용해서 벽 3개를 세팅 2. bfs로 2 채우기 3. 0인 개수 구하기 아래는 풀이한 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72..
[백준] 1260번 DFS와 BFS [풀이] 가장 기본적인 DFS와 BFS를 구현하는 문제입니다! 아래는 구현한 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include #include #include #include using namespace std; vector gf(1001); bool visited[1001] = { false }; void bfs(int v) { queue q; visited[v] = true; q.push(v); while (!q.empty()) { in..

티스토리툴바