본문 바로가기

백준 문제 풀이

 (134)
백준 15661번 링크와 스타트(C++) https://tigerfrom2.tistory.com/80 스타트와 링크에서 파생된 문제이다. 스타트와 링크에서는 반드시 3대3 혹은 2대2 처럼 같은 인원수만큼의 팀원들이 있었지만 여기선 1대5, 2대4가 가능하다. 처음에 스타트와 링크를 풀어놓고 제출을 이 문제에 해서 정답률이 처참하다... 1~N까지 조합의 수를 확인해야한다. 반복문을 하나 추가하는 것 외에 스타트와 링크 문제와 다른 것은 거의없다. #include #include #include #define MAX 20 using namespace std; int N; int board[MAX][MAX]; bool check[MAX]; int answer = INT_MAX; void sol() { int team1 = 0; int team2 ..
백준 14889번 스타트와 링크(C++) 처음에 스타트와 링크를 풀어놓고는 다른문제인 링크와 스타트에 제출을 하고 있었다. 레전드 백트래킹을 통한 완전탐색문제이다. N도 최대 20이라 시간에 딱히 신경을 안쓰고 구현에 집중하면 풀 수 있는 문제다. 1. N까지 N / 2 개의 조합을 구한다. 여기서 조합에 선택된 팀1과 선택되지 않은 팀2로 나뉜다. 2. 팀1의 능력치와 팀2의 능력치를 구해 최솟값을 갱신한다. 3. 모든 조합을 구할 때 까지 반복한다. #include #include #include #define MAX 20 using namespace std; int N; int board[MAX][MAX]; bool check[MAX] = { false, }; int answer = INT_MAX; void sol() { int team1..
백준 1715번 카드 정렬하기 (C++) 우선순위 큐라는 분류를 보지않았다면 조금 해맸을 것 같다. 주어진 카드뭉치를 우선순위 큐 오름차순으로 정리하고 꺼내면서 연산하면 된다. 그러나 처음 이해한 것이 예를들어 N =3 이고 A B C라 정렬되어있다하면 (A + B) + (A + B + C) 인줄 알았다. 그래서 꺼내면서 중복처리해주면서 연산했는데 이런문제가 아니었다. 로직은 다음과 같다. 1. 두개를 꺼내 더함 2. 더한 값을 큐에 다시 넣음 3. 더한 값을 answer에 sum 해놓음 3. 1,2,3번을 큐가 빌때까지 반복, 단 큐가 끝날 때 아직 더하지 않은 요소가 있다면 덧셈함. 문제를 확실히 읽고 파악하는 연습이 필요하다. #include #include using namespace std; priority_queue q; int ma..
백준 11279번 최대 힙(C++) 자료구조 힙, 우선순위 큐, 그리디 문제를 열심히 풀어보려고 한다. 먼저 최대힙 문제를 풀어봤다. 우선순위큐를 구현하기 위해 생긴 자료구조가 힙이다. 힙은 이진트리로 구성되어있고 배열 혹은 리스트로 구현이 가능하다. 물론 이 문제는 힙같은건 구현할 필요 없고 stl만 사용해도 충분하지만 공부를 위해 배열로 구현해봤다. 기본적인 최대힙의 개념을 살펴보면 1. 부모노드는 언제나 자식 노드보다 크다. 2. 자식 노드 중 작은 노드가 왼쪽 더 큰 노드가 오른쪽이다. 이러한 배열이 있다고 치면 index 1 2 3 4 5 6 value 1 3 6 5 9 8 이걸 트리 형태로 만들어보면 1 / \ 3 6 / \ / 5 9 8 이렇게 될 것이다. 그러니까 부모노드의 index = 자식노드의 index / 2 자식노드..
백준 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)의 시간이 걸리니 이분탐색까지 하면 ..

티스토리툴바