꺼진불도다시보자

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 접근방법 최고점과 최저점을 저장한 후. 최고점에서 한 칸 제거하는 시간과 최저점에서 한 칸 추가하는 시간을 비교한다. 더 짧은 시간이 걸리는 쪽을 선택하고, 만약 최저점에서 추가할 블록이 없는 경우에는 무조건 최고점에서 한 칸 제거를 택한다. 코드 #include #include #include #include #include #include #include #include #include..

문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 접근방법 삼성 sw역량평가에 출제됐던 문제라고한다. 푸는 방법은 대충 bfs 이용해서 하는 거 같은데, 코드가 복잡해지니까 나중에는 디버깅이 잘 안되서 많이 헤멨다. 그래서 유투브를 참고했다. 링크 : https://www.youtube.com/watch?v=SarTy3ZwmVo&t=1114s&ab_channel=na982 내가 생각했던 풀이..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근방법 bfs를 이용해 푸는 문제였다. 처음 dfs로 접근했는데, dfs로 풀기엔 쉽지 않을 거 같다. sum과 cnt를 계산해야하는데 dfs를 사용하면 복잡해진다. 어쨋든 dfs든 bfs든 포인트는 돌면서 마주친 나라들을 배열에 담아두어서 나중에 한번에 sum과 cnt를 계산해 table의 값을 변경해 주는 것이다. 이를 위해서 table을 전역변수로 설정하는 것이 유리하다..

문제 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 접근방법 k의 개수만큼 배열의 크기를 유지하는 게 포인트라고 생각했다. 각 알파벳마다 인덱스를 저장할 배열이 필요했고, 그 배열의 크기는 k로 일정했으면 좋겠다는 생각이 들어서 queue를 선택했다. 각 알파벳마다 queue를 만들었다면, queue에 k개의 원소가 채워질 때마다 첫번째 인덱스와의 거리를 계산한후 push, pop해주면 된다. 그러면 queue의 크기를 항상 k로 유지할 ..

문제 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 접근방법 S에서부터 시작하는 방법은 2^50의 시간이 걸려서 불가능하다. 거꾸로 T에서 시작해 하나씩 지워나간다면, 경우의 수를 줄일 수 있다. T에서 시작하는 경우, 1. 맨 뒤의 문자가 'A'인 경우 -> 삭제 2. 맨 앞의 문자가 'B'인 경우 -> 삭제 3. 맨 뒤의 문자가 'B'인 경우 -> 삭제 불가 4. 맨 앞의 문자가 'A'인 경우 ->..

문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 접근방법 이 문제는 메모리를 신경써야하는 문제였다. 12mb면 12000byte인데, 무턱대고 2차원 배열 만들어버리면 메모리초과다. 따라서 입력을 받는 중간 중간 메모리를 정리해줘야한다. priority_queue로 풀어도 되는데, vector로 푸는 게 더 빠를 거 같아서 vector를 썼다. 메모리가 제한되므로, 한 줄 받을 때마다 상위 5개 숫자빼고 다 배열에서 pop했다. 코드 #inclu..

문제 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 접근방법 O(n*n)의 시간복잡도로는 해결하기 힘든 문제였다. 그리디 알고리즘이라고 생각하고 풀려고 했지만 잘 안 풀렸다. 결국 생각해낸 방법은 매수 매도 포인트를 미리 정해두는 것이다. 매일 하나씩 주식을 살 수 있으므로, 매도는 어차피 뒷 순서에 위치한 가장 큰 숫자에서 이루어질 수밖에 없다. 따라서 뒤에서부터 훑으며 매수 포인트와 매도 포인트를 구분할 수 있었다. 코드 //..

문제 https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 접근방법 .. 코드 #include #include #include #include using namespace std; #define FOR(i, n) for(int i=0;i> p >> m; FOR(i, p) { int temp; string name; cin >> temp >> name; //들어갈 방이 있으면 넣고, 아니면 방새로 생성. if (!insert(temp, name)) { b..

문제 https://www.acmicpc.net/problem/22233 접근방법 포인트는 2가지이다. parsing과 unordered_set 사용. 인풋값이 아래와 같이 크기때문에 최대한 시간을 줄이는 방법을 택해야한다. 1 ≤ N ≤ 2×10^5 1 ≤ M ≤ 2×10^5 map에서 접근 시간은 O(1)로 알고있었는데, map을 사용하니 시간초과가 났다. 알고보니 O(1)이 아니었다. map과 set은 둘 다 red-black-tree를 사용하고, unordered_set은 hash-table을 사용한다고 한다. 다음을 참고하자. - **std::map** - **Find:** O(log n) (finding a value by key) - **Inserting:** O(log n) - **Dele..

문제 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 접근방법 이분탐색이다. 이분탐색을 할 때 중요한 포인트는 오른쪽으로 이동할 때, mid+1을 해주고 같은 값(정답이 될 수 있는 값)일 때는 왼쪽으로 이동해주는 것이라고 생각한다. mid = (left + right) / 2이므로 left와 right이 이어지는 숫자인 경우, 항상 mid는 left에 위치하기 때문에, 여기서 만약 정답이 left에 ..