Algorithm
[백준(파이썬/Python)] 11779_최단경로 구하기2 - 다익스트라
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 통해 최단거리를 구한 후, 최단 거리에 대한 경로를 출력을 요구하고 있습니다. 따라서, 일반적인 다익스트라 구현에 경로를 출력하기 위한 구현이 추가로 필요한데 이 부분은 아래 코드에서 parents라는 딕셔너리로 구현햇습니다. 현재 지점에서 다른 지점으로 넘어가면서 최단거리를 갱신할 때 다음 지점의 부모를 현재 지점으로 설정해주는 것..
Algorithm
[백준(파이썬/Python)] 2665_미로만들기 - BFS, 우선순위 큐
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 얼마 전에 풀었던 백준 1261번(알고스팟, https://www.acmicpc.net/problem/1261) 문제와 동일하게 풀 수 있었던 문제입니다. BFS와 우선순위 큐를 이용하는데, 검은 방에서 흰 방으로 바꾸는 횟수를 최소화해야 하므로 우선순위 큐의 첫번째 원소를 '지금까지 흰색으로 바꾼 검은 방의 갯수'로 지정해주면 됩니다. 이렇게 하는 이유는 매번 우선순위 큐에서 원소를 뽑을 때마다..
Algorithm
[백준(파이썬/Python)] 4485_녹색 옷 입은 애가 젤다지? - 다익스트라
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 이차원 배열을 이용해야 하는 다익스트라 문제였고, 우선순위 큐를 활용해서 O(N^2*logN)의 시간복잡도 안에 해결할 수 있습니다. 많이 풀어봤던 노드와 간선 형태의 그래프 문제에서 상하좌우로 탐색해주는 부분만 조금 다르게 구현하면 어려운 부분은 없습니다. 추가적으로, 여러 개의 테스트 케이스에 대한 답을 연속해서 출력해야 하기 때문에 tc = 1로 초기화하고 출력을 할 때마다..
Spring & Springboot
[스프링/Spring] 스프링 컨테이너(Spring Container)와 스프링 빈(Spring Bean)에 대해 알아보자.
📚 0. 들어가면서 이전 포스팅에서 의존관계 주입(DI)가 왜 필요한가에 대해 예제 코드를 가지고 이야기해보았습니다. 궁극적으로 DI는 객체지향 설계의 원칙인 DIP와 OCP를 지키기 위한 노력에서 탄생했다는 것을 알 수 있었습니다. 이번 시간에는 예전에 자바로 작성했던 AppConfig를 스프링을 이용해 리팩토링해보고, 이 때 사용되는 스프링 컨테이너와 빈(Bean)의 개념에 대해 공부해보려고 합니다. 💻 1. 예제 코드 우선 아래처럼 자바 기반으로 작성한 코드가 있다고 해봅시다. MemberRepository는 멤버를 저장하는 데이터베이스이고 discountPolicy는 어떤 물건을 살 때 적용되는 할인 정책입니다. 그리고 orderService를 통해 멤버는 주문을 하게 됩니다. 지금은 AppCon..
Algorithm
[백준(파이썬/Python)] 1261_알고스팟
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net BFS와 우선순위큐(heapq)를 동시에 활용해서 푸는 문제입니다. 현재까지 부순 벽의 수를 count라는 변수에 저장하고, 상하좌우로 이동을 하며 벽이면 count+1, 벽이 아니면 count값을 그대로 우선순위 큐에 넣어주면 됩니다. 일반적인 bfs와는 다르게 우선순위 큐를 이용해야 하는 이유는 벽을 깨는 횟수를 "최소한"으로 하기 위해서인데, 다음 방문할 곳 중에서 벽이..
Algorithm
[프로그래머스(파이썬/Python)] 상호 평가
https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 올 해 네이버 공채 코딩테스트에서 봤던 문제랑 똑같은 문제입니다. 프로그래머스에 네이버 문제도 오픈되는 것 같네요. 본론으로 들어가서, 이 문제는 당시 코딩테스트에서 1번 문제로 나왔을만큼 어렵지 않은 문제입니다. 다만, 이 문제에서 가장 중요한 포인트는 "문제를 잘 읽어야 한다"는 점입니다. 알고리즘..
Spring & Springboot
[Spring/React] CORS? CORS에러를 해결해보자
1. 들어가면서 CORS 에러는 누구나 한번쯤 만나보게 되는 고통스러운 문제입니다. 저 역시 인턴을 하면서 CORS 문제 때문에 하루종일 골머리를 앓았는데요. 이렇게도 해보고 저렇게도 해보고 하면서 결국 “프록시 우회”로 해결하긴 했는데, 그 시간을 되짚어보면서 정확히 CORS란 무엇이며 이로 인해 일어나는 에러를 어떻게 해결해야는지 정리해보려고 합니다. 2. 교차 출처 리소스 공유(CORS) 교차 출처 리소스 공유(Cross-Origin Resource Sharing, CORS)는 HTTP 헤더를 사용해서 한 출처에서 실행 중인 웹 어플리케이션이 다른 출처의 선택한 자원에 접근할 수 있는 권한을 부여하도록 브라우저에 알려주는 체제입니다. 무슨 말일까요? 만약 https://domain-a.com의 자바..
Algorithm
[백준(파이썬/Python)] 10830_행렬 제곱
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 거듭제곱의 연산 수가 100,000,000,000까지 갈 수 있기 때문에 일일이 계산하는 것은 불가능한 문제입니다. 따라서 분할 정복 개념을 바탕으로 거듭제곱근으로 나눠나가는 아이디어를 떠올려야 합니다. 예를 들어 A^100 = A^50 * A^50이고, A^5 = A^2 * A^2 * A처럼 차수를 2의 제곱근으로 떨어뜨릴 수 있는 것이죠. 한편, 행렬의 곱셈 연산은 multyplyMatrix(m1, m..
Spring & Springboot
[스프링/Spring] 객체 지향 설계와 DI(Dependency Injection)의 시작(feat. 생성자 주입)
👻 0. 들어가면서 이전 포스팅에서 스프링이 만들어지고 각광받는 이유가 "객체 지향 프로그래밍의 장점을 극대화할 수 있기 때문"이라고 했습니다. 그리고 객체 지향 프로그래밍이란 '컴포넌트를 쉽고 유연하게 변경'하는 것을 목표로 하며, 이를 위해서는 역할(인터페이스)과 구현(객체)을 분리하는 과정이 핵심이라고 설명했습니다. [스프링/Spring] 스프링(Spring)은 왜 만들어졌는가? 🏃 0. 들어가면서 정말 많은 기업에서 스프링을 쓰고 있다. 스프링이 무엇이길래, 어떤 점이 좋기에 개발 생태계에서 정말 중요한 프레임워크로 자리매김했을까. 이번 글에서는 스프링은 왜 만 studyandwrite.tistory.com 🤔 1. 객체 지향 프로그래밍을 위한 시도 자, 그렇다면 이제 "다형성을 활용해서 인터페이..
Algorithm
[백준(파이썬/Python)] 5639_이진 검색 트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이 문제는 시간초과 때문에 고통받았던 문제입니다. 아래는 기존의 풀이이고 이렇게 하면 (전위순회를 통해 트리를 생성하는 시간) + (후위순회를 하는 시간(덤으로 재귀까지))때문에 시간초과가 발생합니다. 기본적인 트리 순회는 스택이나 재귀를 이용해서 하면 되지만 이 문제에서는 효율적인 탐색을 요구한 것이죠. // 시간초과 import sys sys.setrecursionlimit(10 ..
