tmi)2022년의 개강날이다. 3학년의 시작이다. OT가 끝나서 시간이 좀 비어서 중도에서 코딩 한문제 풀고 올린다. https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 사고과정) 우선 처음엔 당연히 M~N까지 2부터 M까지 쭈우욱 돌려보려했다. 하지만 이럴 경우 반복문이 두 개 이므로 O(N^2)이다. 저번에 소수 관련해서 포스팅을 올릴 때 , 에르테스토노스의 체? 라는 방법을 공지했다. 1 2 4 8 16이 16의 약수인데 어차피 16의 제곱근인 2 4로 나뉘어지는 거면 자..
https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net x, y 좌표 두 개가 필요해서 이차원 배열을 활용하는 방법도 있지만, pair 자료형을 사용해봤다. 약간 특이한 점이 있다면, y좌표를 기점으로 둬야한다는 것이다. 그렇기에 기존의 sort함수를 활용할 때 추가적인 기능을 같이 넣어줘야한다. #include #include #include using namespace std; bool co..
https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net x > p 그리고 y > q 가 핵심이다. 우선 좌표가 x,y 이렇게 두 개이기에 pair을 활용했다. 그 다음 해당 사람 한 명 마다 나머지 사람 전부를 비교해야하므로 이중 반복문을 활용해주었다. 등 수 표현이 약간 처음에 이해가 잘 안되었는데, 문제 그대로 '자신보다 더 큰 덩치의 사람이 k명이면 그 사람의 등수는 k + 1' 이 된다를 활용하면 된다. #include #inclu..
우선 가장 먼저 생각해볼 생각. #include using namespace std; int main() { int i, n; unsigned long long counter = 0; for (n = 2; n
https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 경우의 수를 생각해봤다. 15 * 28 * 19 정도이다. 안 크다. 그냥 그래서 숫자를 하나씩 키워가면서 맞는 경우를 판단하게 했다. 해당 범위를 넘기면 바로 다시 1로 초기화 시키고. #include using namespace std; int main() { int result = 1; int E, S, M; cin >> E >> S >> M; int e = 1, s = 1, m = 1; whil..
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 처음의 생각은 초기 상태도 생각해줘야하니, 초기 상태에서의 최대 갯수를 구하려했다.(예시 2) 하지만 생각해보면 PPPP에서 오른쪽으로 2개 교환해도 결국엔 같으니, 그건 의미없다 판단. 오른쪽으로 한번 OR 아래로 한번 교체를 해주면 결국엔 모든 사탕을 교체할 수 있으니, 케이스가 2가지다. 교체를 하고, 확인하고 , 다시 원상태를 위한 교체를 해줘야한다. 안해주면 다음 번 케이스를 하려 할 때 이미 바뀐 거로 해야하니 오류가 남. #include #include #include using namespace st..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 백준 기초 알고리즘 강의를 수강하며 같이 푼 문제이다. 경우의 수가 9C7 = 9C2 = 36이다. 매우 적은 수라 그냥 다 해보기로 했다. (이게 브루트포스) 7개 다 찾는 것보단 그냥 해당 안되는 2개를 찾는게 빠르겠다 싶었다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); co..
https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 그냥 조건문과 C++의 stack을 활용해서 구현했다. 특이한 건 없다.. #include #include #include using namespace std; int main(int argc, char* argv[]) { std::cin.tie(NULL); std::ios::sync_with_stdio(false); int count = 0; cin >> count; std::..
