devely

내일이 시험이기도 하고, 이번주 배운 내용 정리하고, 구현할 수 있는 구조(템플릿)이 있는 알고리즘은 간단히 복습을 해보려고 한다. [01. 완전탐색] - Brute Force 알고리즘이라고 부르며, 모든 가능한 조합, 순열을 만들어 답을 찾는 알고리즘 - 순열과 조합 - 시간복잡도가 매우 높지만, 특정 문제에 대해 최적의 해를 보장한다 예시 : 주어진 배열에서 조합만들기 package src.com.company.week3.day5; import java.util.ArrayList; import java.util.List; public class BruteForceCombinationExample { // 모든 조합 찾기 public static List generateCombinations(int[]..

오늘은 DP(dynamic programming) 에 대해 배웠다. 증명하는데 매우 힘들었는데, 내 설명이 부족한 탓인지.. 이해를 못시켜 드린 것 같아 블로그에 남겨본다.. 지금은 이해 하셨겠지만 혹시나 !! 제 블로그를!! 보시게 된다면!! 설명을 못드려 죄송하다는 말씀을 남기고 싶습니다 해설은 링크 남길게요! https://devdevleyy.tistory.com/41 [백준_2293] 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연 devdevleyy.tistory..

오늘은 그리디와 다엑스트라알고리즘에 대해 배웠다 사실 BFS 와 다익스트라의 차이점은 아직도 잘 모르겠다. 그래서 오늘 배운 것들에 대해 정리해보려고 한다 1. 목적 - BFS : 시작 정점에서 출발, 그래프를 가까운 정점까지 방문하는 탐색알고리즘, 깊이나 구조 파악하는데 사용 - 다익스트라 : 주어진 출발점에서 최단경로를 찾는 문제 2. 가중치 ⭐️ - BFS : 모든 간선의 가중치가 동일 - 다익스트라 : 간선의 가중치가 있는 그래프 3. 구현 - BFS : 일반적으로 Queue를 사용 - 다익스트라 : Priority Queue(우선순위 큐 사용), 현재까지 알려진 최단 경로에 따라 정점탐색 4. 시간복잡도 V : 정점의 수, E: 간선의 수 - BFS : 인접리스트 : O( V + E ) - 다익..

오늘 목요일이라고?? 목요일?? 진짜로요?? 네 항해를 하면 시간이 엄청 빨리갑니다.. 나.. 진짜 열심히 살았다고 생각했는데 덜 열심히 살았나보군.. 항해를 하면서 체험해 가고 있습니다.. 그래서 오늘 TIL은 머리도 식힐 겸 좋은 문제를 정리해 보았다! https://devdevleyy.tistory.com/36 [백준_8911] 거북이 https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설 devdevleyy.tistory.com [사담] 사담이지만.. 오늘 문제 난이도 무엇입니까? 그리고 저에게 4번까지 푸는건 매우 힘드..

https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 구현문제 기본이라서 가지고 왔다. 방향을 설정해 이동시키는 로직이다. [문제 요약] 실버 3단계 문제입니다. 0,0 위치에서 위(북쪽)을 바라보는 거북이 로봇이 있다. 제공되는 문자에 따라 - F: 한 눈금 앞으로 - B: 한 눈금 뒤로 - L: 왼쪽으로 90도 회전 - R: 오른쪽으로 90도 회전 하며 움직이고, 움직인 좌표를 모두 포함하는 가장 작은 직사각형의 넓이를 구하면 된다 [입력 이해] 테스트 케..

오늘은 조합과,, 모든 경우의 수를 탐색하는 알고리즘을 풀었다 날이 갈수록 어려워 지는 걸 느껴서.. 조금 더 일찍일어나 공부를 해보려고 한다 https://devdevleyy.tistory.com/34 [기타] 자바로 조합 구현하기(with 공주 옷입히기) [01. 조합] 조합은 N개의 숫자가 있으면 몇개(R)뽑니? 순서는 상관 없단다! 항상 순열과 조합이 했갈렸는데, 순열 : 순서생각해서 나열, 조합은 조건없이 합침 이런 느낌으로 구별하는 듯 싶다.. 그 devdevleyy.tistory.com 오늘의 TIL은 문제 하나를 좀 깊게깊게 파봤다.. 변형도 해보고.. 열심히 살아야지

[01. 조합] 조합은 N개의 숫자가 있으면 몇개(R)뽑니? 순서는 상관 없단다! 항상 순열과 조합이 했갈렸는데, 순열 : 순서생각해서 나열, 조합은 조건없이 합침 이런 느낌으로 구별하는 듯 싶다.. 그래서 조합은 ? 초등학교때 옷입기 조합을 만들어 본 적이 있을 것이다.. 그거랑 비슷하게 공주님 옷 입히기를 해보겠다 조합은 순서가 상관이 없어서 겹치는걸 다 빼준다는 이야기라고 생각하면 쉽다 신발을 먼저 고르고, 드레스를 먼저 고르냐 -> 드레스를 먼저 고르고 신발을 먼저 고르냐... 같은 이야기지 않습니까 ? 조합은 옷입히기다! 라고 생각합니다. 그래서 코드로는 어떻게 구현하냐.. public class MakeCombination { public static void main(String[] args..

오늘 시험봤는데ㅋㅋㅋㅋ 그 4번 문제 어려웠다 ㅋㅋㅋ 일단 이분탐색 생각하지도 못했고 간선에 무게가 추가되면 어떻게 되는거지 ?.? 물음표만ㅋㅋㅋ 생각하다가 끝났다 ㅋㅋㅋ 지금도 다시 풀다가 머리 식힐 겸 TIL 작성하러 왔다 [02 너비우선탐색 BFS] 같은 깊이의 가까운 정점들을 차례차례 검사하고 그 다음 깊이로 내려가서 탐색한다. "최단거리" 를 사용할 때 구현한다고 합니다아아아아! (항상 그런 것은 아니지만, 지금 내 레벨에서는 이렇게 생각하는 것이 정신건강에 이로울 수 있다..) 구현 로직을 살펴보자... 이렇게 생긴 그래프가 있다. 일단 너비우선 탐색이기 때문에 하나 선택해서 인접한 노드 모~~두 탐색한다고 생각한다. 코드레벨로 구현해 보겠다 public class 그래프그리기 { privat..

오늘은 알고리즘에 기본! 그리고 개인적으로 너무 어려워웠던 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)개념을 익히는 시간이였다. 문제를 푸는 것 보다 개념을 이해하는게 더 중요한 날이라 개인적으로 공부를 좀 더 한 날이기도 하다! [01 깊이우선탐색 DFS] 한 방향으로 최대한 깊이 들어가 탐색한 뒤 인접한 다른 정점을 탐색하는 방식입니다. - stack과 재귀를 활용한 방법이 있는데! 정말정말 기초니까! stack을 활용한 방법을 작성해 보겠습니다. 먼저 이런 그림의 그래프가 있다고 하자... 그러면 stack에 쌓여가는 모습을 그려보도록 할 것이다! 위와 같은 그래프가 있다고 생각해보자 그리고 머리속에 stack을 하나 생각해준다. 이제는 넣고 빼고 하는 과정을 그려 볼 것이다. 코드레벨로 구..

오늘은 기존에 배웠던 개념을 복습했던 날인 것 같다 3번 문제에서 많이 어려움을 느꼈다... 옆으로도 돌려보고 찢어도 보고 했는데, 결국 좌표로 구해서 풀었다. 클래스도 만들어 보긴 했으나 자꾸 실패가 떠서 어려웠다 ========================================================================= 풀었던 문제 [백준 2108번 통계학] https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net package src.co..