ballqs 님의 블로그

오늘 풀어본 문제는 프로그래머스의 미로 탈출 이라는 문제를 풀어보았다.문제를 보자마자 DFS , BFS 알고리즘 쪽으로 풀면 될거라고 생각했다.문제 설명1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 ..

Proxy 패턴이란?프록시 패턴은 실제 객체에 대한 접근을 제어하고, 추가적인 기능을 제공하기 위해 사용되는 디자인 패턴이다.마치 대리인처럼 실제 객체를 대신하여 동작하며, 다양한 상황에서 유용하게 활용될 수 있다.Proxy 패턴 장점접근 제어실제 객체에 대한 직접적인 접근을 제한하고, 프록시를 통해서만 접근하도록 함으로써 보안을 강화할 수 있다.특정 조건에 따라 접근을 허용하거나 거부할 수 있다. 추가 기능 제공실제 객체의 기능을 확장하여 새로운 기능을 추가할 수 있다.예를 들어, 캐싱, 로그 기록, 권한 검사 등을 프록시에서 처리할 수 있다. 지연 로딩실제 객체를 필요한 시점까지 생성하지 않고, 프록시 객체를 통해 미리 참조할 수 있다.이는 큰 객체를 로딩하는 데 드는 시간을 절약하고 시스템 성능을 ..

오늘 풀어본 문제는 프로그래머스의 점 찍기 라는 문제를 풀어보았다.애초에 어떻게 접근해야할지 감도 못잡고 있다가 같이 공부중인 분이 힌트를 줘서 진행이 가능해졌다.문제 설명이 문제는 x축과 y축이 직교하는 좌표명면에서 k 값과 d 값이 주어지면 다음과 같이 점을 찍는다.원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.이는 좌표명면에 d 반지름의 원안에 k라는 간격만큼 점을 얼마나 찍을수 있는지 알아보기 위한 문제이다.제한 조건1 ≤ k ≤ 1,000,0001 ≤ d ≤ 1,000,000입출력 예kdresult2461526풀이과정주..

DFS 알고리즘에는 꼭 재귀 메서드를 호출하는게 아닌 Stack이나 Queue를 활용하는 방법도 있다고 한다. 해당 방식으로 풀게된 문제는 프로그래머스의 전력망을 둘로 나누기이다.문제 설명n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있고 여기서 하나의 전선을 끊어서 현재의 전력망 네트워크를 2개로 분할하는 문제이다.단! 두 전력망이 가지게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 한다.제한사항n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.1 ≤ v1 전력망 네트워크가 하나의 트리 ..

투 포인터(Two Pointer) 이란?배열이나 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 정렬되어 있을때 사용한다.두 개의 포인터는 보통 양 쪽 끝으로 시작하여 각각 탐색하면서 특정 조건을 만족하는지 검증한다.다만! 한 쪽 방향에서 동시에 시작하는 경우도 있는데 이는 해당 배열의 합과 차를 통해 특정 조건이 만족하는지 검증한다.투 포인터의 문제 적용프로그래머스 문제를 풀다가 이런 문제를 접했다.연속된 부분 수열의 합 이라는 문제이다. 문제 설명내림차순으로 정렬된 배열이 주어질 때 특정 조건을 만족하는 수열을 찾는 문제이다.주어진 k값이 있고 배열의 연속된 부분의 합이 k와 같으면 해당 포인터들의 index를 반환..

예전에 정렬에 관련된 게시물을 작성한 적이 있다.Array.sort와 Collections.sort의 차이점 이다. 하지만 여기에서는 말그대로 sort에 관련된 것만 작성했고Comparator 과 Comparable 를 이용한 정렬이 아니였다. 그래서 작성하여 메모해두려고 한다. Comparator compare()Comparator Interface를 찾아보면 compare()라는 메서드가 있고 int를 반환하도록 되어있다.compare() 메서드는 매개변수를 기반으로 비교한다.import java.util.Comparator;public class Test { public static void main(String[] args) { Person person1 = new Person(..

BFS(Breadth-First Search) 이란?너비 우선 탐색이라고 불리며 그래프 자료구조에서 완벽 탐색을 수행하는 탐색 기법이다.시작부분인 노드에 방문한 후 인접한 노드들을 우선으로 방문하며 기본적으로는 Queue 자료 구조를 이용해서 구현한다.특징재귀적으로 동작하지 않는다.BFS도 DFS처럼 노드 방문 여부를 검사해야 한다.최단경로를 찾는데 활용한다.탐색 과정  노드1 를 시작으로 자료구조에 데이터를 넣으면서 시작한다.노드1를 진행하고 방문완료 처리 후 노드1에서 파생되는 노드2와 노드3를 자료구조에 넣는다.2번 과정에 의해 노드2가 먼저 자료구조에 들어갔기에 노드2를 진행하며 노드2 또한 진행하고 방문완료 처리 후 노드 2에서 파생되는 노드4와 노드5를 자료구조에 넣는다.노드3를 진행하고 방문..

IT 회사에 취업하기 위해서는 2가지를 준비해야한다고 들었다.1. 미니프로젝트2. 코딩 테스트 미니프로젝트는 코딩테스트 같은 알고리즘보다는 주어진 프로젝트에 기능을 구현해서 제출하는 방법이다.이는 메일을 받아서 주어진 기간내에 구현하는 것이라 아무래도 공부해야하는 방법이 코딩 테스트와는 다른감이 있다.하지만 이 작성글에서는 코딩테스트를 다루는 글이니 미니프로젝트가 아닌 코딩테스트 쪽으로 살펴보자.준비해야 하는 알고리즘은 아래처럼 많다.DFS : 깊이 우선 탐색 알고리즘백트래킹 : DFS에서 더이상 정답이 아니라고 판단되는 부분은 탐색하지 않도록 가지치며 탐색하는 알고리즘BFS : 너비 우선 탐색 알고리즘(최단경로)투포인터(Two Pointer) : 특정 구간에서 작업을 할때 효율적에라토스테네스의체 : 특..

프로그래머스에 있는 알고리즘 문제 피로도를 풀다가 고생한 것들을 작성해볼까 한다.문제에 들어가보면 자세히 적혀 있겠지만 요약해서 적도록 하겠다.문제 설명XX게임에는 피로도 시스템이 있으며 일정 피로도를 사용해서 던전을 탐험할 수 있다. 다만 해당 던전에 대한 정보를 담고 있는 dungeons 이라는 변수가 있다고 치자!  해당 던전의 정보는 입장시 "최소 필요 피로도 수치" 와 "소모 피로도" 수치를 가지고 있다. 그리고 한번이라도 탐험한 던전에는 재입장 불가능이며 k 라는 피로도 수치가 주어지면 최대 몇번의 던전을 클리어 할수 있는지 리턴하는 함수를 작성하는 문제이다.제한 사항k는 1 이상 5,000 이하인 자연수dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하dungeons의 ..

Stream이란?Java 8부터 추가된 기술로 람다를 활용해 배열과 컬렉션을 간단하게 처리할 수 있는 기술이다. Java 8 이전에는 데이터의 요소를 관리하려면 반복문을 이용해서 하는 방법이였으나 Stream이 생긴 이후에는 함수 여러 개를 조합하여 결과를 필터링하여 가공된 결과를 얻을수 있게 되었고 이를 람다 표현식으로 사용했기에 가독성까지 챙길 수 있게 되었다.Stream의 특징Stream은 데이터를 변경하지 않는다.Stream은 일회용이다.Stream은 작업을 내부 반복으로 처리한다.Stream의 흐름생성하기 : 스트림 인스턴스 생성가공하기 : 필터링 및 맵핑 등 원하는 결과를 만들어가는 중간 작업결과 만들기 : 최종적으로 결과를 만들어내는 작업흐름 : 전체 -> 맵핑 -> 필터링1 -> 필터링2 ..