전체 글

전체 글

    [C++][백준 BOJ]16953_A->B.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]16953_A->B.

    문제 번호 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B는 가능하다. if(B==A) break; B가 A보다 작아진다면 A->B는 불가능하다. if(B < A) return -1; 마지막..

    [C++][백준 BOJ]1080_행렬.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]1080_행렬.

    문제 번호 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 알고리즘 분류 그리디(greedy). 문제 풀이 문제에서 주어진 A,B 행렬을 (0,0) 부터 (N-2, M-2) 까지 탐색하여서 서로 다른 값을 갖을때 마다 3*3 크기의 부분행렬을 뒤집어주는 과정을 수행하였다. 1. 다른 부분이 있을때 까지 탐색한다. for (int i = 0; i < N - 2; i++) { for (int j = 0; j < M - 2; j++) { if (arry1[i][j..

    [C++][백준 BOJ]1744_수 묶기.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]1744_수 묶기.

    문제 번호 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 알고리즘 분류 그리디(greedy), 정렬 문제 풀이 문제에서 주어진 수열을 오름차순으로 정렬한다. 합을 가장 크게 만드는게 목표이기 때문에 양수는 가장 큰 수 끼리 묶어서 더해야하고 음수는 가장 작은 수 끼리 묶어서 더해야한다. 그래서 양수부분의 합, 음수부분의 합을 구한다음 bool 형태의 visited 배열을 선언하여서 남은 수 들을 더해주기로하였다. 문제에서 주어진 수열을 오름..

    [C++][백준 BOJ]1715_카드 정렬하기.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]1715_카드 정렬하기.

    문제 번호 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 알고리즘 분류 그리디(greedy), 자료구조(HEAP) 문제 풀이 그리디 알고리즘과 힙(Heap) 자료구조를 모두 알아야 풀 수 있던 문제같다. 처음 들었던 생각은 가장 작은 값들부터 더하여서 큰값들은 가장 적은 횟수로 더해져야 한다는 것이였다. 문제는 처음에는 주어진 값들을 오름차순으로 정렬하여 시작한다하여도 계산이 진행되는 중간중간에 항상 첫 값을 가장 작은값으로 유..

    [C++][백준 BOJ]1339_단어 수학
    Algorithm/BaeKJoon

    [C++][백준 BOJ]1339_단어 수학

    문제 번호 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알고리즘 분류 그리디(greedy). 문제 풀이 각 알파벳에 어떤 숫자를 대응할지 고민했다. 대충봐도 가장 높은 자리수를 갖는 알파벳에 가장 큰 수를 넣으면 될것 같지만, 같은 자리수를 여러번 같은 알파벳들이 등장하거나 더 낮은 자리수에 등장하더라도 더 많이 등장해서 더 큰 수를 배정받아야 하는 경우등이 있었다. 그래서 각 알파벳들마다 점수를 매기기로 했다.(점수를 매기기위한 벡터..

    [C++][백준 BOJ]1946_신입 사원.
    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). 문제 풀이 그리디 알고리즘을 사용하여 문제를 해결 할 수 있다. 처음에는 문제의 내용을 잘못이해 하여서 가장 우수한 사람을 채용하지 않더라도 가장 많은 수의 사람을 채용해야 하는 줄 알았다. 그래서 모든 지원자를 탐색하면서 각 지원자들이 몇명보다 우위에 있는지를 검사하고, 그중에서 가장 많이 나온 숫자의 개수가 정답인줄 알았다..

    [C++][BOJ 백준]11286_절댓값 힙
    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이 기본이다. 오름차순..

    [C++][BOJ 백준]9251_LCS
    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차원 배열은 아래와 같은 상태이다..

티스토리툴바