전체 글

[python3] 백준 4195 (친구 네트워크, 유니온 파인드)

문제는 아주 심플하다. 소셜네트워크를 구성할때 서로 친구가 될때마다 해당 네트워크에 몇명이 속하는지 알아내면 된다. 테스트 케이스의 범위는 주어지지 않았지만 F의 값이 100,000으로 주어졌다. 그럼 테스트 케이스 * 100,000으로 상당히 연산량이 클것으로 예상된다. 또한 DFS를 통해 구성된 네트워크의 노드 갯수를 센다고 가정한다면 100,000 * O(N) 정도의 시간 복잡도가 걸리는데 만약 N이 100,000이 된다면 너무 시간복잡도가 크다. 즉, 매번 탐색하는 방식으로는 구할 수가 없다. 그럼 A라는 친구가 어디 네트워크에 속하고, 네트워크의 크기는 어느정도인지 한번에 안다면 우리는 testcase*100,000의 연산만으로 정답을 구할 수 있다. 딱 냄새가 난다 네트워크에 속하고 머시기 어..

JAVA의 스레드를 공부하자

프로세스와 스레드의 차이 프로세스(공장) : 실행중인 프로그램이란 뜻이다. OS로 부터 실행에 필요한 자원을 할당받아 프로세스가 된다. 모든 프로세스는 하나 이상의 스레드를 가진다. 스레드(일꾼) : 프로세스 내부에서 작업을 수행하는 것이다. 호출스택만 있다면 무한정 만들어 낼 수 있다. 멀티 태스킹 : 여러개의 프로세스를 동시에 수행한다. cpu의 코어의 개수와 일치한다. 멀티 스레딩 : 하나의 프로세스에 여러개의 스레드를 수행한다. *스레드를 생성하는 것보다 프로세스를 생성하는데 더 자원(시간,공간)이 필요하다. *멀티 스레드는 하나의 프로세스(할당된 공간)에서 자원을 같이 사용하기 때문에 동기화,교착상태와 같은 문제들이 발생할 수 있다. 쓰레드의 구현과 실행 Thread 클래스 상속 (다른 클래스 ..

[python3] 백준 2470 풀이 ( 투포인터 )

문제의 목표는 두 용액을 선택하여 차이 값이 가장 적은 경우를 가지는 두 용액의 특성값을 출력해야한다. 입력으로 주어지는 N값은 100,000이다. 만약 모든 용액을 서로 비교한다고 가정한다면 100,000 * 100,000 경우의 수를 연산해야한다. 이러한 경우 연산 횟수가 너무 많아지기 때문에 완전 탐색으로 풀수가 없다. 따라서 다른 방법을 써야하는데 투포인터를 쓰는 방식을 생각해 볼 수 있다. 투 포인터는 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 따라서 보통은 i,j로 인덱스를 만들고 인덱스를 서로 1씩 증가 시켜가며 특정 합을 구할때도 많이 쓰인다. 이것과 비슷하게 이 문제를 처리할 수 있다. 다만 i,j를 서로 반대편에 놓고 값을 비교해가며 포인..

[python3] 프로그래머스 섬 연결하기 ( 그리디, MST, 크루스칼, 유니온 파인드)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 처음에는 그래프 알고리즘을 고민했다. 다익스트라,플로이드를 떠올렸지만 이건 목적지가 존재하는 경우에 사용하는 알고리즘이라 사용불가능 했다. 그러다가 가중치를 기준으로 정렬하여 하나씩 포함하면 되지 않을까 했고 visited 배열을 만들어 노드를 체크해주었다. def solution(n, costs): answer = ..

[TDD] 자바와 JUnit을 활용한 실용주의 단위 테스트 (작성중)

자바 유닛 단위 테스트 단위 테스트시 빠르게 코드를 점검할 수 있다 테스트클래스의 이름은 테스트할 클래스 이름 앞이 test를 붙여서 명명한다 asserThat으로 해당 값이 맞는지 판단한다 TDD 개발을 위해서 악의적인 테스트 실패코드를 작성해야한다 대부분의 단언은 실제 값과 비교한다 테스트 코드일 경우에는 try/catch보다는 예외를 던지는 방식으로 코딩해라 태스트 코드를 AAA방식으로 일관성 유지한다.(준비 실행 단언) 추가적으로 사후 단계도 필요하다(할당했던 자원 정리) 단위테스트는 개별 메소드 테스트가 아니라 클래스의 종합적인 동작을 테스트 해야한다 코드구조는 테스트를 별도의 디렉토리로 분리하지만 같은 패키지에 넣는다. 메이븐에서도 이를 권장함. 코드의 작은 변화가 수많은 테스트 코드를 깨트린..

[JUnit5] JUnit5를 공부해보자(Spring Boot, REST API)

자바 개발자의 93%가 사용하는 단위 테스트 프레임워크. 스프링 부트 2.2버전 이상 부터는 기본적으로 제공됨. JUnit5 모듈 Platform : 테스트를 실행해주는 런처 제공. TestEngine API 제공 Jupiter : JUnit5를 지원하는 TestEngine API구현체 Vintage : JUnit4와 3를 지원하는 TestEngine 구현체 (*작성한 버전에 따라 Jupiter를 사용하거나 Vintage를 사용한다.) Annotation 사용법 @Test 테스트라는 것을 나타내는 어노테이션 // JUnit4 @Test(expected = Exception.class) void create() throws Exception {} // JUnit5 @Test void create(){} @..

JAVA의 Servlet이 뭐지?

자바를 MVC패턴을 공부하면서 분명 서블릿서블릿 했는데 무슨 말인지 와닿지 않았다. 그래서 도대체 이게 무엇인가, 언젠가는 공부를 해야지 하고 다짐하고 넘어갔다. 오늘 드디어 서블릿을 뿌시는 기회가 왔다. 그래서 공부를 해보자. 우선 다양한 기관과 사람들의 정의를 보자 자바 서블릿은 자바를 사용하여 웹페이지를 동적으로 생성하는 서버측 프로그램 혹은 그 사양을 말한다. (위키백과) A servlet is a Java programming language class that is used to extend the capabilities of servers that host applications accessed by means of a request-response programming model. Alth..

JAVA 인터페이스는 왜 쓰는 걸까?

Spring Boot를 공부하다 보면 상속개념을 자주 사용하게 되었다. 물론 강의를 들으면서 따라치다보니 깊은 고민없이 그냥 이렇게 동작하는구나 하고 이해했었다. 그러다 복습을 하던 와중에 인터페이스를 쓰는 걸지 궁금 해졌다. typescript에서는 interface가 자료형을 공유하여 협업에 도움을 주기 위함이던데 JAVA는 무엇때문에 쓰는걸까싶었다. 인터페이스의 사전적 정의는 아래와 같다. 서로 다른 두 개의 시스템, 장치사이에서 정보나 신호를 주고받는 경우의 접점이나 경계면이다. 이게 무슨 말인가 싶다. 그럼 자바에서 인터페이스가 먼지 살펴보자 자바에서 인터페이스란 일종의 추상 클래스이다. 인터페이스는 추상클래스처럼 추상메서드와 상수를 갖지만 추상클래스보다 추상화 정도가 높아서 추상클래스와 달리 ..