Algorithm/BaeKJoon

    [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차원 배열은 아래와 같은 상태이다..

    [C++][BOJ 백준]2667_단지 번호 붙이기.
    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..

    [C++][BOJ 백준]2178_미로 탐색
    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; #..

티스토리툴바