풀이 이 문제 역시 삼성 SW 역량테스트 기출문제 였다. DFS 백트래킹에 관한 간단한 문제였는데, 백트래킹이란, 모든 경우의 수를 모두 고려하는 알고리즘으로써,위 주어진 문제와 같이 팀을 나눌 수 있는 모든 경우의 수를 고려하는 데에 적합하다. 우선 DFS함수를 0~n/2 - 1 에 해당하는 Vertex에서 실행한다. 절반만 돌리는 이유는 순열이 아니라 조합을 구하는 문제이기 때문에 어차피 한 팀을 구하면 나머지 팀이 자동으로 결정되기 때문에 시간낭비를 막기 위한 처리였다. 예를 들어0에서 시작한 DFS는 우선 점을 하나 방문했으므로 isVisit[0] = true로 바꿔주고 방문한 점의 개수를 나타내는 len의 길이를 1 증가시켜 준다.len == n/2인 경우 하나의 조가 짜여진 경우이므로 팀을 나..

풀이 삼성 SW 역량 테스트 기출문제로, DFS의 간단한 응용 능력을 물어보는 문제였던 것 같다. DFS를 수행하는 방법이야 재귀를 이용해서 처리하면 되지만, 이 문제의 경우에는 DFS를 실행하는 순서를 처리하는 방식이 살짝 까다로운 부분이 있었다. 우선, 문제에서 제시한 방향에 따라 direction변수를 설정해 주었다. 0 - North1 - East2 - South3 - West 그리고 LeftRotate의 경우 direction변수가 들어왔을 때 그 방향의 왼쪽으로 회전한 방향을 출력하도록 처리하였다.예를 들어, 0이 들어오면 북쪽의 좌회전 방향인 서쪽을 가리키는 3을 출력하는 식이다. 그리고 dx[], dy[] 배열을 선언하고, 제시한 방향에 맞게 x, y를 변화시키는 값을 저장하였다.예를 들어..

풀이 최소 힙(MIn Heap)을 직접 구현하는 문제였다.Heap은 연결 리스트로 구현하는 것 보다는 배열(Array)을 이용해서 구하는 것이 정신건강에도 좋고 구현하기 편리하다. 배열로 힙을 구현하면, 물론 데이터의 수를 알 수 없는 경우에는 저장 공간의 낭비가 생길 수 있겠지만그 경우에도 추가적인 메소드 구현을 통해 공간을 줄여주거나 공간을 늘려주면 되므로 큰 무리는 없다.가장 좋은 점은 Left Child, Right Child, Parent의 데이터를 index만으로 접근할 수 있다는 점이다. index 0부터 시작하는 경우에는Left Child = i*2+1Right Child = i*2+2Parent = (i-1)/2로 접근할 수 있다. 소스 코드 1234567891011121314151617..

풀이 설마 이렇게 벽을 3개 세울 수 있는 모든 경우의 수를 다 확인해 봐야하는 건가? 라고 생각하면서 문제를 풀었던 것 같다. 하나의 벽을 세우기 위해서 행과 열을 세는 n*m반복문을 세워야하고 벽을 3개 세워야 하므로벽을 세우는 데만 반복문을 6개를 사용했고, 또 DFS를 위해 반복문을 두개 또 집어넣어야 해서결과적으로는 반복문을 8개나 집어넣는 어마무시한 일이 발생해버렸다. 하지만 애초에 n

풀이 깔끔한 수학 구현 문제였다. 입력케이스의 개수가 홀수 개여서 복잡하게 머리를 굴리지 않아도 된다. 문제를 해결하는 기본 원리는 다음과 같다.입력으로 들어오는 모든 숫자들을 더한다음 2로 나누면, 1~N까지의 학생들이 가지고 있는모든 사탕의 수가 나오게 된다.(왜냐하면 모든 수를 다 두 번씩 더하기 때문 1+2 2+3 3+1) 거기에 지금 구하고자 하는 학생을 제외한 나머지 학생들의 사탕의 개수들의 합을 빼주면지금 구하고자 하는 학생의 사탕의 개수가 나오게 된다. 1 = (1+2+3) - (2+3)2 = (1+2+3) - (3+1)3 = (1+2+3) - (1+2) 이 식을 N에 대해 일반화하면 금방 정답을 구할 수 있다. 소스 코드 1234567891011121314151617181920212223..

풀이 처음에 문제를 접근 할 때에는 그냥 반복문을 n번정도 돌리면서 곱하고, 그 값이 c보다 커지면 한번씩 나누어 나머지를 구해주고 이렇게 계산을 반복하면 되는 것 아닌가? 하고 생각했다. 이렇게 생각하면 굉장히 단순하고 구현또한 어렵지 않았기 때문에 왜 정답률이 30%가 채 안되는지 이해할 수 가 없었지만..Online Judge에 코드를 넣고 돌려본 뒤에 시간초과가 뜨는 걸 확인하고아 O(n)으로 풀면 안되는 문제였구나 라는 생각이 들었다. 정수의 거듭제곱을 구하는 알고리즘은 여러가지가 있다.그 중 가장 단순하고 구현하기 쉬운 알고리즘은 물론 a를 b번 반복하면서 곱해주는 것이지만시간복잡도가 O(n)으로 비교적 오래 걸리는 알고리즘이다. 그래서 나온 것이 바로 Divide & Conquer 방법을 사..