Algorithm
[프로그래머스(파이썬/Python)] 키패드 누르기(2020 카카오 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 문제의 요구사항을 그대로 구현하면 됩니다. 키패드의 숫자의 위치를 dictionary 형태로 표현했는데 key = 키패드의 숫자, value = 숫자의 위치로 지정했습니다. 그리고 주어지는 각 숫자에 대해 해당 숫자가 1, 4, 7(맨 왼쪽 열)중 하나..
Algorithm
[백준(파이썬/Python)] 2225_합분해 - DP
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP를 맨 처음에 공부할 때 즈음에 배우는 피보나치 수를 DP로 구하기가 떠오르는 문제였습니다. 탑다운 방식으로 DP를 해결하는 방식인데, 이 문제 역시 문제 풀이의 로직만 생각해낸다면 구현은 탑다운으로 거의 똑같이 할 수 있는 것 같습니다. 이 문제가 DP의 정당성을 가지는 이유(부분 최적해가 전체 최적해를 보장하는 이유)는 각 자릿수가 하나라도 다르면 다른 경우의 수로 취급하기 때문이입니다. 예를 들어 어떤 수 N을 3개의 숫자로 표현한다고 해보죠. N = 0 + _ _ N = 1 + _ _ N = 2 + _ _ .....
Algorithm
[백준(파이썬/Python)] 8983_사냥꾼 - 이분탐색
https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 모든 사대에서 사격 가능한 영역을 구하고, 그 영역 안에 동물들이 있는지를 확인하는 방식으로 풀었을 때 시간복잡도가 O(M*N*L)이 소요됩니다. 비효율적이죠. 따라서 이분탐색을 통해 각 동물의 위치에서 가장 가까운 사대의 위치를 찾고 그 거리가 사정 거리 안에 있는지를 확인해주는 방식으로 문제를 풀었습니다. 각 동물의 위치에서 가장 가까운 사대의 위치는 x좌표가 가장 가까운 사대이기 ..
Spring & Springboot
[스프링/Spring] 의존관계 주입(DI)은 어떻게 할 수 있을까? - 여러가지 의존관계 주입 방법
🧑💻 들어가면서 의존관계 주입은 객체 지향 설계를 하는 데 있어서 정말 중요한 개념이죠. 의존 관계 주입 없는 쌩 자바 코드만으로는 DIP, OCP 등의 객체지향 설계 원칙을 지키기 힘들고, 객체끼리 서로 의존할 수밖에 없는 상황이 발생하기 때문입니다. 의존 관계 주입이 왜 필요하고 무엇인지에 대한 내용은 이전에 정리한 글도 있으니 참고하실 분들은 참고하시면 좋을 것 같습니다. [스프링/Spring] 객체 지향 설계와 DI(Dependency Injection)의 시작(feat. 생성자 주입) 👻 0. 들어가면서 이전 포스팅에서 스프링이 만들어지고 각광받는 이유가 "객체 지향 프로그래밍의 장점을 극대화할 수 있기 때문"이라고 했다. 그리고 객체 지향 프로그래밍이란 '컴포넌트를 studyandwrite...
Algorithm
[백준(파이썬/Python)] 두 용액 - 이분탐색, 투포인터
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net '맞왜틀'을 엄청 반복했던 문제입니다... 이 문제에서 약간 트릭(?)이었다고 생각하는 부분은 산성과 알칼리 용액이 모두 존재했을 때에도 한 종류의 용액 두 개를 골라 혼합했을 때가 최적해가 될 수 있다는 것입니다. 예를 들어 -100, -50, 1, 2라고 주어졌을 때 정답은 1+2 = 3이 되어야 하는데, 잘못 생각하면 abs(-50 + 2) = 48 이라고 ..
Algorithm
[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS + DP를 이용한 문제입니다. 우선 이 문제를 DFS로만 풀려면 가능한 모든 경로의 수를 다 세야하기 때문에 정말 많은 경우의 수가 나오게 됩니다. 그러면 시간초과가 뜨겠죠? 500 * 500 배열에서 계속해서 상하좌우로 이동이 가능한 상황을 떠올려 보면 직관적으로 느낄 수 있습니다. 따라서 이 문제는 DP를 이용해서 불필요한 연산을 줄여야하는데, 이를 위해서는 우선 DP의 사용 정당성에 대해 ..
Spring & Springboot
[스프링/Spring] 싱글톤(Singleton) 패턴과 스프링 컨테이너
📖 싱글톤 패턴이란 무엇일까? 스프링은 기업용 온라인 서비스 기술을 지원하기 위해 탄생했고, 웹 어플리케이션은 보통 여러 고객이 동시에 요청을 보냅니다. 위와 같은 그림의 예시에서 세 명의 클라이언트가 동시에 어떤 요청을 보내게 되면, DI 컨테이너는 memberService를 생성해서 반환해줍니다. 하지만 이 상황에서는 고객의 요청만큼 객체가 계속 생성되고, JVM 메모리에 객체가 계속 쌓이는 문제가 발생합니다. 아래 테스트 코드와 결과를 통해 확인해보죠. public class SingletonTest { @Test @DisplayName("스프링이 없는 순수한 DI 컨테이너") void pureContainer(){ AppConfig appConfig = new AppConfig(); // 1. 조..
Algorithm
[프로그래머스(파이썬/Python)] 튜플 - 문자열 처리
https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 처음에 주어진 문자열 s를 리스트로 바꿔서 처리하기 위해 크게 1) 여는 대괄호, 2) 쉼표, 3) 닫는 대괄호, 4) 숫자일 때로 조건을 나누어 처리했습니다. 위 과정을 통해 주어진 문자열 s를 리스트 형태로 바꾸고 나면, 해당 이차원 리스트를 길이 순으로 정렬하고 길이가 짧은 리스트의 앞에서부터 결과 리스트..
Algorithm
[백준(파이썬/Python)] 15683_감시 - 구현, 시뮬레이션
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이 문제에서 핵심적인 부분은 어떻게 모든 카메라의 관찰 방향의 조합을 다 찾아서 그 때의 감시를 받지 않는 구역의 개수를 체크할 것인가입니다. 저같은 경우에는 카메라마다 감시 방향도 깔끔하게 떨어지지가 않아서 카메라 1~5번 마다 cam{n}_direction이라는 방향을 입력해주었고, 감시 방향을 순회하기 위해 [[방향1의 방향들], [방향2의 방향들]...] 식으로 3차원 리스트를 ..
Algorithm
[백준(파이썬/Python)] 10282_해킹 - 다익스트라
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제의 조건 중에서 "d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다." 라는 표현이 있습니다. 이 부분을 주의해서 각 노드(컴퓨터)의 방향성을 정해줘야 합니다. 즉, a에서 b로 방향이 생기는 것이 아니라, b에서 a로..
