본문 바로가기

Java16

[Java/백준/BFS, DFS] 1707번: 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 주어진 조건을 보고 이분그래프인지 아닌지 판단하면 되는 문제다. 이분그래프는 아래처럼 하면 된다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 2색변 이분 그래프의 예 그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite gra.. 2021. 6. 25.
[Java/백준/투포인터] 1806번: 부분 합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 연속된 수들의 부분합들 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성해야 한다. 참고한 부분은 아래 링크! https://dev2som.tistory.com/135 [Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간.. 2021. 6. 25.
[Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간합 알고리즘에 대해 알아보려 한다. 수열에서 합이 N인 연속부분수열 → Two Pointer N개의 정수로 구성된 수열에서 M개의 쿼리에 해당하는 구간합 → Interval Sum 코테에서도 많이 나오는 것 같다. 특정한 합을 가지는 부분 연속 수열 찾기 [투 포인터를 활용한 알고리즘 설명] 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 현재 부분 합이 M과 같다면, 카운트한다. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 양의 .. 2021. 6. 24.
(Java Servlet) foward는 request로 구현 가능하다. RequestDispatcher는 요청이 들어온 것을 담아서 전달하겠다는 의미이다. 기존의 것을 담아 forward한다. HttpServletRequest request.getRequeestDispatcher("경로"); RequestDispatcher foward(); 1. RequestDispatcher 인터페이스의 foward(); forward의 메소드를 가진 것은 RequestDispatcher 인터페이스이다. 인터페이스는 메소드의 명시만 되어 있지 직접적인 코드 구현은 안되어 있기 때문에, 해당 인터페이스의 객체를 얻어올 수 있는 클래스와 함수가 필요하다. 2. HttpServletRequest 인터페이스의 getRequestDispatcher 인터페이스지만 웹에서 요청하면, 해당 요청이 Ht.. 2021. 4. 16.
[Java/프로그래머스/탐욕법] Level 2 : 구명 보트 문제 programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 처음 생각했던 방법(걍 틀림) 우선순위 큐에 넣어서 작은 것들부터 묶으려고 했다. 하지만 이 경우 people = {30, 40, 60, 70}, limit=100 일 때 (30,40) / 60 / 70 으로 3이 리턴된다. 옳은 답은 (70,30) / (60, 40) 으로 2가 리턴되어야 한다. 두번째로 생각한 방법 ( 효율성 테스트: 실패(.. 2020. 11. 10.
[Java/프로그래머스/DFS] 여행경로 문제 programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 코드 처음엔 인접하는 공항들을 전부 adjacent에 넣어야 하는데 어떻게 해야할까 끙끙댔다. 다행히 tickets는 양방향이 아닌 순서가 있는 것이라, dfs함수의 if문에서 조건을 걸러낼 수 있었다. import java.util.ArrayList; import java.util.Collections; public class Solution { boolean[] visited; //방문한지.. 2020. 11. 5.
[자료구조/Java] Queue 구현하기 in Java www.youtube.com/watch?v=W3jNbNGyjMs 선입선출 방식(First-In First-Out, FIFO) 1) add() 2) remove() 3) peek() 4) isEmpty() import java.util.NoSuchElementException; class Queue{ class Node{ private T data; private Node next; public Node(T data){ this.data = data; } } private Node first; private Node last; public void add(T item){ Node t = new Node(item); if(last != null){ last.next = t; } last = t; //큐가 비.. 2020. 9. 9.
[Java/프로그래머스/브루트 포스] 소수 찾기 (Level 2) 문제 https://programmers.co.kr/learn/courses/30/lessons/42839# 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 � programmers.co.kr 코드 checkPrime 함수 2부터 √n 까지 나누면서 체크한다. (√n 을 기준으로 나눠지는 수가 대칭되기 때문이다. 이해가 안된다면 아래 링크 참고) https://programmers.co.kr/questions/11572 소수가 맞아도 ans라는 전역 ArrayList에 같은 값이 있는지 확인한다. 중복을 피하기 위함이다. pe.. 2020. 8. 29.
[자료구조/Java] 해시 테이블 (Hash Table) https://www.youtube.com/watch?v=Vi0hauJemxA&t=4s 검색하고자 하는 key 값을 입력받아 해시 함수를 돌려 반환받은 HashCode를 인덱스로 해서 데이터에 접근하는 방법! (key : 문자열, 숫자, 파일데이터) 암호화폐의 핵심 기술인 블록체인에서도 각 사용자들의 공공장부를 비교할 때도 해시코드를 이용한다. 해시테이블의 장점 검색 속도가 매우 빠르다! O(1) (해시 함수를 통해 만들어낸 해시 코드는 정수이다 → 배열 공간을 고정된 크기만큼 미리 만들어놓고 나눠담는다 해시코드 자체가 배열방의 인덱스로 쓰이기 때문에, 검색을 할 필요가 없고 바로 데이터의 위치에 접근할 수 있다!) 해시테이블의 단점 규칙에 따라 공간 활용이 비효율적으로 될 수 있다(Collision이 .. 2020. 8. 26.

티스토리툴바