Stargazer

접근: 처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다. 대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에 위상 정렬로 풀어야 한다는 걸 알 수 있다. 전략: 대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트) 진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다. 제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 코드: #include #include #include using namespace std; int n,m; vector comp; vector income; int main(){ cin >> n >> m; comp..

접근: 스도쿠 자체로 크기가 9x9로 정해 있기 때문에, 백 트래킹 이 가능한 크기다. 따라서 백트래킹으로 하나씩 전부 조사하되 사전식으로 조사하면 된다. 전략: 앞에서 부터 하나씩 입력 받을 때, 0의 위치와 갯수를 입력받아서 백트래킹으로 각 점을 대입하면서 답을 찾아본다. 코드: #include #include using namespace std; int map[9][9]; int cnt = 0; bool flag = false; vector vac; bool visit[81] ={false,}; void print(){ for(int i=0;i

접근: 어떤 자연수가 주어지면 그것보다는 작은 소수의 합의 갯수를 구하는 것이므로, n보다 작은 소수의 배열을 구하고, 그에 맞는 구간 합을 구하면 된다. 전략: 소수를 구하는 것은 에라스토테네스의 체를 이용하여 구하면 되고, 구간합은 투 포인터(two pointers)를 이용하여 구하면 된다. 코드: #include #include #include using namespace std; vector sosu; //n이하 소수 배열 bool so[4000001]; //소수 판별 배열 int n; int sum = 0; int s = 0, e = 0; int res = 0; int main(){ cin >> n; for(int i=2;i= sosu.size()) break; sum += sosu[e++]; ..

접근: 전광판이 무한으로 연결되어서 나오는 형태의 광고이기 때문에 적어도 L 만큼은 광고 할 수 있음이 보장이 되어있다. 문제는 주어진 문자열에 대해서 어떤 광고를 말하는 것인지 최소 길이를 구하는 것이다. 문제의 예에서도 말했듯이, aabaaa 가 주어졌다면, aaba 는 광고가 가능한 최소 길이이다 중요한 것은 반복할 문자열이 그 뒤에 얼마나 겹치는 가이다. 그래서, 최소 길이를 구하려면, 길이 L 에서 최대한 겹치는 부분을 제외한 나머지 부분으로 구해야한다. 위 예로 들자면 aabaaa 처럼 뒤에 2개가, 길이 L이 주어졌을 때, 반복하면 최대로 겹치는 부분이다. 그렇기 때문에 저 2개를 제외한 나머지 부분이 반복해야 할 최소 길이가 된다. 전략: KMP 알고리즘을 이용하여, 하나씩 길이를 늘려가면..

접근: 가방에는 무조건 1개만 넣을 수 있고, 최대한 넣었을 때 가장 가치가 높은 거를 넣어야 하는데, 가방 중에 가장 작은 가방에 들어갈 정도의 보석이라면, 다른 가방에는 무조건 들어갈 수 있게 된다. 전략: 가방과 보석을 크기 오름차순으로 정렬을 한다. 모든 가방을 조사하면서, 이 가방에 들어갈 수 있는 보석을 모두 꺼내어 놓은 뒤, 이 중 가장 가치 있는 것을 넣어서 하나 씩 가방을 채운다. 그렇게 되면, 들어갈 수 있는 가방 중에 가장 가치 있는 것 부터 넣을 수 있게 된다. 이때, 우선순위 큐를 이용하면, 가방에 들어갈 수 있는 보석 중에 가장 가치 있는 것을 선택하기 수월하다. 각 보석은 조사할 때 한 번 우선순위 큐에 들어간 보석은 더는 조사하지 않는다. 이유는 우선순위 큐의 성질에 의해서 ..

접근: 일반적으로 계산하면 시간 초과가 뜨는 문제이다. 반복적으로 더해주는 작업을 하는 것이기 때문에 DP로 접근하여서 푸는 것이 적절해 보인다. 전략: 구간 합을 입력 받을 때 마다 (0,0) 부터 (x2,y2)를 구해주어 2차원 배열로 저장하고, 구간 합이 주어지면 구해준 구간 합의 조합{(0,0) ~ (x2,y2)}으로 해결해주면 된다. (x1 - 1 , y1 - 1) (x1 - 1, y2) (x2 , y1 - 1) (x2 , y2) 구하고자 하는 값이 (x1,y1)부터 (x2,y2) 까지의 구간 합 이므로, (x2, y2) - (x1-1 ,y2) - (x2 ,y1-1) + (x1 - 1 , y1 - 1) 이런식으로 구해준 값으로 겹치는 영역을 빼고 더해주면 원하는 구간의 값이 나온다. 구현: #i..

접근 이름부터 플로이드 이지만, 단순히 문제만 바라보면, 도시의 가장 빠른 길을 찾는데, 모든 도시를 대상으로 찾아야 한다. 이렇게 모든 대상에 대해서 최단 경로를 구하려면, 플로이드 워셜(Floyd-Warshall) 알고리즘을 이용하면 된다. 그렇지만 나는 이 알고리즘을 제대로 이해하지 못해서 다른 방식으로 해결했다. 전략 플로이드 워셜 알고리즘의 전략은 각 정점을 조사해서 해당 정점을 사이로 지나는 두 정점을 찾아서 만약 더 짧은 거리이면 짧은 거리로 갱신한다(두 정점의 직접 경로가 없는 건 ∞ 로 가정) 본인은 잘못 이해 해서 시간 복잡도가 조금 더 증가했다. 각 도시 간 거리를 매트릭스의 형태로 저장해서 각 행에 대해서 조사를 하는데, 만약 경로가 있는 도시가 있다면, 그 도시로부터 다른 도시를 ..

#include #include using namespace std; int n, k; // n: 물품의 수, k: 버틸 수 있는 무게 int DP[101][100001]; int W[101]; int V[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i > W[i] >> V[i]; } for (int i = 1; i

접근 3가지의 선택: -1, +1, x2 그리고 가장 작은 weight를 가지는 길을 찾아야 한다. 그래서 일단은 너비 우선 탐색을 선택했다. 왜냐하면 가장 짧은 길을 탐색하기 위해서 너비를 우선으로 탐색해야 하기 때문이다. 그렇게 하기 위해 큐를 이용하기로 했다. 그리고 가중치가 0,1 로 다르기 때문에 다익스트라 알고리즘을 이용하기로 했다. 전략 큐에 n의 위치를 넣고, 3가지 선택 중에 선택을 할 수 있는 조건을 만족하면(범위 내 이고, 가중치가 더 작으면) 선택을 하여 큐에 삽입을 한다. 이때, 중요한 건 선택 순서가 중요한데, 2배를 하면 가중치가 0이기 때문에, 3가지 중에 2배를 하는 것을 먼저 선택하도록 순서를 정해야, 최소의 가중치를 구할 수 있다. 방향성이 음수로 가는 방향은 -1 밖에..

*이 포스팅은 "C++ How to Program(10th)(Paul Deitel,Harvey Detiel)"를 참고하여 정리한 포스팅임을 밝힙니다* 프로그래밍이나 전공 시험에 전적으로 도움이 되지 않는 내용은 배제하고 정리할 것이니 유의하시기 바랍니다. 1단원은 교양,역사지식이 대부분이므로 조금은 알아야 되는 내용은 넣도록 하겠습니다. 컴퓨터란? 컴퓨터 계산이나 논리적 결단을 하는 장치 프로그램(소프트웨어) 컴퓨터의 데이터를 처리하도록 조종하는 명령의 집합 프로그래머의 의해 만들어진다. 하드웨어 컴퓨터를 구성하는 다양한 장치 ex) 키보드, 스크린,마우스, 하드디스크, 메모리, 시디롬, 처리 장치 등 컴퓨터의 6가지 장치들 -입력장치 입력을 받는 부분. 여기서 정보를 얻는다. 마우스,키보드,마이크,스캐..