본문 바로가기

전체 글123

49. SW_Test 연습 백준 어른상어 www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 청소년상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다. N×N 크기의 격자 중 M.. 2021. 2. 28.
React 개념 : map 이전의 코드에서 Test 컴포넌트 안에 Game 컴포넌트를 3번 넣어주었다. 만약 웹에서 표현해야하는 Game이 100가지가 넘어간다면 어떻게 될까? 아마도 코드는 import React from 'react'; function Game(props){ return ( I'M {props.name} ); } function Test() { return ( Ha Ha Test!!! . . . X100 . ); } export default Test; 이렇게 100줄을 입력하는 비효율적인 코드가 될것이다. 이를 줄여주기 위해 서용하는 함수는 map 함수이다. 우선 map 함수를 이용하기 위해 GameList 배열을 선언한다. GameList 배열은 서버에서 데이터를 전달하였다는 상황을 가정하기위해 추가하는것이.. 2021. 2. 27.
React 개념 : props 리액트에서 props 는 쉽게 말해 C++ , JAVA 등 다른 컴퓨터 언어에서 쓰이는 매개변수와 비슷하다고 볼수있다. 다시말해 props 는 컴포넌트 간의 전달되는 데이터를 뜻한다. 놀랍게도, 리액트는 컴포넌트 안에 컴포넌트를 정의 할수있다. 다음과 같이 Test.js 파일을 수정하였다. import React from 'react'; function Game(){ return ( I'M LOL ); } function Test() { return ( Ha Ha Test!!! ); } export default Test; 이전에 말했듯 리액트는 " " 과 같은 표시로 컴포넌트를 인식한다고 하였다. 위의 코드를 보면 Test 컴포넌트 안에 이라는 코드를 통하여 컴포넌트안에 컴포넌트를 넣었다. 또한 '' .. 2021. 2. 27.
React 개념 : 컴포넌트 (Component) 컴포넌트란 (Component) ? - 리액트에서 기능을 나눌때의 최소 단위이다. - 리액트는 컴포넌트와 함께 동작하고, 리액트 앱은 모두 컴포넌트로 구성된다. 컴포넌트는 JSX 라는 문법을 사용해서 만들어지는데 이는 HTML + javascript 언어를 조합한 언어이다. 리액트는 과 같은 표시를 컴포넌트로 인식하고, 그 컴포넌트가 반환하는 값을 화면에 그려준다. 다음은 index.js 에서 APP 컴포넌트를 사용하는 코드이다. import React from 'react'; import ReactDOM from 'react-dom'; import App from './App'; ReactDOM.render(,document.getElementById('root')); 여기서 추가적으로 컴포넌트를 추가.. 2021. 2. 27.
위상정렬 위상정렬은 정렬 알고리즘의 종류이다. 위상정렬이란 '방향그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열' 하는 것이다. 쉽게 비유를 하자면 '대학교 커리큘럼'을 예로들수있다. 예를들어 모 대학교의 컴공과는 인공지능과목을 자료구조를 선수강한 뒤에 신청할수있도록 하였다. 이처럼 그래프상에서 선후관계가있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 순서를 계산할수있다. 위상정렬의 알고리즘 순서는 다음과 같다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌때 까지 다음의 과정을 반복한다. 1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 여기서 진입 차수란, 특정노드로 들어오는 간선의 개수와 같다. #.. 2021. 2. 26.
신장트리, 크루스칼 알고리즘 신장트리는 그래프에서 자주보이는 유형이다. 신장트리란, 하나의 그래프가있을때 모든 노드를 포함하면서 사이클을 발생 시키지 않는 부분그래프를 뜻한다. 이처럼 신장트리에서 최소 비용으로 만들어진 신장트리를 '최소비용 신장트리' 리고하는데 이 신장트리를 구하는 대표적인 방법은 크루스칼 알고리즘이 있다. 크루스칼 알고리즘의 동작순서는 다음과 같다. 1. 간선데이터의 비용을 크기에 따라 오름 차순 정렬한다. 2. 간선을 하나씩확인하며 사이클을 발생 시키는지 확인한다. 1. 사이클이 발생하지 않는다면 최소비용 신장트리에 포함시킨다. 2. 사이클이 발생하는 경우 포함하지 않는다. 3. 모든 간선에 대하여 2 번의 과정을 반복한다. 다음은 크루스칼 알고리즘의 코드이다. #include #include #include .. 2021. 2. 26.
플로이드 워셜 다익스타 알고리즘은 한지점에서 다른 지점까지의 최단경로를 구해야하는 경우에 사용해야 한다면, 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두구해야하는 경우에 사용할수있는 알고리즘이다. 플로이드 워셜 구현 알고리즘은 다음과 같다. #include #include #include #define INF 1e9 // 무한을 의미하는 값으로 10억을 설정 using namespace std; int graph[101][101]; int n,m; void init(){ // 모든 지점간의 거리값을 INF 로 초기화 for (int i = 0; i < 101; i++) { fill(graph[i], graph[i] + 101, INF); } // 자기자신을 갈수없으므로 0 으로 초기화 .. 2021. 2. 25.
다익스트라 다익스트라 알고리즘은 그래프에서 여러개의 노드가 있을때, 특정한 노드에서 출발하여 다른 노드로가는 최단 경로를 구하는 알고리즘이다. 다익스트라 동작 방식은 다음과 같다. 1. 출발노드를 설정한다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않는 노드중에서 최단거리가 가장 짧은 노드를 선택한다. 4. 해당노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 갱신 5. 위 과정에서 3 4 반복. 다익스트라를 구현하는 방법은 두가지가있는데, 하나는 1차원 리스트를 순차탐색하면서 구현하는 방법이고 두번째는 힙(우선순위큐)를 이용하여 구현하는 방법이다. 첫번째 방법의경우 O(V^2) 의 시간복잡도를 가지지만 두번째는 O(ElogV) 의 시간복잡도를 가진다. 아래는 우선순위큐를 이용하여 다익스트라를 구현한.. 2021. 2. 25.
이진탐색, upper_bound , lower_bound 이진탐색이란 배열의 내부가 정렬되어있어야 사용할수있는 탐색이다. 이진탐색은 시작점, 끝점, 중간점을 반복 이용하여 중간점과 찾고자하는값을 비교하며 데이터를 찾는다. 또한 탐색을 진행할때마다 평균적으로 확인하는 원소가 절반으로 줄어든다. 즉, 빅오 표기법에 따라 O ( logn) 의 복잡도를 가진다. 간단한 이진탐색을 구현하는 방법은 재귀,반복을 이용하는 두가지 방법이 있는데 반복을 이용하는 코드는 다음과 같다. #include #include #include using namespace std; vector list; int binarySearch(vector &list , int left, int right ,int target){ while (left> N >> target; for(int i = 0.. 2021. 2. 25.

티스토리툴바