Algorithm

    Algorithm

    [leetcode] 238. Product of Array Except Self

    Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. examples. Input: nums = [1,2,3,4] Output: [24,12,8,6] 풀이 🚀 처음엔 이중 포문을 사용해서 i !=..

    Algorithm

    [백준] 2503 숫자야구 Java

    소스코드는 Github에서도 확인하실 수 있습니다. 풀이 🚀 1~9까지 중복되지 않는 세자리 수만 가능하므로, 123 ~ 987까지 모두 순회하며 주어진 조건을 모두 만족하는지 확인한다. 주어진 조건 * Input으로 들어온 수와 strike, ball 수를 비교했을 때 같다. * 1~9까지 중복되지 않는 세자리 수로 이루어져있다. 모든 조건을 만족한다면 가능한 답에 포함되므로 answer를 1 증가시킨다. 소스코드 👩🏻‍💻 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java..

    Algorithm

    이진탐색과 lower/upper Bound

    목차 이진 탐색 lower bound upper bound 이진 탐색 이진 탐색이란 주어진 데이터에서 원하는 값을 찾을 때, 데이터를 절반씩 나누어가며 탐색하는 방법이다. 간단한 예시를 통해 이진 탐색에 대해 알아보자. 다음과 같은 데이터가 주어져있을 때, 내가 찾고 싶은 값이 11이라고 해보자. 1 11 13 25 31 44 이진 탐색은 앞서 데이터를 절반씩 나누어가며 탐색하는 방법이라고 언급했었다. 따라서, 이진 탐색을 시작하기 전 준비 단계는 다음과 같다. 1. 가장 작은 값(left), 가장 큰 값(right)을 가리키기 2. 중간값(mid)을 찾기 (mid = (left + right) / 2) 이진 탐색이 진행되었다면 1. 단계는 left와 right를 알맞은 위치에 옮기기로 변경된다. 여기서..

    Algorithm

    [알고리즘] 문자열 유형 정리 Java

    백준 문자열 문제 모음 백준 문자열 태그 문제 모음 목차 1. 회문 만들기 2. 문자열 뒤집기 3. 조건에 맞게 재 정렬하기 4. 특정 단어 추출하기 5. 애너그램 6. 가장 긴 회문 찾기 7. 문자열 개수에 따른 조합 구하기 8. 문자열 개수에 따른 순열 구하기 9. KMP 알고리즘 10. 접미사 1. 회문 만들기 문제 링크: https://level.goorm.io/exam/48192/%ED%9A%8C%EB%AC%B8/quiz/1 문제를 요약하자면 다음과 같다. 회문인 경우 0을 출력/ 유사 회문(한개의 문자만 제거했을 때 회문인 경우)인 경우 1을 출력/ 아무것도 해당되지 않는 경우 2를 출력 그래서 생각한 방법은, 일반적으로 회문을 체크할 때 주어진 문자열의 길이의 반만큼 순회를 돌며 i번째와 l..

    [알고리즘] 그래프의 깊이 우선 탐색과 너비 우선 탐색
    Algorithm

    [알고리즘] 그래프의 깊이 우선 탐색과 너비 우선 탐색

    이 내용은 프로그래밍 대회에서 배우는 알고리즘 문제해결전략이라는 도서를 통해 공부한 내용을 정리하였습니다. 탐색 알고리즘이란? 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색 알고리즘이라고 한다. 탐색 과정을 통해 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다. 깊이(depth) 우선 탐색이란? 그래프의 모든 정점을 발견하는 가장 방법으로서 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 존재한다면 해당 간선을 따라간다. gif 이미지를 통해 보면 다음과 같다. 즉, 이름 그대로 자식 노드를 먼저 탐색하고, 그 다음 형제 노드를 탐색하는 방법이 dfs이다. 깊..

    [알고리즘] 정렬 알고리즘
    Algorithm

    [알고리즘] 정렬 알고리즘

    대표적인 정렬 알고리즘 6가지를 요약 정리해보자. 이 글은 요약정리용이므로, 자세한 글은 참고 자료를 통해 이미지와 함께 작성된 글을 확인할 수 있다. Selection Sort (선택 정렬) n번의 비교과정이 필요하다. 최악의 경우 O(n)의 시간복잡도를 갖는다. 정렬 방법 1. 각 루프마다 최대 원소를 찾는다. 2. 최대 원소와 맨 오른쪽 원소를 교환한다. 3. 맨 오른쪽 원소를 제외한다. 4. 하나의 원소만 남을 때까지 1~3과정을 반복한다. Bubble Sort (버블 정렬) 정렬 방법 1. 가장 왼쪽부터 서로 인접한 두 원소를 검사하여 정렬한다. 2. 인접한 2개의 원소를 비교해 크기가 큰 값을 오른쪽으로 옮긴다. 3. 한 번의 루프가 끝나면, 가장 큰 값을 제외하고 1~2과정을 수행한다. In..

    [자료구조] 힙(heap)이란
    Algorithm

    [자료구조] 힙(heap)이란

    힙(heap) 자료구조란? 완전 이진 트리를 기본으로 한 자료구조로서, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다. 여기서 완전 이진 트리란, 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 노드들은 가능한 한 왼쪽부터 채워져 있는 구조를 말한다. 완전 이진 트리에 대해서는 이 글을 참고하면 좋을 것 같다. 힙의 종류 힙의 종류에는 두가지가 있다. 부모 노드의 값이 자식 노드의 값보다 항상 큰 힙을 최대 힙(max heap), 부모 노드의 값이 자식 노드의 값보다 항상 작은 힙을 최소 힙(min heap)이라고 한다. 값의 대소 관계는 부모 노드와 자식 노드 간에만 성립하고, 형제 노드 간에는 성립하지 않는다는 특징을 갖는다. 힙의 구현 힙을 저장하는..

    Algorithm

    [백준] 문자열 폭발 java

    import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.stream.IntStream; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String origin = br.readLine(); String bomb = br.readLine(); Stack stack = new Stack(); for (..

    Algorithm

    [프로그래머스] 다리를 지나는 트럭 java

    import java.util.ArrayDeque; import java.util.Deque; class 다리를_지나는_트럭 { public int solution(int bridge_length, int weight, int[] truck_weights) { int answer = 0; // 트럭이 지나면서 걸린 시간 int nowWeight = 0; // 다리 위에 있는 트럭들의 총 무게 Deque deque = new ArrayDeque(); for (int truck : truck_weights) { while (true) { if (deque.isEmpty()) { // 다리 위에 트럭이 없을 때 deque.offer(truck); answer++; nowWeight += truck; break..

    Algorithm

    [자료구조 간단 정리] - 해시, 스택, 큐

    해시 해시 테이블 해시 테이블은 hash function을 사용해 주어진 key 값을 hash 값으로 매핑하고, 이 해시값을 index로 하여금 value를 key와 함께 저장하는 자료구조이다. 예를 들어, hash function := mod 3이라고 해보자. 그러면 주어진 key에 대한 value 쌍은 다음과 같다. key hash value 1 1 2 2 3 0 4 1 하지만 위의 예시에서 확인할 수 있듯이, key가 1, 4일때의 value 값이 동일한 것을 확인할 수 있다. 이렇게 서로 다른 key가 같은 해시값을 가지는 상황을 hash collision이라고 한다. 해시 충돌 해시 충돌이 발생했을 때엔 어떻게 해결할 수 있을까? 우선, Chaining 방식이 존재한다. 즉, 같은 해시값을 갖는..

티스토리툴바