본문 바로가기

전체 글79

[SWEA] 1486. 장훈이의 높은 선반(부분집합/자바) 문제 요약 탑의 높이가 B 이상인 경우 선반 위의 물건을 사용할 수 있는데 탑의 높이가 높을수록 더 위험하므로 높이가 B 이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다. 문제 접근 방법 점원들의 키에 대해 일부를 선택하여 선택한 점원들의 키의 합이 B보다 큰 경우 결과 값에 대해 갱신한다. 점원들 중에서 일부를 선택하는 것은 부분 집합으로 구현해볼 수 있다. 현재 점원을 선택한 경우와 선택하지 않는 경우에 대해 재귀 함수를 호출한다. 특히, 현재 점원의 선택 여부를 확인하기 위해서 boolean 배열을 사용하였다. 현재 점원을 선택하면 true, 그렇지 않은 경우는 false로 세팅한다. 재귀 함수의 탈출 조건은 선택한 점원의 수가 N명이 되는 경우이다. 이 경우에 점원들의 키의 합을 구하고,.. 2022. 11. 5.
선형 자료 구조 본 게시글은 면접을 위한 cs 전공지식 노트를 토대로 작성되었습니다. 선형 자료 구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 형태 선형 자료 구조의 종류 선형 자료 구조의 종류로는 배열, 연결 리스트, 스택, 큐 등이 존재합니다. 1. 연결 리스트 각 데이터 요소들에 이전 데이터나 다음 데이터를 가리키는 참조를 부여하여 자료들을 연결하는 자료 구조를 말합니다. 이를 통해 공간적인 효율성을 극대화시킬 수 있습니다. 삽입과 삭제는 O(1)이 걸리며, 탐색에는 O(N)이 걸립니다.(참조를 따라가며 데이터를 전부 탐색해봐야 하므로 O(N)이 걸림) 2. 배열 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 이때, 삽입과 삭제에는 O(.. 2022. 11. 3.
[Algorithm] 다익스트라 알고리즘(자바) 다익스트라 : 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘 특히, 다익스트라 알고리즘은 음수의 간선 가중치를 허용하지 않습니다. 한 정점에서 다른 정점으로 가는 최단 거리의 문제를 접한 경우 양의 가중치가 있으면 다익스트라 문제이다!!!! 다익스트라 과정 다음은 다익스트라 알고리즘을 통해 최단 경로를 구하는 과정입니다. 1. 초기 상태 저는 1번 정점부터 시작하겠습니다. 1 2 3 4 5 0 INF INF INF INF 1 2 3 4 5 0 4 INF INF INF distance[2] > distance[1] + 4입니다. 이는 distance[2] = distance[1] + adjMatrix[1][2]를 의미합니다. 1 2 3 4 5 0 4 INF 10 IN.. 2022. 10. 30.
[SWEA] 1952. [모의 SW 역량테스트] 수영장(자바/dfs) 출력 각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때, 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램 문제 해결 방법 1년의 경우 dfs를 탐색할 필요가 없으므로, dfs 탐색을 돌기 전에 1년 비용을 미리 세팅합니다. dfs 탐색은 달을 기준으로 탐색하게 되며, 1일, 1달, 3달을 기준으로 돌게 됩니다. 12월까지이므로 cnt가 13이 되었을 때가 기저 조건이 됩니다. 이때 최소 비용을 갱신하며 결과값을 도출하게 됩니다. //package swea.p1952; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja.. 2022. 10. 28.

티스토리툴바