본문 바로가기

알고리즘3

[알고리즘 문제풀이] 백준 16236 아기 상어(JAVA코드) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net /** * 1. bfs 전체 탐색 * * 2. 탐색해서 먹을 수 있는 곳들을 체크. * * 3. 그 중 가장 거리가 가까운 물고기 먹기. * * 4. 거리가 가까운것들 중 우선순위 1. 위, 2. 왼쪽 * * 5. 이동은 1초 * * 6. 아기 상어가 몇초동안 물고기를 잡아먹을 수 있는지 출력. * * ---------------------------------------------- * .. 2022. 3. 23.
[알고리즘 문제풀이] 백준 13701 중복제거(JAVA) https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net /** * 입력값 500만 * 입력데이터 2^25 * * 실패함 ㅠ * * 비트마스크 풀이 * * 1. 비트셋 활용 풀이 * * 입력값을 받으면서, * 현재 데이터가 비트셋에 없었으면 비트셋 표기 및 출력 * 있었으면 패스 * * 2. 배열 + 비트 마스크 * * 배열을 비트셋같이 쓸거임 arr * * int 자료형은 2.. 2022. 1. 13.
[알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드) KMP란 문자열 검색 알고리즘. Knuth-Morris-Pratt 3명의 사람이 설계한 알고리즘으로, 전체 문자열에서 특정 문자열을 찾는 알고리즘. 시간복잡도: N+M N(전체 문자열 길이), M(패턴 문자열 길이) 브루트포스로 풀이 코드 가장 쉽게 생각할 수 있는 브루트포스로 전체 문자열에서 특정 문자열을 찾았다면, 시간복잡도는 전체 문자열의 길이(n) * 특정 문자열의 길이(m) public Main{ String all = "ABABABCD"; // 전체 문자열 String pattern = "ABABC"; // 패턴 int cnt = 0; //패턴이 맞은 개수 for(int i = 0; i < all.length(); i++){ boolean check = true; // 패턴이 맞는지 체크 변수.. 2022. 1. 12.

티스토리툴바