기타
-
[SW 정글 27일차] 분할정복과 DP는 다른가?기타/SW 사관학교 정글 2021. 8. 29. 02:23
목요일부터 오늘까지 Dynamic Programming을 공부하고 문제를 풀면서 오늘에서야 든 생각은 아니지만 분할정복과 접근법이 굉장히 비슷하다는 생각이 들었다. 그래서 이 둘의 차이점을 알아보고 정리해보려고 한다. 1. 분할정복과 DP의 개념 - 분할 정복은? 분할 정복에 대해서는 아래 블로그 글에 정리한 바 있다. https://straw961030.tistory.com/193 [SW 정글 14일차] 분할 정복 1. 분할 정복 분할 정복은 주어진 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고 부분 문제를 재귀적으로 풀고 찾은 해를 결합하여 원래 문제의 해를 만들어 내는 방 straw961030.tistory.com 분할 정복은 주어진 문제를 원래 문제와 유사하지만 크기가 ..
-
[SW 정글 26일차] Knapsack Problem 이해하기기타/SW 사관학교 정글 2021. 8. 28. 02:14
오늘 푼 문제 중에서 Dynamic Programming을 사용하여 푸는 Knapsack Problem을 만났다. 오늘 공부시간을 DP문제풀이에 쏟은 만큼 Knapsack Problem의 문제 접근법에 대해 정리해보려고 한다. 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. 문제가 뭔데? 최대 용량이 정해진 배낭에 무게와 값어치가 다른 물건들을 담으려고 하는데 담긴 물건들의..
-
[SW 정글 25일차] LCS는 왜 그렇게 될까?기타/SW 사관학교 정글 2021. 8. 27. 01:35
오늘은 다이나믹 프로그래밍, 그리디 알고리즘을 공부하는 주차로 다이나믹 프로그래밍 문제 중에 LCS(Longest Common Subsequence, 최장 공통 부분 수열)라는 문제가 있었다. https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 푼 경험이 있어 접근법을 알고 있어 나는 풀기는 했지만 다른 동료가 와서 왜 이렇게 되는지에 대한 질문을 던졌고 나는 명확한 답변을 해주지 못했다. 질문은..
-
SW 정글 3주차 회고기타/SW 사관학교 정글 2021. 8. 26. 20:08
[3주차 회고] 2021년 08월 26일 목요일, 3주차가 마무리 되는 날이고 3주차는 전체적으로 어땠는지 이 글을 쓰면서 돌아보려고 한다. 3주차는 전체적으로 여유롭고 개인적인 시간을 가질 수 있던 주였다. BFS, DFS, 위상 정렬이라는 알고리즘이 쉽다는 것이 아니라 어떻게 보면 하나의 범주이고 문제 접근방식이 비슷하기에 여유롭게 느껴진 것같다. 하지만, 3주 만에 여유라는 것을 느낀 나에게는 꿀로 위장한 독이였다고도 생각이 든다. 너무 마음이 편안한 나머지, 해이해졌다는 느낌을 받았고 그 느낌이 든 순간 다시 정신을 차리고 몰입에 시작했다. 하루를 알고리즘에 쏟아부으니 잘 집중도 안되고 특히 아침에는 너무 졸려서 새로운 것(Spring framework)를 공부해보니 재미있고 집중도 잘되고 오랜만..
-
[SW 정글 24일차] 플로이드 와샬 알고리즘이 궁금하다기타/SW 사관학교 정글 2021. 8. 26. 01:37
오늘은 DFS, BFS, 위상정렬을 공부하는 마지막 날로 복습을 하고 다른 동료들의 블로그를 보며 어떻게 문제에 접근했는지 살펴보았다. 그 중에서 알고리즘 공부를 꽤 하고 왔던 동료의 블로그를 보게 되었고 새롭고 신기한 알고리즘을 알게 되었다. https://kspsd.tistory.com/15 백준 2617 구슬 찾기(python) 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중. kspsd.tistory.com 문제를 보고 플로이드 와샬 알고리즘이 떠올라서 적용을 한 것이다. 개인적인 시간이 부족했다면..
-
[파이썬 코테 6기] 마지막 세션 최종 후기기타/파이썬 코테 스터디 6기 2021. 8. 25. 22:54
이 글은 프로그래머스에서 진행하는 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 6기를 참여하면서 일주일에 한 번(매주 수요일) 진행되는 세션에서 배운 내용을 정리하는 글이다. 오늘은 3주차 세션(2021년 08월 11일 진행)에서 배운 내용을 정리해보려고 한다. https://programmers.co.kr/learn/courses/12441 [스터디/6기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 🚀 아쉽지만 6기는 마감되었어요. 12월 시작 예정인 7기 오픈 알림을 신청하고, 최저가에 수강하세요! 최저가 알림 받기 코딩테스트와 실무 역량 모두 잡는 스터디: Python반 코딩테스트 운영진과 programmers.co.kr 오늘은 지난 주차와 다르게 특정한..
-
[SW 정글 23일차] 트라이 (Trie) 알아보기기타/SW 사관학교 정글 2021. 8. 25. 02:22
오늘은 아래의 문제를 풀면서 새롭게 안 트라이(Trie)에 대해 정리해보려고 한다. 문제를 통해 알게 되어 내가 공부한 것을 정리하는 것도 있지만 내가 평소에 검색기능을 이용하면서 자동완성을 많이 경험하곤 했는데 이 자동완성에 쓰인 알고리즘을 알았다는 것이 신기해서 정리하는 것도 있다. 1. 트라이(Trie)란? 트라이(trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 여기서, 트리 형태에 대해서는 아래의 글에 정리했으니 혹시 모르겠다면 참고하면 좋을 것같다. https://straw961030.tistory.com/192 [SW 정글 13일차] 트리 구조와 이진 트리 1. 트리 구조 트리 구조는 데이터 사이의 계층 관계를 표현하는 자료 구조로 노드(node)와 가지(ed..
-
[SW 정글 22일차] 내가 생각하는 추상화는?기타/SW 사관학교 정글 2021. 8. 24. 02:07
오늘은 컴퓨터 시스템책을 읽으면서 가장 많이 나오지만 개념을 잘 알고 있지 못하는 추상화에 대해 공부를 했다. 추상화라는 단어는 그냥 어떠한 것을 구체적이고 명확하게 나타내지 않고 뭔가 흐릿하게 혹은 간단하게 생각만을 옮겨놓은 것이라고 생각한다. 하지만, 이 추상화라는 단어가 컴퓨터 구조에서는 어떻게 적용되어서 쓰이고 왜 쓰이는지가 궁금했다. 에는 추상화라는 단어가 아래와 같이 쓰였다. 운영체제는 세 가지 근본적인 추상화를 제공한다. (1) 파일은 입출력장치의 추상화다. (2) 가상메모리는 메인 메모리와 디스크의 추상화다. (3) 프로세스는 프로세서, 메인 메모리, 입출력 장치의 추상화다. 대충 문맥 상 A가 B를 추상화했구나라고 이해는 할 수 있지만 조금 더 명확하게 개념을 잡고자한다. 1. 추상화란?..