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가 아닌 배열..
2559. 누적합 (prefix sum)https://www.acmicpc.net/problem/2559 2559번: 수열첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기www.acmicpc.net[풀이] 누적합을 이용한 풀이를 생각해내지 못하면 시간초과를 받게되는 문제이다. 나 또한 그랬다. 첫 번째 코드는 누적합 없이 푼 코드이다. → 시간초과 참고로 accumulate()는 O(N)이며 해당 코드의 시간복잡도는 O(N^2)이다.#include using namespace std; vector input; int N, K, in, maxim..
