본문 바로가기

백준 문제 풀이

 (148)
백준 14888번 연산자 끼워넣기(C++) 삼성 역량 기출 문제를 모두 풀어보는 것이 이번학기 목표이다. 먼저 생각난 풀이는 트리를 구성한 후 dfs 하는 것이었다. 예를 들어 + - x 한개씩 들어왔다고 생각하고 트리를 구성해보면 + x - / \ / \ / \ - x - + + x | | | | | | x - + - x + 이렇게 6가지 경우의 수가 나온다. 이렇게 트리를 구성하고 각 루트를 시작으로 dfs 하면 완전탐색을 할 수 있을 것이다. 그러나 트리를 구성하는것도 귀찮은 일이고 순서대로 트리를 계속 넣는 게 어려웠다. 그 다음 생각난 풀이가 순열이다. + - x 를 원소로 모든 수를 사용하는 순열을 만들어 완전탐색했다. 백트래킹을 이용한 순열의 대한 글은 아래를 참조하면 좋다.https://tigerfrom2.tistory.com/72..
백준 3190번 뱀 (C++) 삼성 SW 역량 테스트 기출 문제이다. 역시 삼성은 dfs bfs 엄청 좋아하는 것 같다. 그리고 언제나 그렇듯이 뭔가 되게 애매하게? 문제를 낸다.... 이번에도 가장 중요한 포인트가 있었다. 1. 시간이 끝나고 방향이 변한다. 즉 8 D 라고 들어오면 8초가 끝난 후 9초부터 방향이 바뀌는 것이다. 2. 1,1 부터 시작은 우리 일반 적 배열에선 0,0 에서 시작하는 것과 같다. 나의 풀이 - 각 방향이 주어지고 어떠한 거리를 구하는 것이 아니기 때문에 DFS가 적절하다. - 지나온 지점을 모두 기억하고 있어야한다. 이동할 수록 꼬리의 위치가 바뀌기 때문이다. 나의 경우 큐에 담아두었다. - 이번에 간 지점이 사과이면 큐에 담기만 하고 방문표시를 한다. - 이번에 간 지점이 사과가 없으면 큐에 담고 ..
백준 5014번 스타트링크 (C++) 전형적인 bfs문제이다. bfs의 근거는 다음과 같다. 1. 최소값을 구한다. 2. 갈수있는 방향과 칸수가 정해져있다. 그리고 조심해야할 점으로는 빌딩의 층을 넘어가면 아에 동작하지 않아야하는 것과 빌딩에는 0층이 없다 는 것을 간과해선 안된다. 그리고 c++ 에서 배열의 최댓값은 컴파일러에 따라 다르지만 VS의 경우 1메가바이트 = 1백만 바이트이기 때문에 거리를 저장할 배열을 정적으로 선언해놓는 것이 힘들다. 때문에 동적할당을 통해 거리와 방문여부를 체크할 배열을 만들었다. #include #include using namespace std; int main() { int F, S, G, U, D; queue q; cin >> F >> S >> G >> U >> D; int* dis = new int..
백준 2295번 세 수의 합(C++) 어려운 문제였다. 문제를 잘 읽고 분석하는게 참 중요했던 문제. 이런 문제도 있구나 세상은 넓고 나는 너무 ㅈ밥이다.... 처음 생각한 풀이: 1. nC3 조합을 구함 2. 집합에 속하면 삽입 3. answer를 max로 갱신 -> 시간초과. 이 문제는 완탐을 해야하는데 그 도구가 DFS 조합이었다. 그러나 N이 클 때는 오버헤드 문제를 고려하여 반복문 BF보다 조합이 훨신 느리다. 시간복잡도는 O(2^100 * N^M) 두 번째로 생각한 풀이: 1. BF로 모든 값을 구함 2. 벡터에 삽입 3. 주어진 집합을 sort 4. 주어진 집합의 최대값부터 이분탐색 5. 큰 값부터 찾으니 존재하면 출력 후 종료 이것도 틀렸다. 우선 3개를 고르기 때문에 기본적으로 O(N^3)의 시간이 걸리니 이분탐색까지 하면 ..
백준 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..

티스토리툴바