전체 글
프로그래머스 [2020썸머코딩] 코딩테스트 합격 후기
썸머코딩이란 프로그래머스에서 주최하는 프로그램으로, 졸업예정자, 졸업자에게 방학 약 2달 동안 스타트업 기업들에서 인턴을 할 수 있는 기회를 주는 프로그램입니다. 이 썸머코딩 프로그램에서 지원 할 수 있는 기업들은 대표적으로 Watch, 당근마켓, 태거스와 같은 좋은 투자를 받고 있는 회사들이 있습니다. 그리고 한 번 지원할 때 회사는 최대 5개만 지원을 할 수 있습니다. 그렇기 때문에 스타트업에서 인턴을 하고 싶어하는 많은 학생들이 지원을 하는데, 이때 기업들에게 서류를 제출하기 위해서는 먼저 프로그래머스에서 여는 코딩테스트의 벽을 넘어야합니다. 이번 2020 썸머코딩 코딩테스트에는 총 4문제가 나왔는데, 알고리즘 3문제와 SQL 1문제로 구성되어있었습니다. ※ 아! 그리고 저는 원래 알고리즘을 C++..
[VueJS] NuxtJS를 통해 VueJS 프로젝트 만들기 (feat. Typecript)
☞ NuxtJS를 이용해 VueJS 애플리케이션을 만들 수 있는 프로젝트 어떻게 생성할까? ☞ 먼저 NuxtJS가 무엇인지 살펴보면, Nuxt는 현대 웹 애플리케이션을 만들기 위해 Vue.js를 기반으로 하는 진보적인 프레임워크입니다. Nuxt는 Vue.js의 공식 라이브러리(vue, vue-router 및 vuex)와 강력한 개발 도구(webpack, Babel and PostCSS)를 기반으로 합니다. Nuxt의 목표는 뛰어난 개발자 경험과 함께 강력하고 뛰어난 웹 개발을 가능하도록 하는 것입니다. https://ko.nuxtjs.org/guide/ 소개 Nuxt는 현대 웹 애플리케이션을 만들기 위해 Vue.js를 기반으로 하는 진보적인 프레임워크입니다. Vue.js의 공식 라이브러리(vue, vue..
세그먼트 트리 (구간 트리, Segment Tree)
☞ 세그먼트 트리란 이름 그대로 저장된 자료를 적절히 구간별로 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 해주는 트리입니다. 예를 들어 A={1,2,3,4,5}에서 [2,4] 구간의 최소치를 알고 싶다면 해당 배열을 순회하며 찾는 방법도 있지만, 해당 배열을 전처리해 세그먼트 트리를 생성해 더욱 더 빠르게 구현 할 수 있습니다. A배열을 세그먼트 트리로 바꾼 후 -> 아래처럼 구간별로 나눠 세그먼트 트리를 만들 수 있다. ☞ 이렇게 이론적으로만 설명했지만, 코드 구현에 많은 어려움이 있을 수 있습니다. 그래서 세그먼트 트리 문제의 한 유형인 구간 최소 쿼리(range minimum query,RMQ)를 구현해보겠습니다. ※ 여기서 중요한 점은 세그먼트 트리에 초기 크기를 설정해줘야하는데 가장..
[백준] 11657번 - 타임머신 (벨만-포드 알고리즘)
☞ 이 문제에서는 음수 간선이 존재하며, 출력 내용에서의 "만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다." 를 보면 그래프에 음수 사이클이 존재하는 경우 -1을 출력하라는 말이라고 볼 수 있다. 따라서 음수간선이 존재하며 음수 사이클의 존재를 판단 할 수 있는 '벨만-포드 알고리즘'을 사용하면 된다. '벨만-포드 알고리즘'은 아래에 잘 설명이 되어있으니 참고해주세요. https://withseungryu.tistory.com/34 벨만-포드 알고리즘 (Bellman-Ford Algorithm) ☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로..
벨만-포드 알고리즘 (Bellman-Ford Algorithm)
☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로를 구해도 될까? -> 정당성에 성립되지 않습니다. 따라서 음수 간선이 존재하고 음수 사이클이 존재한다는 것을 확인하고 싶을 때 Bellman-Ford Algorithm을 사용해야합니다. ☞ 벨만-포드 알고리즘이란 무엇일까? 벨만포드 알고리즘 원리는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식입니다. 여기서 상한은 upper 배열에 저장하며 이 upper의 값은 알고리즘이 진행됨에 따라 점점 줄어들고 알고리즘이 종료되면 실제 최단 거리를 담게 되는 원리입니다. ☞ 벨만-포드 알고리즘 동작..
[백준] 2014번 - 소수의 곱
☞ 이 문제에서 가장 중요하게 생각 할 점은 배열에 저장되어 있는 소수들을 어떤 방식으로 곱해야 최대한 순서대로 저장시킬 수 있도록 해줘야 합니다. 그냥 순서대로 처음에 한개씩 다음에 2,2 2,3 2,4 2,5와 같이 2개씩 계산을 해서 우선순위 큐에 저장시켜주면 나중에는 같은 수로 곱하여도 차이가 많이 나기 때문입니다.(예를 들어 2*2*2 와 7*7*7의 차이가 어마어마하다.) 따라서 여기서 우선순위 큐를 이용해 앞에 있는 수와 배열에 저장되어 있는 수들을 곱해 우선순위 큐에 저장시킨 후 다시 앞에 있는 수와 배열에 저장되어 있는 수들을 곱하는 방법을 반복한 후 N-1번째까지 반복 한 후 맨 앞에 있는 수가 정답이라는 것을 알 수 있었습니다. 여기서 2*2 를 하고 2*3 2*5를 가는 것보다 맨 ..