Algorithms
1.[백준] 다리 만들기 - python (2146번)
가능한 경우들을 탐색하며 최솟값을 찾는 문제이기 때문에 bfs로 접근하는 것이 합당하다고 생각하였습니당섬들의 정보들을 담고 있는 islands 리스트를 만듭니다.예를들어 주어진 2차원 배열(나라)이이라면이 됩니다.
2.[백준] 치즈 - python (2638번)
전체적인 풀이 방향 1. 항상 (0, 0)부터 보면서 외부 공기를 탐색합니다. 모눈종이를 (0,0)부터 탐색하며 맞닿아있는 공기, 즉 외부공기들을 모두 0 -> 2로 바꾸어준다. 이때 모눈종이를 복사하여 바꿔줘야 합니당. 2. 외부공기를 복사한 모눈종이에 2로 바꿔준 뒤 원본 모눈종이에서 치즈들을 탐색하면서 2면 이상이 외부공기와 맞닿아있는 치즈를 0으로...
3.[백준] 연구소 3 - python (17142번)
풀이 전략 하나 씩 탐색하며 최솟값을 찾는 문제는 대부분 BFS 알고리즘을 적용하여 푸는 것이 정답입니당 풀이 과정 1. 빈 칸 세주기 바이러스가 모든 빈 칸에 다 퍼졌는지 나중에 확인하기 위해 처음 빈 칸의 갯수를 미리 세줍니다. 2. 바이러스 위치 정보 저장 바이러스들의 위치를 담고있는 리스트를 만듭니다. 3. combinations로 탐색하기 모든 ...
4.[백준] 가장 긴 바이토닉 - python (11054번)
풀이 전략 가능한 모든 경우의 수를 생각하는 것은 무리라고 생각이 들었습니다. 수열 길이가 최대 1000이기 때문입니다. 따라서 다이나믹 프로그래밍 (DP)로 풀어야 겠다고 생각하였습니다. DP 로직의 포인트는 바이토닉 수열에서 꺽이는 점, 즉 바이토닉 수열이 증가하다 감소하는 형태이니 수열의 값들 마다 해당 값이 꺽이는 점 일때 바이토닉 수열의 최대 길...
5.[백준] 경사로 - python (14890번)
풀이 전략 행과 열, 총 2N개의 리스트를 차례로 탐색하며 경사로를 설치할 수 있는지 확인하면 된다고 생각하였습니다. 함수로 구현하지 않아도 되지만 함수로 구현하면 중간중간 경사로 설치가 불가능 할 때 return문으로 빠져나올 수 있는 장점이 있습니다. 풀이 과정 1. 행, 열을 하나씩 함수에 넣어 경사로를 만들 수 있는지 체크 2. 경사로 체크 함수가...
6.[프로그래머스] 귤 고르기 - JavaScript
가장 갯수가 많은 종류 부터 골라야 가장 적은 종류로만 선정할 수 있습니다.따라서 먼저 tangerine 리스트를 갯수를 기준으로 파악해야 합니다.tangerine 리스트 자체를 정렬할 수도 있지만 갯수를 기준으로 sorting하는 것은 코드가 길 뿐만 아니라 시간도
7.[프로그래머스] 정수 삼각형 - JavaScript
동적 계획법을 사용하여 실행 시간을 줄여야합니다.위에서 부터 아래로 내려가며 최댓값만을 저장하며 진행합니다.for문과 if문의 조건절에 있는 n들을 n으로 미리 계산하지 않고 trianglei.length로 하면 그때 그때 계산해야 해서 시간이 더 걸리게 됩니다.
8.[프로그래머스] 최고의 집합 - JavaScript
합이 일정한 숫자들의 곱이 최대가 되기 위해서는 숫자들의 차이가 가장 적어야합니다.이는 산술-기하 정리를 이용하여 어렵지 않게 확인할 수 있습니다.따라서 주어진 's' 라는 숫자를 n개로 가장 균등하게 나눠야합니다.예를 들어 n = 5, s = 3인 상황에서는 아무리
9.[프로그래머스] 네트워크 - JavaScript
인접한 것을 탐색해 나가거나 그룹을 세는 것은 항상 DFS 또는 BFS로 컴퓨터에게 모든 작업을 맡기는 것이 가장 간단합니다. 물론 어떤 문제는 더 깊게 고민하면 더 빠른 풀이가 있을 수 있습니다.JavaScript로 알고리즘 문제를 풀 때는 deque는 구현하여 사용
10.[프로그래머스] 스티커 모으기(2) - JavaScript
우선 문제를 처음 보면 많은 풀이법이 생각난다.DFS/BFS를 통해 완전 탐색을 하며 최댓값을 도출하는 방법, deque를 통해 rotate시키며 해결하는 방법.하지만 JavaScript로 풀기에 배열을 계속해서 사용하는 것은 효율성 측면에서 옳지 않기에 DP로 푸는
11.[프로그래머스] 징검다리 건너기 - JavaScript
정답 알고리즘 - 이분탐색처음에는 여러가지 방법이 떠올랐습니다.첫 번째는 stones배열을 0번째 인덱스부터 k+2길이만큼 슬라이싱해서 젤 앞과 젤 뒤가 가운데 k개들 보다 큰지를 비교하는 것입니다. 그렇게 해서 가운데 k개들 보다 크다면 그 구간을 지나갈 수 없는 것
12.[프로그래머스] 수레 움직이기 - JavaScript
보통 최소 횟수 탐색의 경우 BFS로 푸는 것이 더 좋은 접근입니다BFS는 탐색 완료 조건을 만나면 그곳에서 바로 함수를 종료하면 결과는 항상 최소 횟수이기 때문이죠하지만 이런 문제의 경우 BFS로 푼다면 각 경우에 대해서 이전 상황을 알기 위해 visited 배열을
13.[프로그래머스] 상담원 인원 - Python & JavaScript
각 상담 유형 별로 상담원이 n명 있을 때 총 기다리는 시간이 몇 분인지를 미리 계산해 놓는다!상담 유형 별로 최소 1명씩 있어야 한다.테스트케이스 1번의 경우 상담원이 배치되는 경우는(1,1,3)(1,2,2)(1,3,1)(2,1,2)(2,2,1)(3,1,1)총 6가지
14.[프로그래머스] 고고학 최고의 발견 - javascript