메모장

개요 두 포인터(Two Pointers) 혹은 슬라이딩 윈도우(Sliding Window)라고 부른다. 1차원 배열에서 2개의 포인터를 조작하며 값을 얻는 기법이다. 본문 예를 들어 1차원 배열에서 구간 합의 경우의 수를 찾는 문제가 있다고 하자. 위와 같이 브루트포스로 경우의 수를 찾게 된다면 O(N^2)가 될 것이다. N의 범위가 10만을 넘기기만 해도 시간 초과가 나버리게 된다. 이럴 때 필요한게 두 포인터다. 두 포인터(Two Pointers) front와 back 처럼 두 개의 포인트를 잡고 시작한다. 현재 합이 20보다 작으므로 b를 뒤로 움직여 부분합을 증가시킨다. 합이 20보다 커질 때 까지 b 포인터를 뒤로 움직인다. 20이 된 경우의 수가 있다면 count를 증가시킨다. 위처럼 합이 2..

개요 https://nakuri.tistory.com/41 [BOJ] 1937 욕심쟁이 판다 C++ 개요 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, nakuri.tistory.com 위 문제를 풀다가 잘못된 코드로 인해 배열의 음수 인덱스에 접근을 했다. 제출했더니 에러가 나지 않고 정답이 나와버려서 궁금증에 한 번 알아봤다. 본문 C++에서는 잘못된 문법이 아니라고 한다. 배열과 포인터의 작동방식이 같기 때문에 이전 포인터를 참조하는 것이다. 하지만 초기화 되지 않은 공간을 참조했기 때문에 문제가 풀린 건 그냥 운..

개요 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 골드급 DFS + DP 문제다. 풀이 처음에는 재귀를 활용한 DFS로 접근했다. 모든 구간에서 DFS로 탐색했고, 최대값을 구했다. visited 배열에 판다가 이동한 값의 최대 값을 기록하며 가지치기 해줬다. (다음 칸이 현재 칸보다 높은 값일 경우 continue) 하지만 결과는 시간 초과 행렬 기반 DFS는 O(V^2)다. 500*500을 25,000이라고 착각해서,,,, 2..

개요 https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 실버급 BFS/DFS 문제다. 풀이 DFS를 사용해서 풀었다. 입력이 문자열인 점, 모든 위치에서 탐색을 수행해야 된다는 점을 제외하면 기본적인 DFS/BFS 문제와 동일하다. 한 노드에서 시작된 탐색이 끝날 때마다 memset 함수로 visited 배열을 초기화해 줬다. memset 사용 시 cstring 헤더를 include 하지 않으면 컴파일 에러가 나니 주의해야 한..

개요 https://www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 실버급 정렬 문제다. 풀이 STL의 sort로 간단하게 해결할 수 있다. algorithm 헤더를 include 해서 사용할 수 있다. std::sort는 intro sort라는 방식을 사용하는데, quick sort의 개선 방식이라고 한다. 기본적으로 퀵 정렬의 빠른 성능을 내지만 최악의 경우에도 O(nlogn)을 보장한다. // 오름차순(기본) sort(begin, end..

개요 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 실버급 백트래킹 문제다. 풀이 배열을 재귀로 탐색하다 조건이 맞으면(수열의 길이가 M이 됐을 때) 리턴시켜줬다. 방문이 끝나면 다른 경우의 수에서도 인덱스를 방문 할 수 있도록 방문 배열을 다시 false 시켜주어야 한다. 코드 #include #include using namespace std; constexpr int LIMIT = 10; int N, M; int num[LIMIT]; ..

개요 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 골드급 BFS 문제다. 풀이 [BOJ] 2206 벽 부수고 이동하기 C++ [BOJ] 14442 벽 부수고 이동하기 2 C++ 위 문제에서 이어지는 문제다. 낮과 밤, 정지라는 개념이 추가되었다. visited 배열의 차원을 하나 늘려서 어느 시간에 왔는지를 체크할 수 있도록 해주었다. 벽에 있을 때 밤인 경우 부시는 기회를 감소시키고, 낮에 벽에 왔을 경..

개요 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 골드급 BFS문제다. 풀이 https://nakuri.tistory.com/35 위의 벽 부수기 1 코드와 거의 일치한다. 다른 점이라면 벽을 부실 수 있는 기회가 한 번이 아니라 여러 번인데, 애초에 여러 번 할 수 있는 확장성을 고려하고 작성했었던 코드라 아주 살짝만 수정하면 됐다. 코드 #include #include #include using nam..

개요 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 골드급 BFS 문제다. 풀이 처음에는 구조체에 카운터 변수(cnt)와 부실 기회 변수(brk)를 추가해서 그냥 BFS 돌리면 될 줄 알았다. 테스트 케이스는 통과했지만 오답이 나왔다. 문제는 visited 배열에 있었다. 초반에 벽을 부순 경우의 수가 특정 위치에 방문을 먼저 해버리면 그렇지 않은 경우의 수 들은 전부 방문할 수 없게 된다. 하지만 나중에 벽을 부수어..

개요 https://www.acmicpc.net/problem/26162 26162번: 인공 원소 원자 번호 43번을 가진 테크네튬은 세계 최초의 인공 방사성 원소이자, 가장 가벼운 방사성 원소이다. 테크네튬의 최초 발견은 특이하게도 자연이 아닌 인공 합성을 통해 이루어졌는데, 원자 번 www.acmicpc.net 실버급 소수판정&브루트포스 문제다. 풀이 에라토스테네스의 체로 소수를 판별한 후, 브루트포스로 답을 구했다. 근데 풀고나니까 골드바흐의 추측이란걸 이용하면 훨씬 더 간단히 구할 수 있다는 사실을 알아 버렸다,, 골드바흐의 추측 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것 코드 #include using namespace std; constexpr..