Computer Science/알고리즘(백준+프로그래머스)
백준 12865) 평범한 가방 - Python
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제 2. 문제 풀이 방식 기본적인 0/1 Knapsack 문제이다. 우선 무게를 고려해 물건을 담는 경우의 수는 두가지가 있다. 배낭 무게보다 물건이 무거워서 물건을 못담는 경우 물건을 담을 수 있는 경우 여기서 가치를 고려했을 때 두가지 경우가 또 갈라진다. 이 물건을 포함했을때의 가치 이 물건을 포함하지 않았을 때의 가치..
프로그래머스 Lv4- 징검다리
https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 1) 문제 분석 출발지점~ 도착지점 까지의 거리가 distance만큼 떨어져 있으며, 그 사이에 바위들이 놓여있다. 이 바위들이 놓여져 있는 지점을 rocks라는 배열에 저장한다. 그중 바위를 n개 만큼 제거하는데, 각 경우에서 각 지점 사이 거리의(출발, 끝지점 포함) 최솟값이 가장 큰 값을 return하도록 한다. 2) 코드 def solutio..
프로그래머스 level 3- 네트워크
https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr #Idea : 주로 dfs는 인접그래프로 많이 문제를 풀었는데, 배열로 풀어야 해서 살짝 헷갈리는 부분이 있었다. 그렇지만 별다를 것 없이 각 index를 edge로 생각해서 한 노드부터 아직 방문한 적이 없고 인접한 노드로 dfs를 해나가면 그 노드와 연결되어있는 연결 성분을 찾을 수 있다. 그리고 이전 시작 노드와 연결되어있지 않아 아직 방문되지 않은 ..