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까지 돌며 해당 배열의 값 중에 '어떤 수의 배수'인 값만 ..
PS
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..
[풀이] n개 자연수 중 r개를 고르는 조합 문제이지만 nCr에서 r의 모든 경우의 수를 고려해야 하는 문제이다. 따라서 각 숫자가 포함되냐, 아니냐 두 가지 경우로 나눠 2^n 개의 경우의 수를 고려하는 문제로 바꿔 생각할 수 있다. 예를 들어, n=3이고 {1,2,3}을 고려해야하는 문제라면 3C0, 3C1, 3C2, 3C3 네 가지 경우를 모두 고려해야 하며 해당 경우의 수는 모두 1+3+3+1 = 8가지인데, 각각을 포함되냐 포함되지 않냐로 구해도 마찬가지로 2^3 = 8가지 이다. 이를 재귀함수를 이용해 구현하면 다음과 같다. vector v; int n, ret; void go(int idx, int sum) { if (idx == n){ ret = max(ret, sum%11); return..
1260. 노드와 간선으로 이루어진 DFS, BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [풀이] #include using namespace std; vector adj[1002]; int vis1[1002]; int vis2[1002]; int N,M,V; void dfs(int cur){ cout N >> M >> V; for(int i=0; i> u >> v; adj[u].push_back..
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(..
1. 시간 초과 -> 시간복잡도를 고려하자 (자료구조, 알고리즘구조, 누적합) 런타임 에러 -> 인덱스 초과 참조, 음수 인덱스 참조 분모에 0 자료구조 empty 상태에서 pop(), top() 틀렸습니다 -> 예외처리 (문제해석할 때 예외 파악하기) 2. 변수를 전역으로 초기화할 때 지역변수로 반복 초기화해야하는지 확인 3. 구현 단계를 나눠서 코딩해야 단계별 디버깅 가능 4. 구현할 때 시간이 적게 걸리는 방법을 고려하는 습관 5. 입력 혹은 출력 형식이 특이할 때 예외처리를 확실히 해야한다. ex) [1,2,3] 과 같은 형태로 정수를 입력받을 때 모든 경우 char를 처음에 한 번, 정수 뒤에 한 번씩 받으면 되지만 [] 입력값이 없는 경우만 처음에 한 번, 정수가 없어도 마지막에 한 번 받도록..
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가 아닌 배열..
