본문 바로가기

분류 전체보기

 (403)
백준 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 자식노드..
map의 다양한 사용법 - key, value 순으로 정렬, auto 반복문 기본적인 사용법: 선언 - map test; 삽입 - test.insert(make_pair(key, value)) 제거 - test.erase(key) ex) #include #include #include using namespace std; int main() { map test; test.insert(make_pair(1, 10)); test.insert(make_pair(2, 9)); test.insert(make_pair(3, 8)); test.insert(make_pair(4, 7)); test.insert(make_pair(5, 6)); cout
프로그래머스 - 카카오 프렌즈 컬러링북(C++) 기본적인 그래프 탐색 문제이다. 각 좌표에서 그래프 탐색 후 방문체크를 한다. bfs를 해도되지만 각 타일에서 다음 타일과 비교해야하는 부분도 있으니 dfs로 풀이했다. 그러나 bfs로 풀이해도 문제없다. 유사한 문제 - https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include using namespace std; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int M; int N; int ar..
프로그래머스 - [3차]자동완성 (C++) Trie 자료구조를 공부하게 된 이유가 바로 이 문제 때문이었다. https://tigerfrom2.tistory.com/74 문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오 tigerfrom2.tistory.com 대표 실습 문제라고도 할 수 있는데 Trie 자료구조에서 변수하나를 추가해줘야한다. 개념에서 알 수 있듯, 트라이 자료구조는 트리의 형태로 go -> gone 순으로 추가한다고 치면 g, o는 두번 방문될 것이고 n, e는 한번 방문될 것이다. 즉, 노드에 따로 방문 횟수를 저장한다. 그렇다면,..
문자열 관리 자료구조 - 트라이(Trie) 개념/구현 C++로 PS를 공부할 때나 코딩테스트를 볼 때 문자열 문제가 나오면 일단 짜증이난다. 파이썬은 문자열 다루기가 편하다는데 C++는 아무래도 문자열을 다룰때 힘든 면이 많다. 문자열 문제가 나오면 파이썬을 쓰고 다른 문제에선 C++을 쓰는 사람도 있을 정도다. 아무튼, 트라이는 문자열을 다루는 방식 중에서도 특히 문자검색을 할 때 가장 유용하고 효과적인 자료구조가 바로 트라이 이다. 먼저 트라이는 문자열로 트리를 만든다고 보면 된다. AB, ABC, BCD, ABD 라는 단어가 들어온다고 치자. 그렇다면 root / \ A B / \ B* C / \ \ C * D* D* 이런식으로 트리를 구성한다. 이렇게 하고 단어가 끝나는 글자들에는 표시를 해둔다. 즉 , 단어를 찾을 때 표시가 되어있는 글자라면 끝났..
백준 14888번 연산자 끼워넣기(C++) 삼성 역량 기출 문제를 모두 풀어보는 것이 이번학기 목표이다. 먼저 생각난 풀이는 트리를 구성한 후 dfs 하는 것이었다. 예를 들어 + - x 한개씩 들어왔다고 생각하고 트리를 구성해보면 + x - / \ / \ / \ - x - + + x | | | | | | x - + - x + 이렇게 6가지 경우의 수가 나온다. 이렇게 트리를 구성하고 각 루트를 시작으로 dfs 하면 완전탐색을 할 수 있을 것이다. 그러나 트리를 구성하는것도 귀찮은 일이고 순서대로 트리를 계속 넣는 게 어려웠다. 그 다음 생각난 풀이가 순열이다. + - x 를 원소로 모든 수를 사용하는 순열을 만들어 완전탐색했다. 백트래킹을 이용한 순열의 대한 글은 아래를 참조하면 좋다.https://tigerfrom2.tistory.com/72..

티스토리툴바