Algorithms/ACM_ICPC
-
백준 알고리즘, 11727 문제Algorithms/ACM_ICPC 2018. 7. 19. 16:02
개요 이 문제는 11726 문제 (2xn 타일링) 의 다른 버전이다. 11726 문제를 정확히 이해했다면 같은 방식으로 풀어낼 수 있다. 풀이 2 x n 타일링 문제에서는 2 x n 타일을 채우기 위해 1 x 2, 2 x 1 타일을 사용했다. 그러나 이 문제에서는 2 x 2 타일이 추가되었다. 무엇이 달라질까? (1) 2 x 1 (2) 2 x 2 2 x 1 과 2 x 2 를 위와같이 준비해놓았을 때 2 x 3 은 다음과 같이 그릴 수 있다. (3) 2 x 3 2 x 2 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 크기의 타일을 세로로 하나 넣는다. ---> 개수 변화 없음. 2 x 1 번 그림을 그대로 가져온 후, 오른쪽에 2 x 1 번 크기의 타일을 가로로 2개 넣는다. ---> 개수가 x 2 가..
-
백준 알고리즘, 11726 문제Algorithms/ACM_ICPC 2018. 7. 18. 14:26
개요 이 문제는 Dynamic Programming 분류에 속하는 문제이다. 앞으로 문제를 풀며 기억해야 할 점은 문제에서 언급되는 알고리즘 이외에 언어들.. 예를 들면 타일링, 직사각형, CCTV ... 등의 단어에 집착하지 말아야한다는 점이다. 가장 중요한 것은 규칙을 찾고 그 규칙에 따른 식을 만드는 것이다. 풀이 입력받는 n 에 따라 2 x n 의 타일이 생성된다. 그 생성된 타일에 2 x 1 모양, 혹은 1 x 2 모양의 직사각형을 채워나가는 방법의 수를 구하는 문제이다. 직접 그려보기로 하는데 주의해야할 점이 있다. 2 x 4 만 되더라도 그려나가는 규칙이 제대로 성립되어 있지 않으면 빼먹기 쉽고 매우 헷갈린다. 먼저 규칙을 정해야 한다. (1) 2 x 1 (2) 2 x 2 (3) 2 x 3 ..
-
백준 알고리즘, 1463 문제Algorithms/ACM_ICPC 2018. 7. 17. 16:33
개요 이 문제는 Dynamic Programming 의 첫번째 문제다. Dynamic Programming 은 반복되는 연산을 매번 하지않고 배열이나 힙 등의 저장 공간에 저장해두었다가 필요할때 사용하는 알고리즘이다. 이러한 특징 때문에 이광근 교수님이 지은 "컴퓨터 공학이 여는 세계" 에는 Dynamic Programming 이 "기억하며 풀기" 라고 설명되어 있다. 학교 수업에서도 Dynamic Programming 은 Dynamic 과 거리가 멀다고 배웠는데, 적절한 번역이라고 생각한다. 동적 계획법 이라고 하면 전혀 감이 오지않지만, "기억하며 풀기" 라고 한다면 한번에 이해가 되는 기분이다. 시행착오 다음을 기억하려 했다. 1. X 를 3 으로 나누는 연산2. X 를 2 로 나누는 연산3. X ..
-
백준 알고리즘, 입출력 관련문제Algorithms/ACM_ICPC 2018. 7. 17. 12:11
개요 백준 알고리즘 사이트에는 여러 입출력 문제가 있다. Problem Solving 을 시작하기 전에, 입출력에 관한 아주 조금의 불편함도 없어야 한다는 생각에 여러 입출력 문제를 모두 풀어내려고 한다. 이 글은 그 과정 중에서 주목할만한 부분만을 언급한다. 문제 리스트 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 - 출처: http://plzrun.tistory.com/56 [plzrun's algorithm] 주목할..
-
백준 알고리즘, 1924 문제Algorithms/ACM_ICPC 2018. 7. 16. 14:44
개요 이 문제는 흔히 볼 수 있는 DATE 관련 문제이다. 입력되는 month, date 를 미리 정해논 기준으로 count 를 해줌으로서 해결할 수 있다. 풀이 먼저 상수 전역 변수로 DATE 와 요일을 나타내는 char 포인터 배열 를 정의 해놓는다. 그다음 1 월 1 일 부터 입력되는 요일까지를 count 해준다는 의미로 처음부터 count 변수를 생각했었기 때문에 count_date 변수에 누적되는 요일값을 더해줌으로써 해결했다. /** * @site: https://www.acmicpc.net/problem/1924 * @github: https://github.com/7772 * @auth: Landon Park * @date: 2018. 07. 16 */ #include using names..
-
백준 알고리즘, 11723 문제Algorithms/ACM_ICPC 2018. 7. 13. 21:16
이 문제는 비트연산자를 다루기 위한 문제이다. 까다로운 시간 제한 조건 때문에 풀어내고도 애를 먹었다. 시간 제한 조건을 맞추기 위해서 게시할 코드는 이 곳 을 상당부분 참고하였다. 1. cin, cout --> scanf, printf --> gets, puts c++ 을 사용하면서 cin, cout 에 어느덧 익숙해졌지만, 이런 시간제한이 까다로운 문제에서는, 더군다나 반복된 입출력이 빈번히 등장한다면 cin, cout 은 상당한 시간을 잡아먹는다. 그래서 scanf, print 로 바꾸었으나.. 그마저도 문제가 되어 puts 로 바꾸었다. printf 의 자료형에 맞게 파싱해주는 내부 구현이 상당한 시간을 잡아먹을 수 있다. 2. 함수의 호출 strcmp 함수를 초기에 호출하여 에러 핸들링 하려 했..
-
백준 알고리즘, 11720 문제Algorithms/ACM_ICPC 2018. 7. 13. 12:27
이 문제 는 숫자의 합을 구하는 문제다. 입력 조건은 다음과 같다. 1. 숫자의 자리수를 입력한다. 2. 해당 자리수의 수를 입력한다. unsigned int 자료형의 최대 범위인 -2,147,483,648 ~ 2,147,483,647 을 넘는 범위까지 수용하기 위해서 char 형으로 데이터를 받은 후, int 형으로 캐스팅 해주려고 했다. /** * @site: https://www.acmicpc.net/problem/11720 * @auth: Landon Park * @github: https://github.com/7772 * @date: 2018. 07. 12 */ #include #include #include using namespace std; // Bad code int main() { i..