전체 글 썸네일형 리스트형 Dynamic Programming 4: 배낭 문제 (백준 7579, 2629번 파이썬) Dynamic programming 개념을 설명할 때 피보나치 수열 말고도 가장 흔하게 언급되는 예시가 배낭 문제(knapsack problem)이다. 어느 정도 난이도가 있는 배낭 문제는 DP로 푸는 게 대부분이다. 배낭 문제를 처음 접해본 사람은 올바른 풀이를 떠올리기 정말 어렵다. 그러나 배낭 문제는 결국 사소한 문제 설정에서 차이가 있을 뿐 비슷한 유형의 문제를 풀다보면 동일한 패턴을 발견하게 된다. 결국 배낭 문제는 풀이 방식이 비슷하기 때문에 아예 풀이를 외울 정도까지 익숙해지는 게 좋다고 생각한다. 배낭 문제에 속하는 예시 몇 가지를 아래에서 살펴보자. 백준 7579번: 앱 문제 설정은 앞서 살펴본 11066번(파일 합치기)와 11049번(행렬 곱셈 순서)와는 다르다. 이전 문제는 어떤 연속.. 2023. 3. 29. 15:35 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 3: 재귀(top-down)를 이용한 풀이 (백준 11049번 파이썬) 2번째 글에 이어서 재귀를 이용한 top-down 방식의 풀이를 소개하려고 한다. 백준 11049번: 행렬 곱셈 순서 언뜻 다른 것처럼 보이지만 백준 11066번(파일 합치기) 문제와 매우 비슷하다. 두 문제는 아래와 같은 공통점이 있다. 어떤 연속된 값들을 하나씩 더하거나 곱해간다. 두 개를 합쳐 하나로 만드는 과정을 반복한다. 최종 행렬 곱셈 결과를 이미 구했다고 가정했을 때 그 값은 결국 어떤 두 행렬을 곱한 결과고, 각 두 행렬을 더 작은 문제(행렬의 곱셈 결과)로 쪼개나간다는 컨셉은 11066번과 판박이다. 다만 11066번과 다른 점은 단순 합을 구하는 게 아니라 행렬의 곱을 구한다는 점이다. 여기서 dp 배열 말고도 메모이제이션을 통해 재활용해야 하는 값이 생긴다. 아래 코드를 살펴보자. 재.. 2023. 3. 29. 14:15 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 2: 재귀(top-down) vs. DP(bottom-up) (백준 11066, 1520, 1937번 파이썬) Dynamic Programming(DP) 개념을 처음 소개할 때 빠지지 않고 등장하는 게 피보나치 수열이다. 설명 글을 요악하면 다음과 같다. 1) 피보나치 수열을 재귀함수를 이용해 구한다. 2) 재귀함수로 구할 때 중복된 계산이 발생한다. 어차피 같은 답을 내놓는 연산을 여러 번 반복하니 불필요하고 비효율적이다. 3) 불필요한 연산을 방지하기 위해 memoization, 즉 DP 개념을 도입한다. 여기에 핵심이 있다. 우리는 같은 DP 문제에 대해 재귀로 풀 수도 있고, DP로도 풀 수 있다. 이유는 애초에 DP 문제가 다음 성질을 지니기 때문이다. 1) 큰 문제(마지막 항, f(n), 구하고자 하는 답, 현재 상태)를 작은 문제(초기값, 이전 상태, 직전 단계)에 의존하는 관계식으로 표현할 수 있다.. 2023. 3. 28. 15:42 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 1: 기초 풀이 접근 (백준 10942, 17070번) Dynamic Programming 문제는 결국 점화식을 찾는 게 관건이다. 즉 현재 상태가 이전 상태에 어떻게 의존하는지, 어떤 관계 속에 놓여있는지 파악해야 한다. DP 문제 풀이 접근 방식은 다음과 같다. 1) 머리만 굴리지 말고 직접 손으로 써본다. 어차피 DP는 점화식을 찾는 문제고, 점화식은 곧 이전 항과 현재 항 사이 숨은 패턴을 찾는 일이다. 다행히 직접 반복해보면서 써보면 패턴을 발견하게 되는 경우가 대부분이다. 테스트 케이스나 (테스트 케이스가 적절하지 않다면) 직접 예시를 고안해서 4~5개 항 정도 추론해볼 것. 2) 문제 조건을 결정 짓는 핵심 정보는 무엇인가? 3) 현재 상태가 이전 상태에 어떻게 의존하는가? 4) DP 배열의 정보를 명확히 설정한다. 1차원인가? 2차원 또는 그 .. 2023. 3. 28. 13:43 ㆍ 알고리즘과 자료구조/Dynamic Programming 코딩 테스트를 위한 VSCode 자동완성, 추천 설정 해제하기 평소 VSCode intellisense의 자동완성 기능은 익숙해지면 매우 편리합니다. 그렇지만 원하지 않을 때도 있습니다. 특히 코딩 테스트를 앞둔 분들에게는 intellisense를 꺼놓고 연습하는 걸 추천합니다 실제 코딩 테스트를 치르는 환경에서는 모듈 이름이나 변수 맞춤법을 친절하게 알려주지 않습니다. 근데 평소 IDE의 편리한 기능에 너무 의존한 나머지 나중 가서는 아주 당혹스러운 상황이 벌어지는데... 기본적인 모듈이나 라이브러리 이름조차도 까먹으면 식은땀이 납니다. 변수 맞춤법은 기본이고 이중 배열을 써야 하는데 괄호(])를 하나 안 씌웠다든가, 대입(=)해야 하는데 등호(==)를 쓴다든가 하는 별의별 실수가 튀어나오는 경험을 본인이 직접 모두 겪어봤습니다. IDE의 편리한 기능은 어떻게 보.. 2023. 3. 2. 14:49 ㆍ 카테고리 없음 VS Code에서 원격 서버 접속 오류 Case 1: 패스워드 만료 문제 발생 배경 아무런 설정(id_rsa, 서버 비밀번호, 서버 인스턴스 등) 변경 X 서버 인스턴스는 잘 켜져있는 걸 확인 일주일 정도 접속하지 않다가, 다시 VS Code 접속하려고 했을 때 "Could not establish connection to "my_server". 와 같은 메시지가 뜬다. VS Code는 원격 서버 접속이 되지 않는 이유(에러 메시지)를 설명해주지 않는다. 문제 해결 방법 터미널로 ssh 접속 명령어 형식은 아래와 같다. ssh my_server_id@my_server_public_IP_address 그 결과 패스워드 만료가 원인인 것으로 확인. 기존 패스워드를 입력해야 하나, 올바르지 않은 패스워드를 입력하면 아래 에러 메시지(Authentication token man.. 2022. 11. 25. 10:20 ㆍ 2023년 이전/리눅스 ln 명령어로 심볼릭 링크 symbolic link 생성하기 Hard Link vs. Symbolic Link(Soft Link) Hard link는 말 그대로 실제 존재하는 파일의 경로. In computing, a symbolic link (also symlink or soft link) is a file whose purpose is to point to a file or directory (called the "target") by specifying a path thereto. https://en.wikipedia.org/wiki/Symbolic_link Symbolic link - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Any file that c.. 2022. 10. 19. 16:00 ㆍ 2023년 이전/리눅스 ForkLift로 로컬-원격 서버(또는 원격 서버-서버) 간 파일 쉽게 전송하기 1. ForkLift > Go > Connect 클릭 2. Protocol: SFTP Server: 서버의 public IP 주소 Username: 서버의 내 계정 이름(서버에 접속해서 whoami 치면 확인 가능) Password: 패스워드 따로 등록하지 않고, 대신 SSH key가 있다면 내 로컬에서 SSH private key(~/.ssh/id_rsa) 찾아 클릭 Port: 서버를 포워딩한 포트 번호 이렇게 입력하면 Forklift로 파일 전송할 준비 끝! 2022. 10. 13. 15:01 ㆍ 2023년 이전/리눅스 이전 1 ··· 4 5 6 7 8 9 다음 목록 더보기
