문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 맨 처음에는 그래프를 순회하면서 순위를 매기는 방법을 생각했었는데 다른 node 로 이동할 때마다 순위를 명확히 체크할 수 있다는 보장이 없어서 각 node 하나하나 마다 순위를 확정할 수 있는지 체크하기로 했습니다. 주어진 예제를 확인해보니 순위를 확정할 수 있는 node 는 아래 그림과 같이 자신보다 순위가 위 이거나 아래인 다른 모든 node 들을 찾았을 때 였습니다. 그래서 upperVisited 라는 자신보다 상위 순위에 있는 node 목록과 lowerVisited 라는 자신보다 하위 순위에 있는 node 목록을 node 마다 각각 생성했습니다. 이 두개의 길이가 본인을 제외한 전체 노드 갯수인 n - 1 이 될 경우 순위를 ..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 최단 경로로 이동했을 때 가장 멀리 떨어진 노드를 구해야 해서 BFS 알고리즘을 사용했습니다. BFS 는 다음에 탐색할 정보를 queue 에 넣기 때문에 depth 의 경우 shortestList 에 따로 저장하고 현재 노드인 curNodeNum 의 depth 에 1 을 더한 값을 nextNode 의 shortestList 에 추가했습니다. BFS 의 특성상 depth 는 증가만 하기 때문에 이미 최단경로의 depth 를 구한 경우에는 저장하지 않도록 했습니다. 최단경로를 모두 탐색하고 최종적으로 shortestList 에 있는 최대값의 개수를 counting 했습니다. 소스 코드 function solution(n, edge) { l..

문제 정보 프로그래머스 문제 링크 난이도 : level 4 해결 방법 현재까지 확인한 idx 번째 집에서 털 수 있는 돈의 최댓값을 dict 에 key-value 형태로 저장했습니다. 집 사이의 간격은 최대 3칸이 될 수 있어서 헷갈렸는데 ( 아래 이미지에 고뇌의 흔적이 보입니다. ) 현재까지 확인한 이라는 조건이 붙기 때문에 방범장치가 영향을 줄 수 있는 2칸만 확인하면 됩니다. 점화식으로는 아래와 같이 나타낼 수 있습니다. newDp = max(memoization1[idx - 1], memoization1[idx - 2] + money[idx]) 그리고 첫 번째 ( idx 값으로는 0 ) 집을 털지 여부를 판단하기 위해 selZero 라는 변수로 판단했습니다. 첫 번째 집을 털게 되면 마지막 집을 ..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 왼쪽 위 (1, 1) 부터 오른쪽과 아래로만 이동할 수 있는 최단거리 문제로 중학교(?) 교과 과정에서 많이 풀던 경로 문제입니다. 왼쪽 위부터 갈 수 있는 경우의 수를 표시하면서 왼쪽과 위의 경우의 수를 순차적으로 합산하여 구현할 수 있습니다. 그래서 Dynamic Programming 알고리즘을 사용해 구현했습니다. 처음 구현할 때는 두 가지 문제점이 있었는데 첫 번째는 중간에 웅덩이가 있을 경우 지나가지 못하는 경우를 중복으로 세서 물 웅덩이가 많을 경우 음수로 나와버리는 경우를 발견했는데 물 웅덩이에서의 경로의 수를 0 으로 세팅하여 해결했습니다. 두 번째는 위에서 기술했듯이 예전 교과 과정에서 많이 풀던 방식으로 인해 생긴 문..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 1. 문제에 명시된 대로 거쳐간 숫자의 합이 가장 큰 경우를 찾기 위해 Top-down 방식의 DP 를 사용하여 구현했습니다. 제출하니 시간이 많이 초과되어 다른 방법의 풀이를 시도했습니다. 2. 모든 경로를 반복해서 수행하지 않도록 특정 경로까지의 최대 값을 triangle 배열에 update 했습니다. 짧은 경로는 금방 구할 수 있기 때문에 Bottom-up 방식으로 구현했습니다. 소스 코드 # 시간초과 def solution(triangle): answer = 0 answerList = [] def dp(depth, curSum, idx): curNum = triangle[depth - 1][idx] curSum += curNum..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 모든 공항을 방문해야 하므로 DFS 를 사용했습니다. 소스 코드 function solution(tickets) { let answer = []; const visitedList = []; const visited = new Array(tickets.length); const vAirport = []; visited.fill(false); const dfs = function(tickets, cur, depth){ // 종료조건 if(depth == tickets.length){ vAir..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 단어를 변환할 수 있는 최소 단계를 구해야 하므로 BFS 를 사용합니다. DFS 를 사용할 경우 최소 단계를 발견하더라도 다른 경로를 모두 탐색해야 최소 단계임을 보장할 수 있기 때문에 비효율적이기 때문 입니다. 소스 코드 function solution(begin, target, words) { let answer = 0; // target 이 words 에 없는 경우 if(!words.includes(target)){ return answer; } // 방문여부 초기화 const vi..

포스팅 목적 알고리즘의 유형 중 완전 탐색 기법과 그 유형에는 어떤 것이 있는지 알아봅니다. 완전 탐색이란? 완전 탐색(Exhaustive Search)이란 가능한 경우의 수를 모두 확인하는 방법으로, 무식하게 푼다는 뜻의 Brute-Force 라고도 합니다. 완전 탐색 기법 완전 탐색 기법을 사용하기 위해서는 가능한 경우의 수를 중복 없이 모두 확인할 수 있는 순회 방법들을 사용합니다. 단순한 중첩 for 문 : 순회하는데 별다른 기법 없이 모든 경우를 셀 수 있을 때 사용합니다. 재귀 함수 : 순열 (permutation), 조합 (combination) 과 같이 반복적인 작업을 구현할 때 사용합니다. 2^n 경우의 수 : 개수의 제한 없이 포함이나 선택 여부를 판단해야할 때 사용합니다. 완전 탐색 ..

포스팅 목적 SQL 이 무엇인지 알아보고 데이터 조작을 위한 기본적인 SQL 문, 그리고 관련된 제약사항을 학습합니다. SELECT SELECT column names FROM table or view name WHERE search condition GROUP BY column names HAVING search condition ORDER BY column-name INSERT INSERT INTO table-name (column1, column2, ... ) VALUES (value-for-column1, value-for-column2, ... ) UPDATE UPDATE table-name SET column-1 = value-1, column-2 = value-2, ... WHERE sear..

포스팅 목적 비전공자, No Base 상태의 코딩 초보자에게 데이터 분석을 위한 파이썬 사용의 장점과 기초 문법을 학습합니다. 0. 프로그래밍 언어란? 파이썬이 무엇인지 이해하기 위해서는 프로그래밍 언어에 대한 설명이 먼저 필요합니다. 컴퓨터는 0과 1로 이루어진 이진 숫자만을 이해할 수 있는 반면에 사람은 0과 1로만 이루어진 프로그램을 이해하기 어렵습니다. 사람의 언어를 대신해서 컴퓨터라는 기계와 소통하기 위해 만든 언어가 프로그래밍 언어 입니다. 컴퓨터는 프로그래밍 언어를 바로 이해할 수 없기 때문에 프로그램(인터프리터, 컴파일러 등)을 사용해서 0과 1로 이루어진 기계어로 변환하여 의사소통을 할 수 있습니다. ( 아래 그림을 보면 어셈블리어라는 저급 언어가 있지만 개념은 같습니다. ) 이러한 프로..