본문 바로가기

분류 전체보기

 (328)
[백준] 4991번 : 로봇 청소기 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 해당문제는 다이나믹프로그래밍, 비트마스킹, 완전탐색, 깊이우선탐색, 너비우선탐색을 활용하여 문제를 해결 하였습니다. 너비우선탐색으로는 0과 *, *과* 사이의 거리를 구하였고, dp 테이블에 각각의 사이를 메모리제이션 하였습니다. 완전탐색과 깊이우선탐색, 비트마스킹으로 모든 경우의수를 방문 합니다. from sys import stdin from collections import deque input = ..
[백준] 1194번 : 달이 차오른다, 가자. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 해당 문제는 비트마스킹 및 너비우선 탐색으로 문제를 해결 하였습니다. 깊이, 너비중 너비를 고른 이유는 최소거리를 구해야 하는 문제는 너비우선 탐색이 더 편하기 때문입니다. 키를 얻을때마다 새로운 탐색범위가 생기고 문을 다 열어보면서 1을 찾아가는 식으로 문제를 해결 하였습니다. OR 연산과 AND 연산을 통하여 Key를 등록하는 로직과 해당 Door를 방문하였을때 ..
[백준] 1806번 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N O(N) 의 시간복잡도로 문제를 해결 할 수 있다. p1과 p2로 포인터를 2개를 두고, p1=0 인상태 p2=1인 상태 그리고 초기 ..
Redux(리덕스) 란? Redux란 JavaScript(자바스크립트) 상태관리 라이브러리이다. Redux의 본질은 Node.js 모듈이다. 상태 관리 도구(State Management Tools) 란? React에서 State는 Component 안에서 관리된다. Component 간의 정보공유 자식컴포넌트 간의 다이렉트 데이터 전달은 불가능하다. 자식 컴포넌트 간에 데이터를 주고 받을 때는 상태를 관리하는 부모 컴포넌트를 통해서 주고받는다. 자식이 너무 많아지면 상태관리가 매우 복잡해진다. 상태를 관리하는 상위 컴포넌트에서 계속 내려받아야한다. (Props drilling) 상태 관리의 복잡성을 해결해주는 라이브러리를 활용한다. 1. 전역 상태 저장소 제공 2. Props drilling 이슈 해결 - 예를들어, 라는 컴포..
[백준] 2098번 : 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 처음 해당 문제를 접했을때 완전탐색 + 백트래킹 문제로 보고 문제를 풀어보려고 하였습니다. 팩토리얼 시간복잡도를 가지게 되고, 원하는 시간에 문제를 해결 할 수 없습니다. 해당 문제를 풀면서 이틀 동안 머리가 너무 지끈 했습니다... ㅠ 오랜 시간 분석 끝에 이해하게 되었습니다. 다이나믹 프로그래밍과 비트마스킹으로 문제로 해결 할 수 있습니다. dp 테이블을 ..
데이터베이스의 관계 데이터베이스의 관계(Relationship) 기본 (1:1, 1:N, N:N) 관계 관계명 : 관계의 이름: 엔티티가 관계에 참여하는 형태를 지칭하는 이름으로, 두 개의 엔티티에 대한 것이기 때문에 하나의 관계는 2개의 현재형으로 표현한 관계명을 갖는다. 관계차수 : 두 개의 엔티티 관계에서 참여자수를 표현하는 것을 관계차수라고한다. 일반 적인 관계 차수 표현 방법으로는 1:1, 1:N, N:N이다. 관계 차수에서 가장 중요하게 고려해야할 사항은, 한쪽 엔티티와 관계를 맺은 다른 한쪽 엔티티 쪽이 하나의 객체만을 가지는지, 혹은 여러개의 객체를 가질 수 있는지 파악하는것이 중요하다. 관계 선택 사양(Optionality) - 관계에서 항상 참여해야하는지 (필수관계인지) 아니면 참여할 수도 있는지(선택관계..
[알고리즘 - 이론] 분기한정법 1. 분기한정법(Branch and Bound)란? Branch and Bound(분기한정법)이란 BackTracking(백트래킹)을 개선한 알고리즘이다. 분기 한정법 또한 state space tree를 사용한다. 하지만 분기한정법과 백트래킹의 차이점은 - 트리를 여행하는 방법에 제한을 두지 않는다. - 오로지 최적화 문제에만 사용한다. 백트래킹은 깊이우선탐색을 사용하여 상태공간트리를 탐색하였지만 분기한정법은 너비우선탐색을 사용하고, 또 Best-First-Search를 사용하여 더 효율적이게 트리를 탐색한다. 분기 한정법은 특정 마디가 유망한지 결정하기 위해서 그 마디에서 수, 한계값(Bound)를 계산한다. 그리고 최적의 한계값을 가진 노드의 자식을 방문한다. 이 방법은 DFS보다 빠르고, 자주 D..
리액트 입문자료 리액트 자바스크립트에 HTML을 포함하는 JSX(javascript XML)이라는 문법사용 가상 돔(Virtual DOM)이라는 개념을 사용하여 웹 어플레케이션의 퍼포먼스를 최적화함. 단방향 데이터 바인딩(One-way Data Binding) 사용 싱글 페이지 애플리케이션에서 UI를 만들기 떄문에 페이지 전환 기능을 사용하려면 react-router와 같은 추가 라이브러리를 사용해야함. 클라이언트 사이드 랜더링(CSR) 가상 돔(Virtual DOM) 리액트에서는 리플로우와 리액트가 자주 수행되는 문제를 해결하기 위해 화면에 표시되는 DOM과 동일한 DOM을 메모리상에 만들고 DOM 조작이 발생하면 메모리상에 생성된 가삼 돔에 모든 연산을 수행한 후, 실제 DOM을 갱신하여 리플로우/리패인트 연산을 최..

티스토리툴바