본문 바로가기

알고리즘 문제풀이

(66)

[삼성 기출 문제] 백준 5373 큐빙 문제 링크 어떻게 풀까? 진정한 시뮬레이션입니다.정말... 말 그대로 3x3x3 큐브의 U D F B L R을 시계방향과 반시계방향으로 돌리는 것을 구현하면 됩니다! -끝- 이라고 하기엔 너무 힘들고 가혹한 시뮬레이션 입니다.사람에 따라서는 코드 길이도 200~300줄까지 될겁니다. if문과 else문으로 떡칠이 되어있기 때문이죠! 아는 분의 협조를 구해서 가져온 코드의 일부분 입니다! 123456789101112131415161718192021222324252627282930313233343536 if (s == "U+") { Up_cw(a); } else if (s == "U-") { Up_cw(a); Up_cw(a); Up_cw(a); } else if (s == "D+") { Down_cw(a);..

[삼성 기출 문제] 백준 16235 나무 재테크 문제 링크 어떻게 풀까? 최적화를 조금 많이하다보니 문제를 살짝 극혐으로 풀었습니다. 저는 DP, 슬라이딩 윈도도 함께 사용했습니다.만약 슬라이딩 윈도를 잘 모르신다면 여기를 참고하세요 슬라이딩 윈도를 쓰는 이유! 이 문제를 잘 보시면 이전 년도의 나무들에 대한 정보는 전혀 필요가 없습니다.따라서, 현재 년도와 다음 년도에 쓰일 공간만 필요한 것 입니다. 그림에서 보듯이 이전 년도의 나무 개수 자료는 전혀 쓰지 않습니다. 따라서 위처럼, 현재 나무들의 정보를 토대로 다음 년도의 나무를 저장하기 위해선 딱 2개의 정보 배열이 필요합니다. 2개의 나무 배열을 가지고 있다고 하면, y년 이라고 했을때, [y%2^1] 나무 배열을 현재 배열로, [y%2] 배열을 내년 배열로 쓰면 됩니닷! 그리고! 나무들의 정보..

[삼성 기출 문제] 백준 16234 인구 이동 문제 링크 어떻게 풀까? 굉장히 전형적인 bfs 문제입니다. 이 문제를 해결하기 위해서는 크게 세 가지의 생각이 필요합니다. 1. 인구 차이가 L명 이상, R명 미만인 인접한 국가를 묶어서 연합으로 만드는 방법2. 연합이 된 국가의 인구수를 바꾸는 방법3. 연합이 되는 국가가 없어서 수행을 종료하는 방법 일단 1, 2방법을 한 번에 묶을 수 있는 방법이 있습니다.바로 B.F.S입니다. 연합된 국가를 찾으려고 할 때마다, 2차원 배열을 모두 돌면서 인구차이가 L명 이상, R명 이하가 나는 국가를 모두 연합해서 큐에 넣습니다.그리고 큐에 들어갈때 마다 해당 국가의 인구수를 모두 더합니다. 이제 마지막에 모든 국가의 인구수와 큐에 들어있는 국가의 수를 나누면 균등하게 나눠진 인구 값이 나옵니다. 이제, 큐에서..

[삼성 기출 문제] 백준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 ..

[삼성 기출 문제] 백준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번쨰 설치된 가로줄을..

[삼성 기출 문제] 백준 14891 톱니바퀴 문제 링크 어떻게 풀까? 전형적인 시뮬레이션 문제입니다. 문제의 내용을 그대로 구현해야합니다! 먼저 생각해보아야 할 것은 톱니바퀴의 극을 어떻게 설정할 것인가? 입니다. 톱니바퀴는 N극과 S극의 2 가지 상태로 나타낼 수 있습니다.그리고 톱니가 8개이기 때문에, 비트로 나타내면 편하게 관리할 수 있을 것 같습니다! 시계 방향과 반시계 방향도 비트 연산자 하나만으로 해결 될 수 있죠! 123456789101112131415161718192021222324252627282930313233struct TOP { int topni; bool getUP() { return topni & 1; } bool getRIGHT() { return topni & (1

[삼성 기출 문제] 백준 14889 스타트와 링크 문제 링크 클릭시 이동합니다. 어떻게 풀까? 를 구하는 문제입니다. n 개의 데이터를 스타트 팀, 링크 팀에 넣은 뒤에 두 팀의 능력치를 계산해서 두 능력치의 차이 중 최소의 값을 출력합시다! 참고로, 능력치는 입력에 주어지는 것 처럼 2차원 배열에 저장하실 겁니다!팀의 능력치를 구할 때, i, j가 같은 팀이면 능력치를 (i,j)와 (j,i)의 합으로 구할 수 있습니다!즉, 1번 사람과 2번 사람이 팀이라면, (1,2)와 (2,1)를 더해서 구하면 됩니다! 2차원 for문을 이용하면 1번 사람과 2번 사람의 경우와 2번 사람과 1번 사람의 경우 두 개를 중복으로 확인할 것입니다.이를 피하기 위해서 j는 i+1번 번호 부터 확인하도록 합시다! 저는 비트조합을 이용해서 조합을 구했는데, 이를 확인하시려면 ..

이전 1 2 3 4 ··· 9 다음

티스토리툴바