Algorithm

Algorithm/BaeKJoon
[C++][백준 BOJ]1715_카드 정렬하기.
문제 번호 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 알고리즘 분류 그리디(greedy), 자료구조(HEAP) 문제 풀이 그리디 알고리즘과 힙(Heap) 자료구조를 모두 알아야 풀 수 있던 문제같다. 처음 들었던 생각은 가장 작은 값들부터 더하여서 큰값들은 가장 적은 횟수로 더해져야 한다는 것이였다. 문제는 처음에는 주어진 값들을 오름차순으로 정렬하여 시작한다하여도 계산이 진행되는 중간중간에 항상 첫 값을 가장 작은값으로 유..
→2021.07.01
Algorithm/BaeKJoon
[C++][백준 BOJ]1339_단어 수학
문제 번호 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알고리즘 분류 그리디(greedy). 문제 풀이 각 알파벳에 어떤 숫자를 대응할지 고민했다. 대충봐도 가장 높은 자리수를 갖는 알파벳에 가장 큰 수를 넣으면 될것 같지만, 같은 자리수를 여러번 같은 알파벳들이 등장하거나 더 낮은 자리수에 등장하더라도 더 많이 등장해서 더 큰 수를 배정받아야 하는 경우등이 있었다. 그래서 각 알파벳들마다 점수를 매기기로 했다.(점수를 매기기위한 벡터..
→2021.06.29
Algorithm/BaeKJoon
[C++][백준 BOJ]1946_신입 사원.
문제 번호 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 알고리즘 분류 그리디 (greedy). 문제 풀이 그리디 알고리즘을 사용하여 문제를 해결 할 수 있다. 처음에는 문제의 내용을 잘못이해 하여서 가장 우수한 사람을 채용하지 않더라도 가장 많은 수의 사람을 채용해야 하는 줄 알았다. 그래서 모든 지원자를 탐색하면서 각 지원자들이 몇명보다 우위에 있는지를 검사하고, 그중에서 가장 많이 나온 숫자의 개수가 정답인줄 알았다..
→2021.06.29
Algorithm/BaeKJoon
[C++][BOJ 백준]11286_절댓값 힙
문제 번호 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 알고리즘 분류 자료 구조 우선순위 큐 문제 풀이 우선순위 큐를 다루어야하는 문제이다. 헤더에 있는 priority_queue 를 사용하기로 하였다. priority_queue 로 정의된다. - 자료형은 int, double 등등 우리가 알고있는 자료형들을 넣으면 된다. - 구현체는 기본적으로 vector으로 정의된다. - 비교 연산자는 less이 기본이다. 오름차순..
→2021.06.24
Algorithm/BaeKJoon
[C++][BOJ 백준]9251_LCS
문제 번호 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 분류 DP 문제 풀이 Int형 2차원 배열을 사용한 LCS 풀이이다. 2차원 배열의 0항은 첫번째 스트링, 0열은 두번째 스트링 이라고 본다. A C A Y K P C A P C A K 이런 모양이다. 물론 2차원 배열에 실제로 저 값들이 들어가있는것은 아니다. 설명을 위해서 보여진 예시이다. 실제 2차원 배열은 아래와 같은 상태이다..
→2021.06.24
Algorithm/BaeKJoon
[C++][BOJ 백준]2667_단지 번호 붙이기.
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 알고리즘 : 그래프 이론. 문제 풀이 : DFS/BFS 를 활용하여 이어진 모든 구간의 크기를 구하는 문제이다. DFS 연습을 위하여 STACK을 사용한 DFS를 구현하여 문제를 해결하였다. 문제에서 주어진 지도를 MAP 이라는 2차원 배열에 저장하였다. 이후 MAP 배열 전체를 탐색하면서 아직 방문하지 않았고(Visited 배열을 사용하여 판별함.), 갈 수 있는 길이면 DFS를 수행하였다. DF..
→2021.06.24
Algorithm/BaeKJoon
[C++][BOJ 백준]2178_미로 탐색
문제 번호 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 알고리즘 분류 그래프 탐색. 문제 풀이 BFS를 사용하여 출발지부터 목적지 까지 최단거리를 구하는 방법을 선택했다. BFS를 구현할때 Queue를 사용했는데 Queue를 pop하는 과정에서 Front의 값을 pop 해야 하는데 Back의 값을 pop 하여서 오답이 발생하였다. Queue는 선입선출의 자료구조임을 기억하자. 코드 : #include #include #include using namespace std; #..
→2021.06.24

• 이전
• 1
• ···
• 20
• 21
• 22
• 23
• 다음