본문 바로가기

반응형

전체 글

(171)
[삼성 기출 문제] 백준15686 치킨 배달 문제 링크 어떻게 풀까? 해당 문제는 전형적인 조합 문제입니다.생각해봐야할 과제는 다음과 같습니다. 1. 맵에서 치킨집의 개수를 추출한 후에 비트 조합을 이용해서 m개의 치킨집만을 고른다.2. 사람들이 사는 모든 집에서 현재 선택된 m개의 치킨 집 중에서 최소의 치킨집을 구한 후 더한다. (도시의 치킨 거리를 구한다.)3. 최소의 도시의 치킨 거리 값을 출력한다. 만약, 비트 조합을 만드실줄 모른다면 여기를 참조하세요! 1234567891011121314151617181920212223242526272829typedef struct Cod{ int r,c; } cod; int cNum, pNum;cod company[13];cod people[100]; int getAllDist(){ int visit ..
[알고리즘 깨알 팁] 비트로 연산하는 방법 비트로 연산하는 방법! 많은 사람들이 비트로 연산하는 것에 대한 두려움과 거부감을 가지고 있는 것 같습니다.하지만, 비트연산이란 알고보면 별 것 없습니다! 우선, 비트연산을 하기 위해서 알아야할 5가지의 연산 방법을 알아봅시다. 1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. ex) 0b 1111 & 0b 0011 = 0b 0011 2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.ex) 0b 1100 | 0b 1010 = 0b 1110 3. ~ : 모든 비트를 1이면 0으로 0이면 1로 반전합니다.ex ) ~0b 1100 = 0b 0011 4. >> : 1 비트 오른쪽..
[삼성 기출 문제] 백준15685 드래곤 커브 문제 링크 어떻게 풀까? 이 문제에서 문제를 풀기위해 생각해봐야 할 것이 2 가지 있습니다. 1. 세대가 올라갈때 선을 어떻게 연결할 것인가?2. 네 꼭짓점이 드래곤 커브의 일부인 것은 어떻게 찾을 것인가? 1번부터 시작하겠습니다. 우선, 예제를 하나 보시죠! (0,0)에서 3 세대인 그래프입니다. 일단, 선의 총 길이를 보겠습니다.선의 길이는 이전 세대의 길이만큼 +됩니다!n-1 세대 길이가 x 였다면, n세대의 선분 길이는 총 2*x가 되는 것이죠!즉, 2의 제곱승으로 길이가 늘어납니다.문제에서 최대 세대가 10세대까지이므로, 길이는 총 1024까지 될 것 입니다! 그럼 가장 중요한 점!과연, n-1세대에서 n세대로 갈 때 어떻게 그려야 하는가? 입니다. 저 위의 그림에서 한 번 어떻게 그려야하는지 ..
[삼성 기출 문제] 백준15684 사다리 조작 문제 링크 어떻게 풀까? 이 문제는 사다리위에 다리가 있다는 것을 어떻게 표시할지를 생각해야합니다.그리고, 최대 3개의 놓을 수 있는 사다리를 어디에 놓을지, 사다리를 놓은 다음에 해당 사다리 정보가 문제의 조건에 맞는지를 생각해보아야 합니다.그리고 사다리의 가로줄을 만나면 어떻게 처리할지도 생각해야 하죠!문제의 조건에 맞는 사다리란, 사다리가 1,2,3,4,5, ... N으로 출발해서, 도착 했을때에도 1,2,3,4,5, ... N 이어야 하죠! 그럼 우선, 사다리에 대한 정보를 어떻게 표시할지에 대해서 생각해봅시다. 사다리입니다! 가로줄과 세로줄이있죠.그림을 보면, 세로줄과 가로줄을 행과 열에 따라서 2차원 배열로 나타내면 아주 좋을 것이라는 것을 깨달을 수 있습니다!높이 x의 y번쨰 설치된 가로줄을..
[알고리즘 깨알팁] 재귀로 1, 2차원 구간 처리하기 가끔가다 for문만으로는 문제를 처리하기 힘든 경우가 있습니다. 대표적인 경우가 2차원 배열에 대한 순열을 만들어야 하는 경우이죠. 자, 이럴때 여러분은 어떻게 해결하십니까!? 음.. 다른 분들도 편하게 느끼실진 모르겠지만, 제가 사용하는 방법을 알려드리려고 합니다! 우선, 일차원 배열에서 재귀 함수를 어떻게 작성하는지 생각해봅시다. 이렇게, 4개의 배열이 있으면, 위와 같이 0번 인덱스를 처리 후 1번 인덱스, 2번 인덱스, ... 마지막인덱스를 확인한 후에기저사례로 모두 검색한 다음 이전 인덱스로 돌아갑니다! 즉, 현재 인덱스를 처리한 후 다음 인덱스를 처리한다.마지막 인덱스까지 다 봤으면 return한다. 이 처리입니다! 1차원 배열에서는 다음 인덱스는 그냥 현재 인덱스 + 1 입니다. 코드로 나타..
[삼성 기출 문제] 백준 15683 감시 문제 링크 어떻게 풀까? 이 문제는 여러 개의 카메라를 돌려서 카메라의 영역에 들어오지 않는 부분(사각 지대)을 찾는 문제입니다.시뮬레이션이면서 완전 탐색의 성격을 모두 갖추고있죠! 카메라를 돌리는 것에서 다양한 방법이 있을 수 있습니다.문제를 풀기전에 1. 카메라를 어떻게 돌릴지, 2. 카메라가 비추는 영역을 어떻게 표시할지 에 대해서 생각해 봅시다. 첫 번째로, 카메라를 어떻게 돌릴까? 입니다. 보시면, 카메라는 총 5가지 종류가 있습니다.1번 카메라는 90도씩 돌린다고 하면 총 4개의 다른 부분을 보는 영역을 만들 수 있겠죠! 이렇게 4개의 방향을 만들 수 있죠!이와 비슷하게 2번은 2개, 3번은 4개, 4번도 4개, 5번은 1개의 서로 다른 방향을 만들 수 있습니다. (csize)또한, 화살표의 ..
[삼성 기출 문제] 백준 14891 톱니바퀴 문제 링크 어떻게 풀까? 전형적인 시뮬레이션 문제입니다. 문제의 내용을 그대로 구현해야합니다! 먼저 생각해보아야 할 것은 톱니바퀴의 극을 어떻게 설정할 것인가? 입니다. 톱니바퀴는 N극과 S극의 2 가지 상태로 나타낼 수 있습니다.그리고 톱니가 8개이기 때문에, 비트로 나타내면 편하게 관리할 수 있을 것 같습니다! 시계 방향과 반시계 방향도 비트 연산자 하나만으로 해결 될 수 있죠! 123456789101112131415161718192021222324252627282930313233struct TOP { int topni; bool getUP() { return topni & 1; } bool getRIGHT() { return topni & (1
[삼성 기출 문제] 백준 14890 경사로 문제 링크 어떻게 풀까? 이 문제의 핵심은 '경사로를 어떻게 놓으면 될까?'에 대한 결정을 하는 것입니다. 문제에경사로의 가로 길이가 2라고 하겠습니다. 땅의 상황은 위와 같다고 하겠습니다. 아래와 같은 경우는 경사로가 설치된 곳에 중복으로 경사로를 설치했기 때문에 나타나는 문제입니다! 이 문제를 해결하기 가장 좋은 방법은 해당 좌표에 이미 경사로가 설치되었는지를 나타내는 bool 배열을 이용하는 것입니다. 해당 지점에 최초로 경사로를 만들면, 해당 자리를 true로 만듭니다. 다음에 또다시 해당 지점에 경사로를 만들려고 한다면, 경사로를 만들 수 없는 것입니다! 위의 그림을 봅시다. 위의 그림은 경사로가 지어지는 도중에 겹쳐지는 곳이 있어서 결국 경사로를 짓지 못한다는 처리를 해줘야합니다. 하지만, 경..

반응형