Algorithm 개념 및 문제풀이17 백준 문제풀이 - 10815 개요 백준 문제 푼 내용에 대해 정리합니다. 내용 N개의 숫자와 M개의 숫자가 주어질 때, M 숫자들에 N 숫자들이 포함되어 있는지 여부를 1 또는 0으로 표현하면 되는 문제. N, M의 숫자들을 int 배열에 각각 저장하였고 이후 M 숫자들을 arr 배열에 저장하였다. for 문을 돌며 arr 배열의 i 번째 원소를 N 숫자를 저장한 배열과 비교해 여부를 체크하였다. 구체적으론 IntStream 의 anyMatch 함수를 사용하였는데, 문제 조건에 의하면 최대 백만 개를 탐색할 수 있고 시간 제한은 2초이므로, for 문안에서 각 원소를 탐색하는 것은 Big O(n^2) 을 만들어내 시간 초과라는 결과를 내었다. public class Main { public static int i = 0; publi.. 2023. 7. 22. 백준 문제풀이 정리 - 24262 문제내용 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다. MenOfPassion(A[], n) { i = ⌊n / 2⌋; return A[i]; # 코드1 } https://www.acmicpc.net/problem/24262 문제설명 MenOfPassion 코드에서 #코드1 을 수행했을 때의 횟수와, 시간복잡도 표현식인 Big O 표기법으로 나타냈을 때의 최고차항을 출력해야 하는 문제이다. 하나의 값을 가져올 때의 횟수는 1번이므로 어떤 값을 넣든 횟수는 1이다... 2023. 6. 29. 백준 문제풀이 정리 - 2798 문제 내용 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 .. 2023. 6. 21. 그래프 개념 정리 개요 알고리즘 문제 유형에 BFS, DFS는 빠질 수 없는 단골이기 때문에 글로 남기며 정리하고 기억하기 위해 작성합니다. 그래프의 개념, 용어, 자료구조로 표현한 그래프에 대해서 알아봅니다. 개념 그래프란? 두 개의 집합에 의해서 정의되는 구조이다. 그래프는 세 가지 종류가 있다. 무방향 그래프 방향 그래프 가중치 그래프 무방향 그래프, G = (V, E) V : 노드(node) 혹은 정점(Edge) E : 노드쌍을 연결하는 에지(edge) 혹은 링크(Link) 개체(object)들 간의 이진관계를 표현 n = |V|, m = |E| edge의 방향이 없음 ( (1,2) == (2,1) ) 일반적으로 두 정점을 연결하는 edge는 하나라고 가정함 스스로를 연결하는 self-edge 도 없다고 가정 **.. 2020. 9. 9. 동적 계획법 개념정리 개요 동적 계획법을 공부한 내용을 정리하기 위해 작성하였습니다. 공부하신 분들께 도움이 되면 좋겠습니다. 개념 정의 : 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법 큰 의미에서 보면 분할 정복과 같은 접근 방식을 의미합니다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해냅니다. 동적 계획법은 답을 여러 번 계산하지 않고 한 번만 계산하는데 이 계산 결과를 재활용함으로써 속도 향상을 꾀할 수 있습니다. 여기서 답을 메모리에 저장하는데 이 메모리의 장소를 캐시(cache)라고 부릅니다. 메모이제이션 앞서 캐시를 이용한 것처럼 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값.. 2020. 4. 6. 연결리스트(Linked-list) 개념 정리 및 문제 풀이 개요 연결리스트 문제를 풀면서 모르는 점들이 많다고 느껴 해당 개념을 정리하고 관련 문제를 푸는 방법에 대해서 글을 작성하였습니다. 개념 연결리스트란? 배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는 것은 시간이 오래 걸리는 작업입니다. 해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문입니다. 평균적인 경우 이 작업들에는 원소의 개수에 선형 비례하는 시간이 걸립니다. 이와 같은 문제를 해결하기 위해 고안된 자료 구조가 연결 리스트(linked list)로, 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해줍니다. 연결 리스트는 배열과 아주 다른 형태를 가지고 있습니다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되.. 2020. 2. 18. Leetcode 17번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 17. Letter Combinations of a Phone Number 주어진 번호에 해당하는 문자들을 조합해서 나올 수 있는 모든 문자들을 출력하기 https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 풀이 이 문제는 생각보다 간단한 풀이로 풀 수 있다. 문자열이 두개 주어지는 다음 경우를 보자. 위 그림처럼 abc, def 2개의 문자열을 조합해 결과를 출력하면 ad, ae, af ... cf 까지 총 9개가 나온다. 이는 두 문자열을 이중 for loop 로 조합해서 만들 수 있는데 이를 응용하여 다른 문자열들도 조합하는 것이 .. 2020. 2. 5. Leetcode 15번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 15. 3Sum 주어진 배열에서 요소 3개를 골라 합했을 때 0이 되는 것들만 배열로 추려내서 반환하기. 단 중복되는 것은 피하기(not allowed duplicate triplets) 풀이 문제 풀이를 위해서 먼저 주어진 배열을 오름차순으로 정렬해야 한다. 정렬을 하면 합했을 때 0이 되는 요소를 찾기 쉬워지기 때문이다. 그래서 만약 다음과 같이 정렬을 했다고 하자. 현재 배열 요소가 -2 라면, 그 다음 요소와 배열 마지막 요소로부터 인덱스를 줄여나가면서 적합한 요소를 추려낸다. 이 때 현재 배열 요소의 다음 값 인덱스를 low, 배열 마지막 요소 인덱스를 high 라고 하자. 현재 배열 요소가 -2.. 2020. 2. 3. Leetcode 4번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 4. Median of Two Sorted Arrays 주어진 두 배열들에서 중간값(Median)을 구해야 함. ** 중간값은 말 그대로 배열의 중간에 위치한 값임. 이 때 배열요소의 갯수가 홀수이면 중간에 있는 요소가 정답이 되지만 짝수이면 중간위치 주변의 값들의 평균이 정답이 됨. 풀이1 : Bruce force 주어진 두 배열을 합친 후, 합쳐진 배열에서 중간값을 찾음. 이 때의 시간복잡도는 O(m + n) 이며 공간복잡도 또한 O(m + n) 으로 동일함. 풀이2 : Binary Search Binary Search 로 풀기 위한 방법에는 배열을 적당히 나누는 기법이 들어가는데, 이에 대한 이해가 .. 2020. 1. 24. 이전 1 2 다음
