전체 글 검색 결과
199 개의 검색 결과가 있습니다.
ProblemSolving

[BOJ] 1074_Z

Z 문제 링크: https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 문제를 보면 2^N의 2차원 배열이라는 낚시글로 시작된다. 시간제한이 0.5초, 메모리 제한이 512MB에서 2차원 배열로 해결할 수 없다. 먼저 1행을 기준으로 열에 대한 규칙을 찾아보자. 0열 1열 2열 3열 4열 5열 6열 7열 8열 9열 10열 11열 0 1 4 5 16 17 20 21 64 65 68 69 이렇게 나열하고 보니 0열을 기준으로 2^N과 관련이 있어 ..

2021. 2. 2. 17:10
WebStudy/Spring

IntelliJ Community Spring 설치

IntelliJ Spring 설치 참고 링크1: Spring Boot 참고 링크2: Spring MVC 먼저 들어가기 앞서 IntelliJ는 community edition을 이용중이다. community edition은 spring 프로젝트가 생성이 안되는 문제가 되었다. 따라서, 구글링을 통한 일반적인 방법으로는 생성이 안되었다. 위에 올린 링크에서 community edition을 통한 Spring Boot와 Spring MVC 환경설정의 도움을 주었다. 나는 이전 톰캣을 사용하였기에 톰캣에 대한 내용은 건너뛰고 바로 war파일 업로드 부터 진행하였고 해당 내용은 내일 다시 정리 예정이다.

2021. 2. 1. 23:51
ProblemSolving

[BOJ] 1309_동물원

동물원 문제 링크: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 분류를 보니 Dynamic Programming 문제이다. 규칙을 찾기 위해 1부터 4까지 노가다를 해보자. a1 = 3 a2 = 7 a3 = 17 a4 = 41 ... 여기까지 수행을 한 후 규칙을 추측해보자. an = an-1 * 2 + an-2 이를 적용해서 코드를 정리해보자. 우연히 바로 정답이 떠서 당황했다... 정답 코드 #include using namespace std; #define MOD 9901 int dp[100000] = { 0, }; int main() { int n; cin >> n;..

2021. 2. 1. 03:39
ProblemSolving

[BOJ] 1564_팩토리얼5

팩토리얼5 문제 링크: https://www.acmicpc.net/problem/1564 1564번: 팩토리얼5 첫째 줄에 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. 또, 9보다 크거나 같다. www.acmicpc.net 입력받은 n의 팩토리얼 과정은 동일하다. 그리고 뒤에 나오는 0은 읽지 않을것이므로 없애준다. 그 후 적당히 큰 수를 잘라서 저장한다. 마지막 출력할 때 5자리로 짤라서 출력을 한다. 정수 출력에서 앞자리 0은 출력을 안하므로 printf("%05lld\n", fiveDigit);로 5자리를 채운다. 정답 코드 #include using namespace std; int main() { int n; scanf_s("%d", &n); unsigned long long ..

2021. 1. 31. 22:41
ProblemSolving

[BOJ] 1927_최소 힙

최소 힙 문제 링크: https://www.acmicpc.net/problem/1927 간단한 자료구조 priority_queue를 사용하는 방법에 대한 문제이다. 다만 c++로 그냥 사용하면 시간초과가 나오는게 이 문제의 핵심이다. c로 작성해서 제출하면 아마 정답이라고 나올것이다. 즉, 알고리즘 적으로 문제가 있는 것이 아니라, c++의 표준 입출력의 문제가 있는 것이다. 해당 문제의 질문들을 둘러보았다. https://www.acmicpc.net/board/view/33074 여기에 따르면, c++은 기본적으로 입출력 작업을 할 때마다 c의 표준 입출력과 동기화되어 있도록 설정이 되어있다고 한다. 또한, 마지막으로 작업한 I/O 스트림이 아닌 다른 곳에서 입출력 작업을 하려고 할 때 입출력 버퍼를 ..

2021. 1. 29. 18:01
ProblemSolving

[BOJ] 1106_호텔

호텔 문제 링크: https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net i를 i개의 손님 유치 수라 하자. dp[i]는 손님 유치를 하는데 드는 최소비용이라고 정의할 수 있다. 현재 상태의 손님 유치의 수를 c라 하면, 다음의 단계에서 들었던 비용과 현재의 비용의 합이 c를 유치하는데 드는 비용이 된다. 그 중 가장 최소인 값이 dp[i]의 값이 될 것이다. Dynamic Programming의 방법 중 Top-Down 방식을 채택하여 다음과 같..

2021. 1. 28. 19:32
기타

Greedy Algorithm

Greedy Algorithm 동빈나님의 블로그와 위키피디아를 참고해서 정리했음을 밝힙니다. 링크: https://blog.naver.com/ndb796/221242106787 그리디 알고리즘: 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 특징 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 최적의 해에 근사한 값을 빠르게 구할 수 있다. '특정한 상황'에 있어서 최적의 해를 보장할 수도 있다. 언제 쓰는가? 탐욕스러운 선택조건, 최적 부분 구조 조건 두 가지 조건이 만족할 경우 탐욕스러운 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것 최적 부분 구조 조건: 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해이다. 매트로이드: 일차 독립의 성질을 공리화하여 얻은 주합론적 ..

2021. 1. 27. 21:59
기타

Dynamic Programming

Dynamic Programming 동적계획법이란: 큰 문제를 작은 문제로 나누어 푸는 방법 언제 쓰는가? 부분 문제 반복 및 최적 부분 구조를 가지고 있는 알고리즘에 사용 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용 왜 쓰는가? 알고리즘을 일반적인 방법에 비해 더 적은 시간 내에 풀기 위함이다. 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토, 그 중 최적의 풀이법을 찾아냄에 있어 효율적 어떻게 쓰는가? 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 하위 문제로 나누어 푼다. 여러 하위 문제를 푼 후, 그 해결책을 저장한다. 이 후 같은 하위 문제가 나왔을 경우 이전의 해결책으로 정리한다. 예를 들어 피보나치 수열을 보자. 일반적인 피보나치 수열의 알고리즘은 다음과 같다. funct..

2021. 1. 27. 20:08
ProblemSolving

[BOJ] 1149_RGB거리

RGB거리 문제 링크: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 Dynamic Programming 문제이다. 하나의 선택을 했을 경우 다음의 선택에서는 두 개의 선택지로 나뉘어진다. 우리는 가장 최솟값을 구해야한다. 그 두 개의 선택지 중 더 작은 값을 고르면 된다. 하지만 반대로 내가 하나의 선택을 했다면, 이전에 걸어왔던 선택지에서 현재 내가 선택한 색상을 제외한 나머지를 선택할 수 있다. 만일 현재..

2021. 1. 27. 00:52
C++/뇌를 자극하는 C++ STL

Chapter6 시퀀스 컨테이너

vector 컨테이너 주요 인터페이스 및 특징 vector는 시퀀스 컨테이너이다. 원소 추가 및 제거의 메소드 제공: push_back(), pop_back() 첫 원소와 마지막 원소를 참조하는 메소드 제공: front(), back() 지정한 위치에 원소를 삽입하는 메소드 제공: insert() vector는 앞쪽이 막혀 있는 형태이다. 앞쪽에는 원소를 추가/제거가 불가 뒤쪽에만 추가 및 제거 기능 수행 사용예제 #include #include using namespace std; int main() { vector v; for (int i = 1; i

2021. 1. 26. 23:48