Algorithm/BaeKJoon

    [C++][백준 BOJ]4963_섬의 개수.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]4963_섬의 개수.

    문제 번호 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 알고리즘 분류 그래프 탐색(BFS) 문제 풀이 BFS를 사용하여 이어진 부분을 모두 탐색하면 된다. 문제에서 최대 높이와 넓이는 각각 50이라고 하여 52*52 크기의 2차원 배열 Graph와 Visited를 사용하였다. 가장 왼쪽 위(1,1)에서 시작하여 (h, w)까지 탐색한다. 탐색 도중 땅(1)을 발견하면 BFS를 실행하여 Visited배열에 하나의 섬을 방문하였다(true..

    [C++][백준 BOJ]1449_수리공 항승.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]1449_수리공 항승.

    문제 번호 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 알고리즘 분류 그리디(greedy), 정렬(sort) 문제 풀이 구멍난 위치가 가까운 곳부터 먼곳순서로 정렬한다. 문제에서 구멍난곳 양쪽으로 0.5씩 간격이 있어야 한다고 했다. 그래서 (i 번째) + L >= (i+N)번째 +1 의 조건에 만족한다면 i번째에서 시작해서 i+N 번째 까지 같은 테이프로 막을 수 있다고 생각했다. 소수점 계산을 피하기 위해서 0.5씩 필요..

    [C++][백준 BOJ]1202_보석 도둑.
    Algorithm/BaeKJoon

    [C++][백준 BOJ]1202_보석 도둑.

    문제 번호 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 알고리즘 분류 그리디(greedy), 우선순위 큐(priority_queue) 문제 풀이 문제에서 주어진 가방의 크기들을 오름차순으로 정렬한다. 문제에서 주어진 보석들 또한 무게를 기준으로 오름차순으로 정렬한다. 우리는 가방에 1개의 보석만 넣을 수 있기 때문에 넣을 수 있는 보석들중 가장 비싼 보석을 넣어야한다. 그래서 Ma..

    [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). 문제 풀이 각 알파벳에 어떤 숫자를 대응할지 고민했다. 대충봐도 가장 높은 자리수를 갖는 알파벳에 가장 큰 수를 넣으면 될것 같지만, 같은 자리수를 여러번 같은 알파벳들이 등장하거나 더 낮은 자리수에 등장하더라도 더 많이 등장해서 더 큰 수를 배정받아야 하는 경우등이 있었다. 그래서 각 알파벳들마다 점수를 매기기로 했다.(점수를 매기기위한 벡터..

티스토리툴바