1929. 에라토스테네스의 체https://www.acmicpc.net/problem/1929[풀이]일반적으로 n이 소수인지를 판별할 때 n을 2부터 n-1까지 나눈 나머지로 판별한다. 시간복잡도가 O(n)이다.그러나 m과 n 사이의 소수를 판별할 때는 이중 반복문이 사용되어 O(n^2)이 된다. n의 최대크기가 1,000,000정도로 커졌을 때 위와 같은 방식으로는 시간초과를 피할 수 없다. 그래서 에라토스테네스의 체라는 수학적 방법을 사용하게 되는데, 그냥 이게 더 빠르구나하고 외우고 활용하는게 좋을 것 같다. 우선 최대크기의 배열을 하나 잡는다. 나는 a[1000001]라고 잡았다.1) 그리고 각 인덱스값을 값으로 할당해준다.2) 2부터 n까지 돌며 해당 배열의 값 중에 '어떤 수의 배수'인 값만 ..
c++
1926. to_string()https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PTeo6AHUDFAUq&categoryId=AV5PTeo6AHUDFAUq&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 3 6 9 게임을 프로그램으로 제작중이다. 게임 규칙은 다음과 같다. 1. 숫자 1부터 순서대로 차례대로..
10814. stable_sort() https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net [풀이] 해당 문제는 pair의 first를 기준으로 오름차순 정렬하는 문제인데 first가 같을 때 먼저 입력 받은 pair를 먼저 출력하는 문제이다. 그냥 sort를 사용해서 구현해도 입력받은 순서대로 정렬되는 것처럼 보이지만 실제로 이를 보장하진 않는다. 따라서 stable_sort()를 사용해 이를 보장받아야 한다. #include using namespac..
1697. BFS https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 문제를 보고 BFS라는 것을 알아야 하는 문제이다. 꼭 2차원배열에서 상하좌우로 움직이지 않더라도 1차원배열에서도 앞 뒤로 움직이는 문제를 BFS로 해결할 수 있다. 또한 해당 코드에서 N과 K가 같을 때를 edge case로서 예외처리 해주어야 한다. #include using namespace std; int board[1000000]; i..
2178. BFS https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 각행의 수들은 붙어서 입력이 들어온다. 이러한 경우 이중 for문을 통해 입력받는 방법을 코드로 확인할 수 있다. 2차원 배열 board을 선언할 때부터 문자열의 배열로 선언할 수도 있지만 더욱 실수할 확률이 높다. 뿐만 아니라 각 칸의 dist 배열을 2차원으로 초기화하는데 이중 for문이 필요하기 때문에 같이 사용하면 된다. #include using namespace std; #define X f..
1620. Map https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net [풀이] 시간복잡도에 관계없이 코드를 짜면 vector를 사용한 구현 방법도 존재하고 map 하나만 사용한 구현 방법도 가능하지만 모두 시간초과가 발생하며 map와 map 두 개의 map을 사용한 구현 방법만이 Accepted를 받을 수 있다. 1) 먼저 pair의 vector 를 사용한 코드를 보자 vector a; int N,M; int main(..
2493. 스택의 시간복잡도 (Monotonic Stack) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [풀이] 벡터로도 풀 수 있고 스택으로도 풀 수 있는 문제이다. 하지만 첫 번째 코드인 벡터을 사용한 코드는 시간초과가 발생하고 두 번째 코드인 스택을 사용한 코드는 solved 를 받는다. 두 코드 모두 for문 안에 while 문이 들어간 시간 복잡도 O(N) 코드처럼 보이는데 왜 실행 시간이 다를까 (물론 vector가 아닌 배열..
9996. 예외처리 https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net [풀이] substr()과 find()를 사용해서 구현할 수도 있고 나처럼 reverse()를 사용해 구현할 수도 있다. 패턴에서 앞에서부터 *가 나올 때까지를 파일이름의 앞에서부터 비교하고, 패턴에서 뒤에서부터 *가 나올 때까지를 파일이름의 뒤에서부터 비교하며 패턴과 파일이름이 다르면 flag++ 한다. 이 때 예외처리를 생각하지 못해서 많이..
3273. 런타임에러(OutOfBounds)https://www.acmicpc.net/problem/3273 3273번: 두 수의 합n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는www.acmicpc.net [풀이] 위 문제를 풀면서 런타임에러를 7번이나 받아서 왜 런타임에러가 발생했고 어떤 부분에서 주의하면 되는지 설명도 하면 좋을 것 같다.런타임 에러는 1) 0으로 나눴을 때 2) 배열에 존재하지 않는 인덱스를 참조했을 때 2번의 경우에 배열의 크기를 초과한 인덱스를 참조하는 경우, 배열의 음의 인덱스를..
10988.https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.www.acmicpc.net [풀이]#include using namespace std; string input; int flag; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> input; for (int i=0; i
