전체 글 37

[JAVA] 백준 2667 단지번호붙이기 (BFS, DFS)

📝 문제 📎 백준 2667 단지번호붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // 단지 번호 붙이기 // // bfs, dfs public class Baek_2667 { static int[] dx = {-1,0,1,0}; static int[] dy = {0,1,0,-1}; static int N..

Java 2023.11.23

[JAVA] 백준 14502 연구소

📝 문제 📎 백준 14502 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 함 // 0 : 빈칸, 1: 벽, 2: 바이러스 publ..

Java 2023.11.23

[JAVA] 우선순위 큐(Priority Queue)

[JAVA자료구조] 큐(Queue)에 대한 설명글 [JAVA] 큐(Queue) 1. 큐(Queue) 스택(Stack)과 반대로 선입선출(First - In First Out : FIFO) 구조 즉, 먼저 들어온 것이 먼저 나갑니다. 가장 앞에 있는 사람, 즉 가장 먼저 온 사람이 가장 먼저 서비스를 받아야 하고, 방금 도 kyungmin1221.tistory.com 1. 우선순위 큐(Priority Queue) 모든 데이터가 우선순위를 가지고 있고, 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조입니다. 예를 들어, 운영체제에서 시스템 프로세스는 응용 프로세스보다 더 높은 우선순위를 가집니다. 우선순위 큐는 이러한 우선순위의 개념을 큐에 도입한 자료구조입니다. 1-1 우선순위 큐(Pr..

Java 2023.08.19

[JAVA] 큐(Queue)

1. 큐(Queue) 스택(Stack)과 반대로 선입선출(First - In First Out : FIFO) 구조 즉, 먼저 들어온 것이 먼저 나갑니다. 가장 앞에 있는 사람, 즉 가장 먼저 온 사람이 가장 먼저 서비스를 받아야 하고, 방금 도착한 사람은 줄의 맨 뒤에 서서 대기합니다. rear(후단) : 큐에서 삽입이 일어나는 곳 front(전단) : 큐에서 삭제가 일어나는 곳 큐는 스택과 마찬가지로 2가지 방법으로 구현이 가능합니다. 1. 배열 2. 연결리스트 - 배열 배열을 이용하여 큐를 만드는 경우 원형 큐 형태로 구현. 원형 큐 형태를 구현함으로써 배열의 첫 인덱스가 0 이 아닐 수 있습니다. 이를 통해 배열의 마지막 인덱스에 데이터가 있어도 앞서 들어온 데이터를 꺼내 앞쪽 인덱스의 배열은 비어..

Java 2023.08.17

[JAVA] 스택(Stack) / 카카오 크레인 인형 뽑기(KAKAO)

1. 스택(Stack) 이란 ? 스택은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 스택은 후입선출(Last-In First Out:LIFO)의 형태로 일어나는 자료구조를 말합니다. 후입선출 구조란 예를 들어 스택에 A, B, C, D의 순서로 입력을 하여 스택에 넣었다면 D, C, B, A의 순서로만 꺼낼 수 있습니다. Stack ADT(추상 데이터 타입) Stack() : 비어 있는 새로운 스택을 만든다. isEmpty() : 스택이 비어있으면 true , 아니면 false를 반환한다. push(e) : 항목 e를 스택의 맨 위에 추가한다. pop() : 스택의 맨 위에 있는 항목을 꺼내어 반환한다. peek() : 스택의 맨 위에 있는 항복을 삭제하지 않고 반환한다. s..

Java 2023.08.13

[JAVA] 재귀(Recursion)함수 , 재귀(Recursion)호출

재귀(Recursion)함수란 ? 재귀 (Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다. 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식입니다. 일반 반복문을 통해 구현 가능한 기능은 재귀 함수를 통해 구현이 가능하며 반대로 재귀 함수로 구현 한 기능을 반복문으로 구현이 가능합니다. 재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 함수 안에 반드시 종료 구간이 되는 Base Case를 생각하며 코드를 구현해야 합니다. . . 백준 5639번 이진 검색 트리 문제를 풀었을 때, 익숙치 않았던 재귀함수 파트가 나와 머리가 아팠던 적이 있어 직접 간단하게 재귀함수..

Java 2023.08.12

[JAVA] 이진탐색(검색) 트리

1. 이진트리란 ? 이진트리는 각 노드가 최대 2개의 자식을 갖는 트리를 말합니다. 즉, 각 노드는 자식이 없거나 한개 이거나 두개만을 갖는 것 입니다. 2. 이진탐색트리의 특징 각 노드에 중복되지 않는 키가 있다 루트노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 구성된다. 루트노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 구성된다. 이진탐색트리는 기존 이진트리보다 탐색이 빠르다. 이진탐색트리의 탐색연산은 트리의 높이가 h 라면 O(h) 의 시간 복잡도를 가진다. 3. 이진탐색트리의 탐색과정 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이면 탐색을 종료한다 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다. 찾고자 하..

Java 2023.08.12

[JAVA] Brute Force 알고리즘

Brute Force ( 브루트포스 ) - Brute(무식한) + Force(힘) 영어 해석처럼 하나부터 열까지 모든 경우를 탐색하는 알고리즘이다. 모든 경우를 탐색하기 때문에 당연히 정답을 찾을 수 있다. 알고리즘을 설계하고 구현하기 쉽다. 복잡한 알고리즘 없이 빠르게 구현 가능하다. 알고리즘 실행시간이 매우 길다. 메모리 효율면에서 매우 비효율적이다. 선형구조 : 순차탐색 비선형구조 : 백트랙킹 , DFS , BFS 브루트 포스,,이름은 뭔가 멋있어 보이지만 복잡한 알고리즘을 푸는 경우 상당히 무식?한 방법!? 예시1 브루트포스 알고리즘 사용 예시 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

Java 2023.08.12

[ JAVA ] BufferedReader , StringTokenizer, StringBuilder 을 사용하는 이유

BufferedReader, StringTokenizer 는 문자열로 활용하기 위하여 사용되며 Scanner를 사용하는 것보다 빠르다. 백준이나 인프런에 있는 알고리즘 문제를 풀면서 문자에 대한 입력을 처리할 때, 지금까지는 scanner 를 많이 사용했지만, 문제를 풀면서 시간초과 문제가 발생했고, scanner 대신 BufferedReader 를 사용하면 버퍼(Buffer)를 사용하여서 알고리즘 문제를 풀 때, 시간복잡도 효율성에서 유리하다는 사실을 알고 본격적으로 공부 시작 ! 1 . 그렇다면 버퍼(Buffer) 는 무엇일까? 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 임시 메모리 영역 버퍼를 이용한 입력 : BufferedReader 버퍼를 이용한 출력 : ..

Java 2023.08.12

#14 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 올바른 괄호

Stack 의 대표적인 문제 스택(Stack)은 LIFO (Last In First Out)을 따른다. 스택에서 자료를 넣는 것을 '푸시(push)'라고 하고, 자료를 빼는 것을 '팝(pop)'이라고 한다. 마치 책을 쌓아 놓은 것처럼 생각해 볼 수 있다. 새로운 책(자료)을 제일 위에 올려놓는다(push). 그리고 책을 가져갈 때는 제일 위에 있는 책부터 가져간다(pop). 따라서 가장 마지막에 들어온 것이 가장 먼저 나가는 구조를 가지고 있다. [출처] (자료구조) 스택, 큐, 덱, 리스트 정리|작성자 써밋 써밋의 개발 블로그 : 네이버 블로그 컴퓨터교육과 3학년 blog.naver.com import java.io.BufferedReader; import java.io.IOException; imp..

Java 2023.08.11