본문 바로가기
728x90
SMALL

분류 전체보기

 (459)
백준 2302번 [극장 좌석](C++) -yes6686- 티스토리 백준 문제 풀이: 2302 [극장 좌석]문제 링크: https://www.acmicpc.net/problem/2302문제 설명:극장 좌석이 한 줄로 배치되어 있고, 특정 좌석은 VIP로 고정되어 있어 자리를 바꿀 수 없습니다. 나머지 좌석은 자유롭게 배치할 수 있으며, 극장 좌석의 배치 방법의 가짓수를 계산하는 문제입니다.VIP 좌석은 고정되어 이동할 수 없습니다.인접한 두 좌석을 서로 바꾸는 방식으로 자유 좌석의 배치를 다양하게 구성할 수 있습니다.문제 해결 코드#include using namespace std;int dp[41]; // DP 배열: 각 구간의 좌석 배치 방법의 가짓수를 저장int main() { ios::sync_with_stdio(false); cin.tie(NULL);..
시간 복잡도(Time Complexity) [시간 복잡도] 알고리즘이 실행되는 데 걸리는 시간은 컴퓨터가 알고리즘 코드를 처리하는 속도에 의존할 수밖에 없다. 그리고 이 속도는 운영체제, 하드웨어, 프로그래밍 언어, 컴파일러 등 실행 환경에 따라 달라질 수 있다. 그러므로 알고리즘의 성능을 평가하기 위해 입력크기에 따라 컴퓨터가 수행하는 연산의 횟수를 수치화시킬 필요가 있다. 시간복잡도는 이렇게 수치화된 값을 가지고 알고리즘 수행시간 및 성능을 나타낼 수 있는 지표이다. 당연히 시간 복잡도의 수치가 작으면 작을수록 더 효율적이고 성능 좋은 알고리즘이 된다. 시간복잡도는 알고리즘의 복잡도를 단순화시켜 입력값의 크기에 따른 증감 추세를 점근적으로 나타낸다. 이러한 기법을 점근 표기법이라고 한다. 일반적으로 우리가 알고 있는 시간 복잡도는 점근 표기법..
백준 15988번 [1, 2, 3 더하기 3](C++) -yes6686- 티스토리 백준 문제 풀이: 15988 [1, 2, 3 더하기 3]문제 링크: https://www.acmicpc.net/problem/15988문제 설명:정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 결과는 1,000,000,009로 나눈 나머지를 출력해야 합니다.예를 들어, N=4일 때 가능한 방법은 다음과 같습니다: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 (총 7가지).동적 프로그래밍을 활용해 효율적으로 풀이합니다.문제 해결 코드#include #define MOD 1000000009#define MAX 1000001using namespace std;long long int dp[MAX]; // 각 숫자를 1, 2, 3의 합으로 나타내는 경..
주기억장치〔RAM〕 RAM은 CPU의 명령어 처리를 도와준다. 주기억장치는 크게 RAM과 ROM으로 나눠볼 수 있다. 우리가 일상생활에서 흔하게 말하고 듣는 메모리가 주기억장치라고 생각하면 된다. [RAM의 특징] RAM의 영어 약어를 풀어써본다 ㄴRandom Access Memory 임의 접근 기억장치로 직역할 수 있다. 말 그대로 RAM은 데이터를 임의로 접근해서 무엇인가를 할 수 있다는 것이다. 또한 임의로 접근할 수 있다는 것은 데이터를 굉장히 빠른 속도로 CPU에 보내거나 저장할 수 있다는 것이다. 그런데 RAM은 속도는 굉장히 빠르지만 휘발성 저장 장치라는 단점이 있다. 휘발성 저장 장치라는 것은 컴퓨터가 On 되어 있을 때 RAM안에 저장하고 있는 정보들이 컴퓨터가 Off 되면 다 사라져 버린다는 뜻이다. 비휘..
백준 2579번 [계단 오르기] (C++) -yes6686- 티스토리 백준 문제 풀이: 2579 [계단 오르기]문제 링크: https://www.acmicpc.net/problem/2579문제 설명:계단 오르기 게임에서 점수를 최대로 하기 위한 문제입니다. 계단은 한 번에 1칸 또는 2칸씩 오를 수 있으며, 연속된 세 개의 계단을 밟을 수 없습니다. 각 계단에는 점수가 주어지고, 마지막 계단은 반드시 밟아야 합니다.문제 해결 코드#include #include using namespace std;int arr[301]; // 각 계단의 점수int dp[301]; // 해당 계단까지의 최대 점수int main() { int n; // 계단의 개수 cin >> n; // 계단 점수 입력 for (int i = 1; i > arr[i]; } /..
백준 2156번 [포도주 시식] (C++) -yes6686- 티스토리 백준 문제 풀이: 2156 [포도주 시식]문제 링크: https://www.acmicpc.net/problem/2156문제 설명:여러 잔의 포도주가 일렬로 나열되어 있고, 포도주를 마시는 규칙은 다음과 같습니다:포도주는 연속으로 세 잔을 마실 수 없습니다.각 포도주의 양이 주어질 때, 최대한 많은 양의 포도주를 마실 수 있는 값을 구합니다.문제 해결 코드#include #include using namespace std;int arr[10001]; // 각 포도주의 양int dp[10001]; // i번째 포도주까지 최대 마실 수 있는 포도주의 양int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; // 포도주 잔의 개수 ..
백준 5719번 [거의 최단 경로](C++) -yes6686- 티스토리 문제 링크 : https://www.acmicpc.net/problem/5719 이 문제를 푸는 사람들은 이미 다익스트라 알고리즘에 대해 이해했고 구현할 줄 아는 people일 거다.. 그쵸?? 이 문제를 풀기 위해서는 생각이란 걸 하면 된다,, [문제에서 거의 최단 경로는 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것이라고 한다.] ㄴ이 문장을 읽고나서 대부분의 사람들은 머리가 띵~!하고 울렸을 것이다.. 그렇다면 거의 최단 경로를 구하기 위해서는! (일단 다익스트라 알고리즘을 이용해 시작점에서 도착점까지 최단경로로 가는 경로를 구한다.) ㄴ경로를 vI벡터에 저장해줄건디.. 가장 짧은 경로만 저장해야하니께 더 작은 값이 나오면 vI[next].clear()를 해준다. ㄴ그리고 최단..
CPU[1]〔레지스터〕 (컴퓨터의 구조의 4가지) ㄴ〔 중앙처리장치 〕 ㄴ〔 주기억장치 〕 ㄴ〔 보조기억장치 〕 ㄴ〔 입출력장치 〕 이 중에 중앙처리장치는 CPU라고 불리며 컴퓨터의 머리를 담당하고 있다. CPU는 컴퓨터에서 크게 4가지 주요 기능을 수행한다. -인출 : 외부에서 정보를 입력받음 -해석 : 컴퓨터 프로그램의 명령어 해석 -실행 : 해석한 데이터를 연산 -쓰기 : 외부로 출력 그리고 CPU는 레지스터, 연산장치, 제어장치로 구성되어 있다. [레지스터] 레지스터는 CPU 내부에 존재하는 임시기억장치이다. 레지스터는 물리적으로 CPU 옆에 붙어서 데이터 처리 속도를 높여준다. CPU내에 존재하는 저장공간이기에 컴퓨터에서 제일 빠른 저장 공간이라고 볼 수 있다. 속도 : 레지스터 > 캐시 메모리 > 주기억장치 > 보조..
728x90
LIST

티스토리툴바