본문 바로가기

전체 글1068

[자바] 백준 8783 - Architektura niezależna (java) 문제 : boj8783 필요 알고리즘 개념 - 그래프 탐색 (bfs, dfs) 단순히 bfs 혹은 dfs로 그래프 탐색만 해주면 된다. 다만 약간의 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 bfs를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 문제 자체는 간단하다. '#'으로 둘러싸인 부분 내부의 빈칸까지 포함해서 넓이를 구하면 된다. 예를들어 예.. 2023. 1. 10.
[자바] 백준 2571 - 색종이 - 3 (java) 문제 : boj2571 필요 알고리즘 개념 누적 합 (prefix sum) 2차원 누적합 문제인데, 빈 공간을 포함하지 않기 위한 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 누적합 알고리즘으로 O(N^4)으로 풀었다. 다만 실제로 N^4은 아니고, 약간의 백트래킹도 포함되었고, 한쪽 방향으로 탐색 범위를 고정했으므로 4중 반복문이긴 하지만 N^4보단 낮다. 우선 2차원 누적합 알고리즘으로 직.. 2023. 1. 10.
[TDD] 스터디 3주차 (테스트 반복, 순서 지정, Extension 관련) 스터디 메인 페이지 * 책 내용의 1,2부는 책을 따라 실습하는 내용이므로 정리하는게 의미 없다고 판단되어 다른 스터디와 달리 책 내용은 정리하지 않습니다. 스터디에서 책 이외로 나온 내용만 정리했습니다. ⚈ 예를들어 시간 조건을 두고 테스트가 필요한 경우, 아래와 같은 테스트는 실행할때마다 성공할수도 있고 실패할수도 있다. @Test @DisplayName("1000만까지의 짝수의 합은 1ms 이내에 통과해야 한다.") void test() { Study study = new Study(); long sum = assertTimeoutPreemptively( Duration.ofMillis(1) ,() -> study.sumEvenNumbers(10000000) ,() -> "1000만 이하의 짝수의 .. 2023. 1. 10.
[TDD] 스터디 2주차 (JUnit 관련 내용) 스터디 메인 페이지 * 책 내용의 1,2부는 책을 따라 실습하는 내용이므로 정리하는게 의미 없다고 판단되어 다른 스터디와 달리 책 내용은 정리하지 않습니다. 스터디에서 책 이외로 나온 내용만 정리했습니다. ⚈ IntelliJ 에서 JUnit 테스트는 Gradle로 실행하는 방법과 JUnit으로 실행하는 방법이 있다. Gradle 사용 시 기본 실행은 Gradle로 실행된다. JUnit으로 실행하려면 Edit Configurations 에서 설정을 추가해서 실행하면 된다. 큰 차이는 없는데, Gradle로 실행 시엔 BUILD SUCCESSFUL 같은 그래들 메시지가 붙긴한다. 다만 그래들에서 설정할 수 있는 부분들이 있고, IDE 뿐 아니라 서버 환경에서도 동일하게 쓸 수 있으므로 그래들 쓸꺼면 그래들로.. 2023. 1. 9.
[자바] 백준 11663 - 선분 위의 점 (java) 문제 : boj11663 필요 알고리즘 개념 정렬, 해시, 이분 탐색, 누적합 이분 탐색을 활용하는 문제이다. 내 경우엔 prefix sum 개념도 좀 들어갔다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 [a, b] 이내에 포함된 점을 알려면 '[0, b]에 포함된 점의 개수 - [0, a-1]에 포함된 점의 개수' 를 구하면 될 것이다. (누적합 알고리즘 개념) 그럼 임의의 x에 대해 [0, x]에 포함된 점의 개수를.. 2023. 1. 9.
[자바] 백준 14927 - 전구 끄기 (java) 문제 : boj14927 필요 알고리즘 개념 브루트 포스, 그리디 약간의 브루트 포스 + 그리디가 필요하다. 둘 다 알고리즘이라기보다는 개념적인 부분이라, 구현이 크게 어렵지 않은데 아이디어가 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 보통 2차원 문제는 1차원으로 먼저 생각하면 더 쉽게 아이디어를 떠올릴 수 있다. 문제를 간단히 하기 위해 1차원에서만 우선 생각해보자. A. 1차원에서 생각해보자. 선택.. 2023. 1. 6.
[자바] 백준 9024 - 두 수의 합 (java) 문제 : boj9024 필요 알고리즘 개념 정렬, 투 포인터 투 포인터로 해결 가능한 문제이다. 투 포인터 사용을 위해 정렬도 해줘야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 두 정수의 합이 K와 가장 가까운 두 정수의 조합의 수를 찾는 문제이다. 얼핏 K와 동일한 수가 아니라 K와 가장 가까운 두 정수를 찾는거여서 투 포인터로 해결이 안된다고 생각할 수 있다. (예를들어 K=8이고, 두 정수의 합이 8인 경우가.. 2023. 1. 4.
[오브젝트] 11장. 합성과 유연한 설계 스터디 메인 페이지 목차 - ☆ 표시가 붙은 부분은 스터디 중 나온 얘기 혹은 제 개인적인 생각이나 제가 이해한 방식을 적어놓은 것으로, 책에 나오지 않는 내용입니다. 따라서 책에서 말하고자 하는 바와 다를 수 있습니다. - 모든 이미지의 출처는 오브젝트(조용호 저) 책 입니다. 10장과 연관된 내용으로, 10장 부터 봐야 이해 가능합니다. CHAPTER 11. 합성과 유연한 설계 ⚈ 상속(Inheritance)과 합성(Composition) 객체지향 프로그래밍에서 가자 널리 사용되는 코드 재사용 기법이다. 상속 : 부모 클래스와 자식 클래스를 연결해서 부모 클래스의 코드를 재사용. 부모 클래스와 자식 클래스 사이의 의존성은 컴파일타임에 해결된다. =is-a 관계 합성 : 전체를 표현하는 객체가 부분을 .. 2023. 1. 4.
[오브젝트] 10장. 상속과 코드 재사용 스터디 메인 페이지 목차 - ☆ 표시가 붙은 부분은 스터디 중 나온 얘기 혹은 제 개인적인 생각이나 제가 이해한 방식을 적어놓은 것으로, 책에 나오지 않는 내용입니다. 따라서 책에서 말하고자 하는 바와 다를 수 있습니다. - 모든 이미지의 출처는 오브젝트(조용호 저) 책 입니다. CHAPTER 10. 상속과 코드 재사용 ⚈ 코드 재사용 전통적인 패러다임 : 코드를 복사한 후 수정 객체지향 : 코드를 재사용하기 위해 '새로운' 코드를 추가. 객체지향에서 클래스를 재사용하는 전통적인 방법은 새로운 클래스를 추가하는 것. ⚈ 이번 장에서는 상속을 통한 코드 재사용을 알아보고, 11장에서 코드를 효과적으로 재사용할 수 있는 합성을 알아본 후 상속과 합성의 장단점을 비교하게 된다. 01 상속과 중복 코드 ⚈ 중복.. 2023. 1. 3.
[자바] 백준 2843 - 마블 (java) 문제 : boj2843 필요 알고리즘 개념 오프라인 쿼리 (offline query) 쿼리(질의)의 순서를 변경해서 푸는 아이디어를 생각해낼 수 있어야 한다. 분리 집합 (disjoint set) 분리 집합 개념과, 분리집합에서 집합이 합쳐지는 방향을 강제할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서는 조약돌이 멈추는 정점을 묻는 쿼리와 간선을 지우는 쿼리가 존재한다. 일반적으로 간선을 지우.. 2023. 1. 2.

티스토리툴바