devBB 메모장

1. 큐 자료구조 개념 설명큐(Queue)는 가장 간단한 자료구조 중 하나로 FIFO(First In First Out)의 특성을 가지고 있습니다.FIFO는 큐에 먼저 들어온 데이터가 먼저 나간다는 의미이고,은행이나 맛집에서 방문한 순서대로 입장하는 평범한 대기열을 생각하면 쉽게 이해할 수 있습니다. 큐의 가장 끝 자리(rear)에 데이터를 넣는 것을 enqueue라고 하고,가장 앞 자리(front)에서 데이터를 빼는 것을 dequeue라고 합니다. dequeue 시 가장 먼저 들어온 데이터에 가장 높은 우선순위를 두고 뺀다면 일반적인 큐가 됩니다.하지만 dequeue 시 큐에 들어온 순서가 아닌 최소값, 최대값 등 특별한 우선순위를 두고 빼는 방식을 쓴다면이는 우선순위 큐(Priority Queue)라..

(예시 코드 및 이미지는 추후 추가 예정) 1. 힙 자료구조 개념 설명힙(Heap)은 우선순위 큐(Priority Queue) 중 가장 대표적으로 사용되는 자료구조입니다.실제 제가 준비 중인 알고리즘 구현 시험에서도 빈번하게 사용되고 있어서 첫 게시글 대상으로 선정되었습니다. 힙과 우선순위 큐를 이해하기 전에 큐 자료구조에 대해 이해를 하면 좋습니다.큐에 대한 소개는 아래 링크 참고 바랍니다.https://rightbellboy.tistory.com/343 큐 자료구조 개념 설명 및 예시 코드 (C/C++)1. 큐 자료구조 개념 설명큐(Queue)는 가장 간단한 자료구조 중 하나로 FIFO(First In First Out)의 특성을 가지고 있습니다.FIFO는 큐에 먼저 들어온 데이터가 먼저 나간다는 의..

백준 온라인 저지(BOJ) 11279번 최대 힙https://www.acmicpc.net/problem/11279* 사용언어 : C언어, C++ 1. 문제최대 100,000번 연산(x = 0 또는 자연수)이 주어짐x가 자연수이면 배열에 값을 넣고, 0이면 배열에서 가장 큰 값을 뽑아 출력배열이 비어있는 경우 0을 출력 2. 풀이우선순위 큐(Priority Queue, 이하 PQ) 분류에 해당되는 첫 번째 문제입니다. 일반적인 Queue는 선입선출(First In First Out, FIFO)로 Data를 넣고 빼지만,PQ는 이름 그대로 우선순위가 가장 높은 Data가 먼저 나와야 합니다.이 문제는 가장 큰 값이 가장 높은 우선순위를 가지므로 최대 Heap으로 구현합니다. Heap은 PQ를 구현하기 위해 ..

백준 온라인 저지(BOJ) 9251번 LCShttps://www.acmicpc.net/problem/9251* 사용언어 : C언어, C++ 1. 문제주어지는 두 문자열에 대해서 LCS(Longest Common Subsequence)의 길이를 출력 2. 풀이혼자 고민하다가 구글링을 해봤는데 놀라운 퀄리티의 자료를 발견해서 한 방에 이해했습니다.해당 게시글을 통해 내용을 이해한 덕분에 구현도 쉽게 할 수 있었습니다.https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A..

백준 온라인 저지(BOJ) 2565번 전깃줄https://www.acmicpc.net/problem/2565 2565번: 전깃줄첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는www.acmicpc.net* 사용언어 : C언어, C++ 1. 문제2개의 전봇대에 연결되는 전깃줄의 위치 번호가 주어질 때남아있는 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력 2. 풀이LIS(Longest Increasing Subsequence)로 풀 수 있는 문제입니다.백준 LIS 문제 설명 및 풀이는 아래 링크 참고하시면 됩니다.https://right..

백준 온라인 저지(BOJ) 11054번 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 증가하다가 감소하는 수열을 바이토닉 수열이라고 할 때, 주어진 수열 A의 부분 수열 중 가장 긴 바이토닉 부분 수열의 길이를 출력 2. 풀이 백준 단계 별로 풀어보기의 직전 문제인 가장 긴 증가하는 부분 수열 문제를 풀어봤다면 약간의 아이디어만 더해서 쉽게 풀 수 있는 문제입니다. https://rightb..

백준 온라인 저지(BOJ) 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 주어진 수열에 대해서 가장 긴 증가하는 부분 수열의 길이를 출력 2. 풀이 Dynamic Programming으로 푸는 대표적인 문제로 LIS(Longest Increasing Subsequence)라고 부릅니..

백준 온라인 저지(BOJ) 2156번 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net* 사용언어 : C언어, C++ 1. 문제일렬로 놓여진 포도주 N잔을 최대로 마실 수 있는 포도주의 양 출력 단, 연속으로 놓여진 3잔을 모두 마실 수 없음 2. 풀이단계 별로 풀어보기 > 동적 계획법를 순서대로 풀던 중에서 가장 난항을 겪었던 문제입니다. DP가 어느정도 익숙해졌다고 생각했는데 아직 갈 길이 먼 것 같습니다. DP 배열을 2차원이나 3차..

백준 온라인 저지(BOJ) 10844번 쉬운 계단수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 인접한 모든 자리의 차이가 1인 수를 계단 수라고 할 때, 길이가 N인 모든 계단 수의 개수를 출력 (ex. 45656) 2. 풀이 전형적인 Dynamic Programming 문제로 메모이제이션 용도로 2차원 dp 배열을 선언했습니다. 2차원 배열 중 첫 번째 차원의 index는 숫자의 자리 수(숫자의 위치)를 의미하고, 두 번째 차원의 index는 각 자리에 들어올 수 있는 숫자를 의미합니다. 예를 들어 dp[2]..

백준 온라인 저지(BOJ) 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 * 사용언어 : C언어, C++ 1. 문제 정수 X에 가할 수 있는 연산은 3가지(3으로 나누기, 2로 나누기, 1 빼기) 3가지 연산을 활용하여 X를 1로 만들 때 연산을 사용하는 최소값 출력 2. 풀이 Dynamic Programming의 Bottom-Up 방식을 활용하여 O(N)의 시간 복잡도로 풀 수 있는 문제입니다. i번째의 dp 값을 구하는 규칙은 상당히 간단한데, 아래 3개의 값 중 최소값을 골라서 저장하면 됩니다. 1) dp[i / 3] + 1 (i가 3으로 나누어지는 경우) 2) dp[i / 2] + 1 (i가 2로 나누어 지는 경우) 3) dp[i - 1] + 1 저는 i..