목록분류 전체보기 (259)
차근차근
0. 제목 백준 1932 정수 삼각형 BOJ 1932 정수 삼각형 C++ 1932 정수 삼각형 1. 문제 https://www.acmicpc.net/problem/1932 2. 풀이 합이 최대가 되는 경로에 있는 수의 합을 출력하는 것이 문제이다. 2차원 배열 arr, dp를 할당하고 arr는 각 위치의 값이 담기고 dp는 그 위치로 갔을 때의 합이 담긴다. 그런데 합이 최대가 되어야 하므로 전 단계에서 즉, 윗 줄에서 왼쪽과 오른쪽중 큰 것을 선택해야 한다. 따라서 점화식은 다음과 같다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j] 그런데 좌표를 arr[1][1] 부터 시작하도록 설정하였으며 i-1 이 0이 나오는 dp[i][0]들은 0으로 초기화 시켜..
0. Basic React Native Concepts RN의 가장 기본적인 컨셉은 더이상 div, html이 없다는 것이다. 이것은 return 할 수 있는 컴포넌트가 정해져 있다는 뜻이다. 아와 같은 컴포넌트는 RN documentation에서 확인할 수 있다. view 컴포넌트를 이용하면 ios/android환경에 따라 objective-c 혹은 java로 변한다. RN은 굉장히 엄격하다. CSS와 비슷한 Style이라는 것을 사용한다. 1. React Native Layouts with Flexbox flexbox로 디자인을 짤 수 있는 앱은 RN이 유일하다. 기존 css와 백프로 동일하진않지만 비슷하다. 디폴트 설정으로 RN은 flex direction이 column이다. html, css에서는..
0. 제목 백준 1735 분수 합 BOJ 1735 분수 합 C++ 1735 분수 합 1. 문제 https://www.acmicpc.net/problem/1735 2. 풀이 유클리드 호제법을 사용하였다. 유클리드 호제법은 두 정수의 최대 공약수를 구하는 방법이다. 먼저 최대 공약수가 아닌 분모의 곱을 사용하여 합을 구한다. 그 후 분모와 분자의 최대공약수를 유클리드 호제법을 사용하여 구하고 분자와 분모를 최대공약수로 나누어준다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include using namespace std; int gcd(int x, int y){ int z = 1; while(y !..
0. 제목 백준 7562 나이트의 이동 BOJ 7562 나이트의 이동 C++ 7562 나이트의 이동 1. 문제 https://www.acmicpc.net/problem/7562 2. 풀이 dfs가 아닌 bfs를 이용한다. bfs를 활용했을 때 목적지에 도착했을 당시 최소 이동 횟수이기 때문이다. dfs는 목적지에 도착했을 때 최소 이동 횟수가 아니기 때문이다. 최소 이동 횟수를 구할 때는 bfs로 구해야 할 것같다.(내 생각) 배열 arr은 출발지로부터 해당 좌표(i, j)까지의 최소 이동 횟수를 담아 놓은 것이다. bfs방식으로 큐를 이용하여 출발 좌표부터 탐색을 시작하고 출발지 좌표가 나오면 그 때 arr배열의 값을 출력해주고 탈출하면 된다. 테스트케이스도 입력을 받으니 테스트케이스를 하나 실행할때 ..
0. 제목 백준 2252 줄 세우기 BOJ 2252 줄 세우기 C++ 2252 줄 세우기 1. 문제 https://www.acmicpc.net/problem/2252 2. 풀이 Topological Sort(위상 정렬)을 사용하는 문제이다. 위상 정렬은 indegree 즉, 자신에게 들어오는 노드 수를 계산하고 indegree가 0이 되면 먼저 정렬해 주는 것이다. 위상 정렬의 특징 중 하나는 사이클이 생기면 안된다는 것이다. indegree가 모두 0보다 크면 사이클이 생긴다는 의미이다. 따라서 위상 정렬은 indegree가 0인 것이 하나 이상 존재할 때 가능하다. 이 문제에서 1 3 이 주어졌을 때 1 다음에 3이 줄을 서야 한다. 방향을 나타내면 1 -> 3 으로 나타낼 수 있고 이 상황에서 3의..
0. React Native React Native는 네이티브 웹 어플리케이션을 빌드하게 도와주는 UI 라이브러리이다. 줄여서 RN이라고 부르겠다. RN은 html, css 어플리케이션을 생성하지 않는다. 마지막 컴파일링 할 때, 각각 iOS(objective-C) / android(java) 네이티브 코드로 실행이 된다. RN이 구동되는 방법은 JSX, 자바스크립트로 작성을 하고, 그 뒤에서 자바스크립트가 objective-c 혹은 java로 변환되는 것이다. 페이스북이 개발한 이 기술에 의하여 js - objective-c , js - java 의 다리(bridge)가 연결되는 것이다. react js 코드와 비슷하다. 차이점은 다른 패키지를 쓰는데, 그 패키지 이름이 react native이다. 웹..
0. 제목 백준 9935 문자열 폭발 BOJ 9935 문자열 폭발 C++ 9935 문자열 폭발 1. 문제 https://www.acmicpc.net/problem/9935 2. 풀이 입력 문자열의 길이가 1000000까지 될 수 있기 때문에 O(N)으로 탐색을 해야 시간 내에 통과할 수 있다. 처음부터 탐색하는 것을 반복하면 시간이 오래 걸리기 때문에 처음부터 비교해가면서 즉각 제거 하는 방식으로 풀어야 한다. 예를 들어보겠다. 문자열 abcde가 주어지고 폭발 문자열로 cd가 주어졌다고 하자. 문자열이 폭발 문자열의 마지막 문자인 d와 같을 때 역으로 비교해주어야 한다. result라는 배열은 폭발하지 않는 문자열을 담는 배열이다. 문자열에서 d가 나오는 순간 문자열의 d 전에 나오는 문자가 c인지 확..
0. 제목 백준 1717 집합의 표현 BOJ 1717 집합의 표현 C++ 1717 집합의 표현 1. 문제 https://www.acmicpc.net/problem/1717 2. 풀이 Union-Find방식을 사용하는 문제이다. Find를 통해 root를 찾아주고 Union을 통해 합쳐준다. union은 merge로 구현하였다. 0과 1이 입력되는 케이스를 구분하여 적절히 find, union을 수행해주면 된다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include using namespace std; int par..
0. 제목 백준 1325 효율적인 해킹 BOJ 1325 효율적인 해킹 C++ 1325 효율적인 해킹 1. 문제 https://www.acmicpc.net/problem/1325 2. 풀이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 것이 문제이다. dfs를 사용하여 연결되어 있는 컴퓨터의 수를 센다. 각 컴퓨터를 시작점으로 dfs를 시행하여 컴퓨터 수를 세고 그것을 depth배열에 담는다. depth배열의 원소 중 최댓값을 구한다. depth배열의 원소 값 중 최댓값과 같은 값을 가지고 있는 index들을 순서대로 출력한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ..
0. 제목 백준 2606 바이러스 BOJ 2606 바이러스 C++ 2606 바이러스 1. 문제 https://www.acmicpc.net/problem/2606 2. 풀이 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. dfs를 활용하여 연결되어 있는 컴퓨터들의 개수를 구한다. dfs내부에서 감염 컴퓨터 수를 세는 cnt 변수를 사용한다. 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터를 구하는 문제이기 때문에 dfs(1)을 수행하여 정답을 구할 수 있다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3..