해당 포스터는 파킹독님의 유튜브를 보고 작성되는 점 참고해주세요. https://www.youtube.com/watch?v=mBeyFsHqzHg 배열이란? 배열 : 메모리 상에 원솔르 연속하게 배치한 자료구조 (이 점 때문에 본인의 vector 구현이 realloc해서 인덱스 접근이 가능한 점!) 배열의 성질 메모리 상에서 연속하기에 O(1)로 k번째 원소를 확인 / 변경 가능하다. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없다 (운영체제에서 나오는 것, 참조의 지역성때문, cache hit rate가 높음) 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. 배열의 기능 임의의 위치에 원소를 추가, O(n) 임의의 위치에 원소를 삭제, O(n) 사실 C를 사용하는 것이 아니..
문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 입출력 해설 분할정복 문제인데 간단해 보이지만 사실은 아니다... 일단 자신이 분할정복을 어느 정도 한다면 이 문제만 읽었을 때는 굉장히 쉽다고 느꼈을 것이다. 하지만 단순하게 생각하면 안된다. ( 필자는 처음에 풀 때 굉장히 쉽게 풀어서, TLE를 계속 맛봤다고 한다...) 일단 이 문제는 여러 해답이 있는지는 모르겠지만 필자는 가상의 선이 있다는 형식으로 풀었다. 예를 들어 자신..
문제 https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 입출력 해설 이 문제는 백트래킹의 기본 문제이다. 하지만 수열을 1,2와 다르게 이번 백트래킹 문제는 따로 번호를 뽑았는지에 관해서 정보를 저장하고 있을 필요가 없다. 중복으로 뽑아도 되기 때문이다. 그럼 어떤 식으로 뽑는지 규칙을 살펴보자. 9,8,7,1 에서 2개를 뽑아서 나열하는 방법을 한 번 보자. 나오는 수열은 오름차순으로 나와야 하기 때문에 뽑기 전에 정렬하는 것이 제일 ..
문제 https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 입출력 해설 이문제는 단순하게 구현하면 된다. 하나의 토탈 값을 갖고 있고 모든 값을 저장할 배열하나 갖고 있는다. 1. 가장 짧은 것을 절반으로 자른다. 2. 자른 것중 하나를 제외하고 갖고 있는 모든 막대들 더한다. 3. 다 더한 것이 x보다 크거나 같은지 판별하고 맞으면 절반 하나를 버린다. 아니면 둘 다 다시 저장한다. 이 순서대로 구현하면 된다. 정답코드 c언어 더보기 #incl..
문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 입출력 해설 내가 새로 심어야 하는 곳은 각 가로수 지점 사이이다. 그럼 여기서 문제는 각 가로수 지점 사이에 최소로 지어야 한다면 어떻게 라는 생각이 들 것이다. 그러면 최소로 지을 거면 어떻게 해야 될까? 다음을 한 번 보자. 예를 들어 가로수가 1,3,7,13 예제 1번 처럼 있다고 해보자. 그러면 1~3, 3~7, 7~13 이 3개의 사이점 안에 가로수를 지어야 한다. 각 사이..
문제 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 입출력 해설 이 문제는 bfs를 이용해서 풀었다. 일단 초기 숫자는 0부터 9까지 넣었다. 그리고 나서 새로운 숫자는 전에 숫자에다가 %10 + 0~9 이다. 새로운 숫자를 만들 때마다 cnt를 증가하다가 n번째가 되면 새로 만든 숫자를 리턴해주면 된다. 정답코드 c언어 더보기 #include #include #define ll long long /* https://www.ac..
문제 https://www.acmicpc.net/problem/15918 15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net 입출력 해설 해당하는 문제는 굉장히 심플한 백트래킹 문제이다. 해당하는 인덱스 0부터 최대 23까지 24개의 숫자들을 놔두면 되는 것이다. 여기서 어떤 것을 기준으로 백트래킹하는 지에 따라 시간초가 갈리게 된다.(본인은 처음에 숫자를 기준으로 백트래킹했음) 중요한 것은 x와 y에는 같은 수가 있어야 하므로 x,y인덱스에는 무조건 들어가야하는 숫자는 정해져 있기에 미리 넣는다. 그리고 i숫자 사이에는 i개의 수가 있어야 되기에 인덱스를 골랐으면 인덱스 + ..
문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 입출력 해설 해당하는 문제는 브루트 포스로 풀어도 되지만 본인은 bfs 방식을 먼저 떠올렸기에 bfs를 이용해서 풀었다. 일단 c언어로 풀기에 queue를 직접 구현해서 bfs를 돌렸다.(큐 구현 -> https://i-m-possible.tistory.com/13) 일단 bfs를 돌릴 때 n과 같아지면 return 하게 되고, next로 나올 수 있는 숫자들은 0부터 9의 ..
