본문 바로가기
728x90

전체 글

[백준알고리즘] 2339번: 석판 자르기-C++ 2339번: 석판 자르기 (acmicpc.net) 2339번: 석판 자르기 첫 번째 줄에는 석판의 크기 N(1 ≤ N ≤ 20)이 들어온다. 다음 줄부터 N줄에 걸쳐서 석판의 상태가 입력으로 들어온다. 여기서 1은 불순물을 의미하며, 2는 보석 결정체, 0은 불순물과 보석결정체가 www.acmicpc.net 이번 문제도 분할 정복 방식이다. 사실 문제를 처음 보자마자 아이디어는 떠올랐다. 그런데, 분할할 때마다 조건을 검사하는 과정에서 조각난 석판을 반복해서 검사하는 게 시간이 많이 소요될 것 같았다. 그래서 어떤 방식으로 처리를 해야 할지 고민하느라 시간을 많이 소요했다. 그래서 시간을 많이 소요하지 않게 하기 위한 방법을 고민하다 보니 메모리가 걸렸다. 결국에는 일일이 조건을 검사해도 시간이 여유로운.. 더보기
[백준알고리즘] 14601번: 샤워실 바닥 깔기 (Large)-C++ 14601번: 샤워실 바닥 깔기 (Large) (acmicpc.net) 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 분할 정복을 사용해야 하는 문제인 것은 감이 왔는데, 어떻게 분할 정복을 적용할지가 고민이었다. 그래서 생각보다 시간이 꽤 소요됐다. 처음에 생각했던 방식은 큰 'ㄱ'자 모양들로 분할해 나가는 것이다. 그런데 이건 큰 'ㄱ'자 모양 안에 작은 'ㄱ'자 타일들로 배치하는 게 생각보다 귀찮은 문제로 다가왔다. 다음으로 생각한 것은 큰 정사각형 .. 더보기
[백준알고리즘] 2263번: 트리의 순회-C++ 2263번: 트리의 순회 (acmicpc.net) 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 정답률과 골드 문제여서 쉽게 봤다가 시간을 많이 잡아먹었다. 그런데 접근법 자체 때문인 건 아니고, 메모리 초과가 발생했어서 코드를 약간 수정하는 게 너무 귀찮아서 오래 걸렸다. list를 여러번 생성하면서 재귀적으로 문제를 풀었는데, 10만 개가 한 줄로 이어진 경우에는 스택이 모자란 것으로 보인다. 그래서 list를 매번 생성해서 넘겨주는 것이 아닌, 인덱스로 접근하는 방법을 선택했다. 그러다 보니, list를 vector로 변경해주었.. 더보기
[IT/리뷰] 글로벌 소프트웨어를 꿈꾸다 글로벌 소프트웨어를 꿈꾸다 : 네이버 도서 (naver.com) 글로벌 소프트웨어를 꿈꾸다 : 네이버 도서 네이버 도서 상세정보를 제공합니다. search.shopping.naver.com 2010년에 초판 발행된 책이라, 현재 국내 IT 회사들과 상황이 꽤 다를 것이라 생각된다. 그래도, 실리콘밸리에 있던 회사들의 모습을 훔쳐볼 수 있지 않을까 해서 이 책을 골랐다. 책에서는 저자가 실리콘밸리에서 일할 때 본 회사들의 모습과 국내로 와서 국내 기업들을 컨설팅하면서 본 모습들을 통해 어떤 점들이 달랐는지 설명해주고 있다. 물론 국내 기업들의 잘못된 모습들을 지적하며, 글로벌 기업들과 다른 한국 시장의 특징과 고쳐나가야 하는 것들에 대해 얘기한다. 아래에 책을 읽은 뒤 정리한 내용들을 작성했지만, 요약하자.. 더보기
[백준알고리즘] 6549번: 히스토그램에서 가장 큰 직사각형-C++ 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 보니까 2년 전에 풀다가 말았던 문제인 것 같다. 파이썬으로 풀려고 시도했던 흔적이 남아있다. 플레티넘 5라고 해서 너무 쉬운 방법은 안 풀릴 거 같았다. 조금 생각해서 스택을 이용해 푸는 방법을 생각했고, 약간 지저분해 보여 조금 아이디어를 가다듬고 문제를 풀었다. 사실 바로 풀릴지 모르고 했는데 돼서 놀랬다. 해당 문제에 대한 게시판.. 더보기
[디자인패턴][구조패턴] 플라이웨이트 Flyweight - C++ [모던 C++ 디자인 패턴] 책을 바탕으로 공부하는 내용을 정리한 내용이다. Flyweight pattern 플라이웨이트 패턴은 많은 수의 가벼운 임시 객체를 스마트 참조로 사용하는 것을 말하며 그러한 객체들을 플라이웨이트라고 부른다. 종종 토큰, 쿠키라고 부르기도 한다. 플라이웨이트 패턴은 많은 수의 매우 비슷한 객체들이 사용되어야 할 때 메모리 사용량을 절감하는 방법으로서 자주 사용된다. 사용자 이름 대규모 멀티 플레이가 지원되는 온라인 게임을 생각해보자. 중복 이름이 허용된다면, 흔한 이름이 생성될 때마다 중복되는 공간을 낭비하게 된다. 대신에 이름을 한 번만 저장하고 같은 이름을 가진 사용자들은 그 이름을 포인터로 갖게 할 수도 있다. 이것은 적지 않은 메모리 절감이다. 더 나아가 이름을 "성"과.. 더보기
[디자인패턴][구조패턴] 퍼싸드 Facade - C++ [모던 C++ 디자인 패턴] 책을 바탕으로 공부하는 내용을 정리한 내용이다. Facade pattern 퍼싸드(퍼사드)는 프랑스어로 출입구가 있는 건물의 앞부분을 말한다. 이번 패턴은 특이하게 터미널에 대한 이야기를 통해 설명을 진행한다. 먼저 운영 체제에서 제공하는 터미널/콘솔의 CLI와 금융권의 금융 데이터 문자 렌더링은 미묘한 차이가 있따. 터미널은 어떻게 동작할까? 터미널 윈도의 첫 번째 구성 요소는 버퍼다. 버퍼에 렌더링할 문자들이 저장된다. 버퍼는 보통 char/wchar_t 타입의 1차원 또는 2차원 배열로 만들어진다. 버퍼는 보통 현재의 입력 라인을 가리키는 어떤 표시를 갖는다. 그 표시를 이용해 버퍼가 가득 찼을 때, 항상 새로운 라인을 할당하는 것이 아니라 가장 오래된 라인부터 덮어쓰면.. 더보기
[백준알고리즘] 11444번: 피보나치 수 6 -C++ [백준알고리즘] 11444번: 피보나치 수 6 -C++ 11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 골드 난이도면서 정답 비율이 높길래 되게 쉬운 문제인 줄 알았다. 근데 난생처음 보는 풀이를 보고 따라 풀었다. 이 문제를 푸는 방법은 2가지가 있다고 한다. 행렬 곱을 이용한 방법과 방정식을 이용한 방법이다. 아래는 방정식으로 문제를 풀었다. 문제를 푸는 방식은 백준 블로그의 글을 참고했다. 피보나치 수를 구하는 여러가지 방법 (acmicpc.net) 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니.. 더보기
728x90

티스토리툴바