백준 10942 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 전 나의 생각 팰린드롬을 만들 수열에서 S번째 수부터 E번째 까지 수가 팰린드롬을 이루었다면 1, 아니라면 0을 반환한다. 그럼 우선 팰린드롬이 되기 위한 조건을 생각해봐야 한다. 백준 예제인 (1, 2, 1, 3, 1, 2, 1) 수열을 예시로 들어서 설명하면 팰린드롬의 길이가 1이라면 어떤 숫자든 팰린드롬이다. 왜냐하면 숫자 하나는 좌우반전을 해도 결국 같은 값이 나오기 때문이다. -> palindrom[i][..
분류 전체보기
코드를 잘 쓰는 것도 중요하지만 우리가 적은 코드들이 어떤 메모리 영역에 들어가서 관리되는지 이해하는 것도 중요하다. 그래서 오늘은 메모리 구조에 대해 살펴보고자 한다. 1. 메모리 구조 메모리의 구조는 크게 4가지 영역으로 나눠져있다. 1. 코드 영역 프로그램의 실행 코드가 저장되는 공간이며 텍스트 영역이라고 부른다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리한다. 2. 데이터 영역 전역 및 정적 변수를 저장하는 공간이며 특정 함수나 개체의 인스턴스에 연결되지 않았다. 프로그램이 시작할 때 함께 할당되며, 프로그램이 종료되면 소멸된다. 3. 스택 영역 함수의 호출 및 지역 변수와 매개변수를 관리하는 영역. 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸된다. 스택은 가장 최근..
백준 1915 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전 나의 생각 0과 1이 주어진 배열값을 판단하여 정사각형의 최대 크기를 구하는 문제다. 문제를 보면 뭔가 처음부터 계속 탐색을 하면서 값을 갱신 시켜야만 될 것 같다. 그럼 우선적으로 해야 할 것은 DP가 무엇을 의미하고 어떤 값을 갱신 시킬 지 알아야한다. 1. 조건을 보면 정사각형의 최대 크기를 구해야한다. 이 말은 직사각형이 아닌 정사각형을 구해야 하니깐 한 변의 길이만 구하면 정사각형의 크기를 쉽게 구해낼 수 있다. 2. DP는 이전 값을..
백준 4883 https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 풀이 전 나의 생각 이 문제의 요점은 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 구해내는 것이다. 조건 1. N은 2보다 같거나 크거나 100000 보다 작거나 같다. 2. 정점의 비용은 정수이며, 비용의 제곱은 1000000보다 작다. 문제를 풀기위한 조건은 이와 같다. 여기서 중요한 정보는 정점의 비용이 정수라는 것이다. (정수: 0..
백준 1904 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 전 나의 생각 타일을 이용하여 2진 수열을 만드려고 한다. 하지만 0의 쓰여진 모든 타일들은 한 쌍으로 이루어진 00타일이 됐다. 이 조건을 만족하면서 자연수 N에 대해 최대로 만들 수 있는 2진 수열을 구해내야 한다. 우선 N이 1 부터 4까지 있다고 가정할 때 경우의 수를 구해보면 N = 1 -> 1 N = 2 -> 00, 11 N = 3 -> 000, 111, 100 N = 4..
백준 2293 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 전 나의 생각 n개의 동전을 조합하여 k원이 되게하는 문제다. 우선 먼저 생각할 수 있는건 n번째의 동전을 탐색하면서 얻을 수 있는 조합을 찾아내야 한다는 것이다. 그럼 1원이 3원(k = 3)까지 증가하면서 DP값을 구한다고 가정해보자. DP[1] - 1원이 될 수 있는 방법은 '1' 한 가지 DP[2] - 2원이 될 수 있는 방법은 '1 + 1' 한 가지 DP[3] - 3원이..
백준 2302 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이 전 나의 생각 N개의 극장 좌석과 M개의 VIP 좌석이 주어졌을 때 앉을 수 있는 서로 다른 방법의 가짓수를 구해야 한다. 조건 1. 일반석은 본인 자리에서 좌우로 움직일 수 있다. 2. VIP석은 움직일 수 없다. 이 조건을 만족하면서 나올 수 있는 경우들을 한 번 구해보자. 최대 자릿수가 1일 때 [1] 최대 자릿수가 2일 때 [1][2] [2][1] 최대 자릿수가 3일 때 [1][2]..
백준 2240 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 전 나의 생각 자두가 정해진 이동 횟수에 따라 자두나무에서 얻을 수 있는 최대 자두 개수를 구하는 문제다. 자두가 1초 안에 움직일 수 있기 때문에 1초마다 자두가 떨어지는 나무가 테스트 케이스로 주어진다. 그럼 자두가 어느시간에 도착했을 때 얻을 수 있는 최대의 자두 개수를 구해야 한다. 그럼 자두가 30번의 횟수 안에 어떤 나무 앞에 있으면서 몇초 때 최대값을 얻을 수 있는지 알아야..
