복's

https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 알고리즘 문제를 오랜만에 포스팅 합니다. 그래프 탐색을 이용하는 알고리즘 문제로, 그래프 탐색의 변형 보다는 이용이라고 하는게 맞는 것 같다. 처음 문제를 접했을 때는 시간 효율에 대해서는 생각 하지 않고, 풀이에만 집중해서 문제를 풀었더니 효율성 테스트에서 걸려서 자료 구조부터 다시잡고 시작했다. (사실 초기에는 방문 처리도 별도의 자료 구조를 갖고 했는데 효율성에 걸리다 보니 불필요한 코드를 모..

📌 왜 정리하게 되었을까?빌더(Builder) 패턴을 접한지는 정말 오래 되었다.개발을 시작할 때 맨 처음 접한 곳은 이펙티브 자바(Effective Java) 였고, 실무에서 사용할 때는 lombok 이 제공하는 @Builder 를 사용 했었다. Builder 클래스를 내부 클래스(Inner Class)로 만들어서 사용하는 부분은 반복되는 보일러 플레이트(Boilerplate) 코드이기 때문에 직접 구현할 일은 없었는데, 최근에 테스트 코드를 공부하면서 오랜만에 Builder 클래스 코드를 보고 정리를 마음 먹었다. 그렇다면 언제 빌더 패턴을 고려하고 사용해야 할까?📌 생성자에 매개변수가 많을 때생성자가 많을 때 Java 에서는 어떻게 대응할 수 있을까? 나는 가장 먼저 생각나는 예시는 서브웨이 샌..

[ 📌 서론 ]프로그래밍을 하다가 보면 고정된 상수(Constant)가 필요한 경우가 있다.예를 들면 월,화 ~ 토,일요일을 표현하기 위해서는 아래와 같은 여러가지 표현을 할 수 있는데public class Day { final static int MONDAY = 1; final static int TUESDAY = 2; final static int WEDNESDAY = 3; final static int THURSDAY = 4; final static int FRIDAY = 5; final static int SATURDAY = 6; final static int SUNDAY = 7;}이렇게 숫자로 표현해도 괜찮고, String 타입으로 변경해도 좋다.publi..

[ 📌 서론 ]https://www.acmicpc.net/problem/2458 단순히 그래프 탐색으로도 풀이가 가능할 거라고 생각은 되는게 그래프를 정, 역방향 2개 만들고 탐색 알고리즘을 수행한다면정방향: 나보다 큰 키의 학생들역방향: 나보다 작은 키의 학생들선택한 노드 기준으로 다른 학생들과의 키 상하 관계를 알 수 있을 것 같지만, 나는 플로이드-워셜 알고리즘을 연습하기 위해서 알고리즘 분류에서 선택해서 문제를 골랐다.[ 📌 풀이 ]중요한점은 어떤 노드가 크고 작은지가 중요한게 아니라 도달할 수 있는지가 중점이다. 그래프 구성하기도달 여부만 알면 되기 때문에 true/false 로 노드 관계를 구성했다.정방향은 입력으로 주어진다.플로이드-워셜 알고리즘 수행경유 노드를 거쳐서 도달할 수 있는지 ..

https://www.acmicpc.net/problem/11404 플로이드 워셜(Floyd-Warshall) 알고리즘을 접하게 되어서 알고리즘 연습을 위해서 찾다가 풀게된 문제다.예전에 문제를 풀 때 다익스트라 알고리즘은 음의 가중치를 해결하지 못해서 고민하다가 이름만 기억하고 있다가 기회가 왔을 때 문제로 연습 하였다.[ 📌 풀이 ]그래프 구성다른 그래프 문제와 동일하게 출발 -> 도착 (비용) 을 기록할 수 있도록 구성한다.플로이드 워셜 알고리즘경유 노드를 정해서 다른 노드가 지나가면서 INF 로 설정했던 경로를 도달할 수 있는지 체크한다.V^3 시간 복잡도를 갖고, V^2 의 공간 복잡도를 갖기 때문에 불필요한 연산을 최소로 한다.출력 값 포맷 맞춰주기문제에서 요구하는 출력 방식을 맞춰준다. (..

Java 를 사용해서 일을 시작하게 되면서, 소스 코드 리딩을 하고 있는데 서버 사이드에 있는 코드들에 String Literal 연산이 많이 보여서 의문을 가지게 되었다. 의문의 시작은 내가 알고 있는 String 에 대한 기본 지식들에서 시작하는데기본적으로 String Literal 은 value 가 같다면 String Constant Pool 에 존재하고, 같은 값은 가지는 String 들이 같은 주소를 참조하고 있다는 것이다. (이름이 참 많다 => String Pool, String Literal Pool, String Constant Pool) 📌 내가 Java 에서 String 을 다룰 때 기본적으로 기본적으로 생각하는 개념test1과 test2는 equals() 를 사용하지 않아도 같은 ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제의 본질은 최단거리를 구하는 문제로 그래프 탐색중에서 BFS 알고리즘을 사용해서 푸는 문제다. [ 📌 풀이 ] 일반적인 BFS 로직에 조건 하나 추가 해주면 된다. 조건: 타겟으로 하는 층에 도달할 시 종료 [ 📌 주의 사항 ] 목표로 하는 층 보다 높아지거나 낮아 지는건 조건에서 필요 없다. 목표 층을 넘어가도 다시 내려가거나 올라가면 도달하는 최단거리가 있음 다음 층을 연산할 때 인덱스를 넘기면 안된..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리가 주어지고 그래프를 구성해서 그래프 탐색 알고리즘을 사용해서 푸는 문제이다. 목표는 리프 노드의 개수를 구하는 것이고, 고려 조건은 단 1개로 1개의 지워지는 노드가 있다는 점이다. [ 📌 풀이 ] 루트 노드를 기록해두었다. (탐색 시작 기준을 정하기 위해서) 지워지는 노드가 있기 때문에 임의의 노드를 기준으로 탐색을 하게되면 안된다. 지워지는 노드는 그래프에 넣지 않았다. 지워지는 노..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 물 수위에 따라서 수면에 잠기지 않은 붙어있는 영역을 구하는 문제로 간략하게 설명할 수 있을거 같다. 그래프 탐색 알고리즘을 사용해서 문제를 접근했다. [ 📌 고려사항 ] N은 2 이상 100 이하 -> 지역의 총 크기는 100 * 100이 최대 사이즈다. H(높이)는 1이상 100 이하 -> 최대 101번의 높이에 대해서 실행해야 한다. [ 📌 풀이 ] 1. 입력받은 영역들 중에가 가장 높은 지대의 높..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 3번째 풀면서 익숙해져버린 문제 스택을 이용하는 문제인데 다른 알고리즘 보다도 스택을 사용하는 어려운 문제가 진짜 힘든 것 같다. [ 📌 풀이 ] 일반적인 완전 탐색의 방법으로는 시간 초과가 나는 문제다. 탑의 개수가 500,000 개까지 들어오는데 매번 탑이 스택에 들어올 때 마다 확인 하는건 좋지 않다. 주어진 규칙을 활용하자. ◀︎⎯⎯⎯⎯⎯⎯🀆 🀆 🀆◀︎⎯⎯⎯︎⎯⎯⎯⎯⎯⎯⎯🀆 ◀⎯🀆 🀆 🀆..