Disclaimer
채용 진행과정에서 작성한 기밀유지서약서가 있기 때문에 채용 프로세스 및 정보(SW테스트 제약사항, 기출문제 등)는 이미 인터넷에 공개적으로 알려진 사항에 대해서만 정리하여 작성한 것이며, 기밀유지 하기로 한 부분에 대해서 위배한 사항은 없습니다.
SW Test에 대한 안내사항은 Codeground 공식 사이트에 안내된 부분을 다시 정리한 것일 뿐이며, 기출문제는 유출하지 않습니다.
타 사이트(백준저지 등)에 올라온 문제를 기반으로 저의 해설을 추가했을 뿐, 참가했던 SW테스트와는 무관합니다.
그래도 만약 문제가 되는 부분이 있을 경우 통보해주시면 해당 내용은 삭제조치하도록 하겠습니다.
또한, 본 가이드는 알고리즘 학습에 도움을 주기 위함일 뿐이며, 미래 정확성은 책임지지 않습니다.
본 가이드 내 정보를 참고한 모든 결과에 대한 책임은 독자에게 있습니다.
1. 개요
삼성전자에서는 2016년쯤부터 S직군(소프트웨어) 신입사원 및 인턴사원 공채 전형에서 SW 테스트를 실시하고 있습니다. 서류전형 -> SW테스트 (GSAT/SSAT 면제) -> 최종면접(인성, 직무, 창의)으로 진행됩니다.
이 때 보는 SW테스트가 바로 SW Test A형입니다.
기존에는 사내 직원들에게만 실시하던 테스트를 삼성전자가 얼마 전 코드그라운드를 통해 일반 대학생/졸업생에게 오픈하였습니다.
링크 : https://www.codeground.org/sst/common/userTestList (링크는 로그인했을 때 접근 가능합니다. 로그인시에만 메인페이지 상단에 SW TEST 탭이 새로 생성됩니다.)
<Edit : 이제는 접수 페이지가 바뀌어서 https://www.swexpertacademy.com/main/main.do 사이트에서 신청받는다고 합니다.>
A, B, C형은 각각 스타일 및 난이도가 매우 다르므로 가이드 또한 각각에 대해 파트를 나누어 쓰도록 하겠습니다(C형은 거의 알려진 바가 없으므로 생략합니다).
일단 취업에 필요한 건 A형 딱 하나이므로 A형을 먼저 보도록 하죠.
참고로 B/C형은 취득시 인사평가/배치시 우대사항이 있는 것으로 공지되어 있습니다.
2. A형 대비방법
먼저, 삼성에서 공개적으로 밝힌 안내사항입니다.
위와 같이 A형은 3시간이 주어지며 두 문제를 풀어야 합니다. 언어는 C/C++/JAVA이며 라이브러리 제한은 없습니다. C++ STL 사용 가능하고, C++ 11 및 14까지도 지원됩니다. auto, 람다 등 모두 사용 가능합니다. 다만 문제 수준이 11/14를 요구할만한 난이도가 아닙니다. 어차피 간단한 알고리즘 문제에서 C++ 11 이상의 신규기능을 써야 할 일이 많이 없습니다.
A형은 보통 기본적인 알고리즘으로 풀 수 있는 경우가 많습니다. 각종 Sorting 알고리즘이나 자료구조(linked list, queue, stack, heap...) 등을 손수 구현해야 하는 문제도 나오지 않는 편이며, 어차피 라이브러리가 사용 가능하므로 std::priority_queue 쓰면 그만입니다.
개인적으로 여러번 시험을 보고 모두 통과했지만, 대기업 알고리즘 시험에서 algorithm과 std::vector 말고 필요한 건 없었습니다.
(예외 : 카카오 17년도 블라인드 공채의 경우 1차 코딩은 algorithm/vector만 필요했으나 2차 코딩은 REST API 사용을 위한 웹 request 라이브러리 및 json parser가 필요했고, 3차 오프라인 코딩은 python의 list comprehension 및 string manipulation이 매우 유용했습니다. 3차 오프라인 코딩의 경우 C++의 string 라이브러리로는 시간 내 구현이 불가능하다고 느꼈습니다.)
대비를 위해서는 일단 다음의 순서를 추천합니다. 시간이 없으면 윗부분부터 차례대로 포기하세요.
- 만들고 싶은 거 아무거나 생각해서, 과제가 아니라 진짜 하고 싶어서 만드는 거 해보기(과제 삽질은 기억에 잘 안 남아요. 본인이 능동적으로 만드는 프로젝트 삽질이 기억에 남지..). Python이나 웹(html/javascript)으로 하는 걸 추천합니다.
- 알고리즘 책 하나 골라서 자료구조/알고리즘 제대로 한번 보기
- 깔끔하고 정상적인 문제들 알고스팟이나 백준저지같은 사이트에서 풀어보기 (테스트케이스, 문제구조 등이 함정 없이 깔끔합니다)
- 공식 삼전 연습사이트 https://www.codeground.org/ 가셔서 악랄한 문제 체험해보기
- "기출문제"(예시링크) 구해서 풀어보기 (본 링크는 해당 사이트 운영자가 임의로 소문에 유사하게 재구성한 문제이며, 유출된 기출문제가 아닙니다.)
3. 문제풀이 예시
주의 : 만약 아주 기초적인 코딩도 모르는 상태에서 싸트 공부하듯 벼락치기하려는 의도라면, 다른 직군을 알아보거나 기본기를 닦은 다음 도전하는 것을 권해드립니다.
본 글은 기초 소양이 있지만 알고리즘 시험에 익숙하지 않거나 삼전 알고리즘 시험 특유의 어려운 포인트를 확인하고 싶은 분들을 대상으로 작성되었습니다.
3-1. Prerequisites (기본 요구사항)
SW테스트 해설을 읽기에 앞서, 다음 문제들을 보고 답을 바로 생각해낼 수 있는지, 혹은 C/파이썬/자바 등 본인이 가장 편한 언어로 20~30분 안에 구현할 수 있을지 생각해보세요.
그렇지 않다면 자료구조 등 전공과목 복습 및 백준 단계별 학습에서 16단계까지는 적어도 단계별 한문제씩 완료하고 오는 것을 추천드립니다.
- 본인이 사용하는 언어에서, 함수에 정수형 변수를 pass by value가 아닌 pass by reference의 방식으로 전달하여 실제 값을 조작할 수 있는 방법을 말해보세요.
- 삽입정렬의 시간 복잡도는 어떻게 되나요?
- 1억번의 비교적 단순한 연산을 해야 하는 알고리즘을 재귀함수로 구현했을 때 어떻게 될까요? for문으로 구현했을 때는 어떻게 될까요? (프로그램이 정상 동작할까요? 몇초나 걸릴까요?)
- 100x100(nxn) 오목판에 현재 돌 배치가 주어졌을 때, O(n^2) 수준으로 승리조건을 어떻게 확인할까요?
- 정수 N을 받습니다. 해당 숫자가 3으로는 나눠 떨어지나 5로는 떨어지지 않으면 "Fizz", 반대로 5로 나눠지고 3이 안 떨어지면 "Buzz", 3과 5 둘 모두로 나눠 떨어지면 "Fizz Buzz"를 출력하세요.
- 정수 N을 받습니다. 해당 숫자가 소수인지 아닌지 O(N^(1/2)) 혹은 그 이하로 확인하세요.
*답은 아래에 있습니다.
3-2. 톱니바퀴 문제
문제 조건은 링크(https://www.acmicpc.net/problem/14891) 참조바랍니다.
일단, 톱니바퀴 개수는 4개 / 톱니 개수는 8개로 고정되어 있으니 main함수 작성은 쉽습니다. 쿨하게 배열을 만들어버립시다.
다만... 인풋이 좀 당황스럽죠? 10101111과 같은 식으로 들어오는데, 타 언어에 비해 C/C++에서는 이걸 변환하는게 약간 골치가 아픕니다.
atoi나 stringstream을 쓰면 되기는 합니다만, 저는 개인적으로 정신없는 알고리즘 시험장에서는 가능하면 디버깅할 확률이 적은 방법을 선호합니다. (특히 문자열 관련해서는 주소/값 전달 때문에 골치아파질 일이 가끔 있습니다. cstring형을 받아서 주소를 줘야 하는데 내가 주고 싶은 건 3번째 인덱스 문자 하나라서 에러가 터진다든가 등...) 아스키코드 값 이용해서 그냥 char를 int로 바꿔버린다음 offset을 더하거나 빼는 방법도 있습니다만, 이 역시 정신없는 시험장에서는 코드값 다시 확인해야 하는 등 별로 좋지 않을 수 있습니다.
그래서 이 문제에서 전 string으로 다 받아버릴 겁니다.
vector<string> gears(COUNT);
for (auto it = gears.begin(); it != gears.end(); ++it) {
cin >> (*it);
}
그리고, K 회전 수를 받은 뒤 K번 입력이 주어진다고 하므로 입력을 받아줍니다.
int K;
cin >> K;
for (int i = 0; i < K; ++i) {
// ...?
}
잠깐, 여기서 멈추고 생각을 해봅시다. K번 입력이 주어지는데, 돌릴 톱니바퀴와 돌릴 방향이 띄어쓰기가 된 두 정수로 들어옵니다. 그러면 이걸 어떻게 저장하는게 좋을까요?
아래처럼 두 배열을 만들어서 저장하나요?
vector<int> sel(K);
vector<int> dir(K);
아니면, "깔끔하게" class나 struct를 만들어서 저장하나요?
Class Command {
public:
int sel;
int dir;
};
//main
vector<Command> commands(K, Command());
제 의견이지만, 모두 오답입니다. 알고리즘 시험 때는 시간이 생명이고, 이런 건 모두 시간 낭비일 뿐입니다.
문제를 잘 읽어보면 해당 명령을 수행만 하면 될 뿐 반드시 입력이 끝난다음에 실행할 필요가 전혀 없습니다.
그러므로 그냥 K번 입력받는 루프 안에서 그대로 시뮬레이션 함수 돌리면 됩니다.
int K;
cin >> K;
for (int i = 0; i < K; ++i) {
int sel, dir;
cin >> sel >> dir;
Simulate(args);
}
그런데 아직 하나 주의할 점이 있습니다. 톱니 선택이 1부터 4로 주어집니다. 즉, 그대로 함수에 넘겨버리면 index out of range가 뜨게 됩니다. 악랄한 입력값을 정화시켜줍시다.
int K;
cin >> K;
for (int i = 0; i < K; ++i) {
int sel, dir;
cin >> sel >> dir;
--sel; // sel이 1부터 시작하므로 0부터 시작하게 normalize
Simulate(args);
}
자, 그럼 이제 입력 처리는 모두 끝났습니다. 본 게임을 시작해봅시다.
톱니바퀴가 돌아가야 한다는데, 이걸 어떻게 해야 할까요? 알고리즘 문제 삽질을 좀 해보면서 야매스킬이 생긴 분들은 바로 생각나는게 있겠지만, 정석대로 전공과목만 착실하게 하신 분들은 어쩌면 이렇게 생각할지도 모릅니다 :
" 아, 이거 자료구조/알고리즘 수업 때 배웠어! 환형 링크드 리스트로 구현해야 돼! "
네..... 당연히, 그렇게 만들면 한 문제 풀고 3시간 다 끝납니다.
어차피 우리가 알고싶은 건 상대적인 변화일 뿐입니다.
그렇다면, 'top' 배열을 만들어서 그냥 {0,0,0,0}으로 초기화해놓고 첫째 톱니바퀴가 시계방향으로 움직이면 7로 바꾸고, 반시계방향으로 움직이면 1로 바꾸면 되겠지요? 결국 프로그래머인 우리가 저 top의 의미만 인지하고 있으면 톱니간 상호작용 때도 적절히 offset 줘서 계산하고, 나중에 총 점수 계산할 때도 gears[top]만 확인해서 계산하면 됩니다.
0일 때 시계방향이면 -1이 아니라 7로 해주고 7일때 시계방향이면 8이 아니라 0으로 해주는 걸 하드코딩해놓을 순 없으니 %(modular) 연산을 쓰도록 합니다.
int Turn(int current, int dir) {
return ((current + dir) + 8) % 8; // dir를 더한다음 8을 더하고(음수 방지) mod 8을 해주면(8 overflow 방지) 0부터 7까지의 깔끔한 값으로 변함
}
그런데 잠깐 또 스톱!
여기 어김없이 골때리는 함정이 있습니다. 문제 조건을 잘 읽어봅시다.
시계방향일 때 +1이고 반시계방향일 때 -1이랍니다. 하... 대체 왜......
그쵸. Turn 함수를 저렇게 만들면 거꾸로 돌려버립니다. 시계 방향일 땐 -1을 해줘야 하는데 말이죠.
바꿔줍시다.
int Turn(int current, int dir) {
return ((current - dir) + 8) % 8; // dir를 더한다음 8을 더하고(음수 방지) mod 8을 해주면(8 overflow 방지) 0부터 7까지의 깔끔한 값으로 변함
}
돌리는 로직도 만들어놨으니, 이제 Simulate() 함수만 만들어서 돌리게 만들면 끝나겠군요.
Simulate()에서는 먼저 돌릴 바퀴와 방향을 받아서 Turn()을 호출하여 top을 수정해주고, 옆에 있는 바퀴들을 돌릴 수 있다면 옆의 바퀴들도 돌려줘야 합니다.
단, 여기서 주의할 점이 있습니다. 돌릴 바퀴 주변의 바퀴가 돌아갈 수 있는지는 돌린 후가 아니라 돌리기 전의 상황과 비교해야 합니다. 즉, 돌리기 직전에 N/S가 맞아야 옆에 바퀴가 돌 수 있는 것이지, 돌린 후에 맞아봤자 소용이 없습니다.
따라서, top 수정 명령은 defer 처리해야 하며, 다른 톱니를 돌린 후에 적용해줘야 합니다.
이를 효과적으로 구현하는 방법은 여러가지가 있겠지만, 가장 편한 방법은 재귀를 쓰지 않고 그냥 처음 시작할 때 제대로 맞물린 톱니만 찾고 -1/+1을 번갈아가며 양쪽으로 나아가는 것입니다. 만약 Simulate로 톱니 하나만 돌리고 붙어있는 톱니를 돌리기 위해 재귀를 썼다간 난리 납니다. 옆에 Simulate가 다시 돌아와서 부모톱니를 부르고, 또 반복되고....
백문이불여일견이라고, 한번 구현된걸 보죠.
void Simulate(vector<string> &gears, vector<int> &top, int sel, int dir) {
int leftlimit = sel, rightlimit = sel;
// 왼쪽으로 연속해서 맞물린 톱니 탐색
for (int i = sel - 1; i >= 0; --i) {
// 전단계(오른쪽)의 톱니가 현재(왼쪽)의 톱니와 맞물려있는지 -값이 다른지- 확인
if (gears[i + 1][(top[i + 1] - 2 + 8) % 8] != gears[i][(top[i] + 2) % 8]) {
leftlimit = i;
}
else {
break;
}
}
// 오른쪽으로 연속해서 맞물린 톱니 탐색
for (int i = sel + 1; i < COUNT; ++i) {
// 전단계(왼쪽)의 톱니가 현재(오른쪽)의 톱니와 맞물려있는지 -값이 다른지- 확인
if (gears[i - 1][(top[i - 1] + 2) % 8] != gears[i][(top[i] - 2 + 8) % 8]) {
rightlimit = i;
}
else {
break;
}
}
// 자기 자신을 포함해서 왼쪽으로 나아가며 맞물린 바퀴들은 시계/반시계 번갈아가며 적용해줍니다.
int d = dir; // dir를 바꿔버리면 밑부분 오른쪽으로 탐색할 때 본래 방향을 모릅니다.
for (int i = sel; i >= leftlimit; --i) {
top[i] = Turn(top[i], d);
d = -d;
}
// 자기 자신을 제외하고(이미 한번 돌렸으니) 오른쪽으로 나아가며 번갈아가며 바꿔줍니다.
// 주의할 점 : 자기 자신 제외이므로 d를 처음부터 -dir로 설정한 다음 시작해야 합니다.
d = -dir;
for (int i = sel + 1; i <= rightlimit; ++i) {
top[i] = Turn(top[i], d);
d = -d;
}
return;
}
위 코드의 부연설명을 하자면, 윗부분 블록에서는 왼쪽 오른쪽으로 순차탐색을 하며 연속적으로 맞물린 가장 먼 바퀴를 확인합니다. 아랫부분 블록에서는 방금 전 알게 된 정보를 토대로 시계/반시계 번갈아가며 각 바퀴들을 돌려줍니다(연속적으로 맞물린 가장 먼 곳까지만). 참 쉽죠?
사실 실제 시험 때는 이렇게 깔끔하게 못 짭니다. 방금 제가 언급한 "함정"들에 대부분 빠진 상태로 코딩을 하고 테스트케이스 fail해서 디버깅하는 과정에서 확인하는 경우가 많기 때문에 온갖 스파게티 코드 양산 경험을 해볼 수 있습니다.
하지만 이해를 돕기 위해, 그리고 모범적인 답안을 제시해보기 위해 다소 비현실적일 수 있는 형태로 깔끔하게 짜보았습니다.
실제 시험 때 얼마나 헷갈리는 부분이 많을 수 있고, 작은 실수가 전체 구조를 다 짜고 났을 때는 얼마나 고치기 어려운지 미리 한번 경험해보고 잘 대비할 수 있는 데에 도움이 되었으면 합니다.
마지막 간단한 "점수산정" 부분까지 추가하여 완성된 코드는 아래 첨부합니다.
원래 3~4개 예제 풀어서 올리려고 했으나 피곤한 관계로 한개만 하도록 할게요.
미래에 요청이 좀 들어온다면 추가적으로 올리도록 하겠습니다.
#include <iostream>
#include <vector>
#include <string>
#define COUNT 4
#define TEETH 8
using namespace std;
int Turn(int current, int dir) {
return ((current - dir) + 8) % 8; // dir를 더한다음 8을 더하고(음수 방지) mod 8을 해주면(8 overflow 방지) 0부터 7까지의 깔끔한 값으로 변함
}
void Simulate(vector<string> &gears, vector<int> &top, int sel, int dir) {
int leftlimit = sel, rightlimit = sel;
// 왼쪽으로 연속해서 맞물린 톱니 탐색
for (int i = sel - 1; i >= 0; --i) {
// 전단계(오른쪽)의 톱니가 현재(왼쪽)의 톱니와 맞물려있는지 -값이 다른지- 확인
if (gears[i + 1][(top[i + 1] - 2 + 8) % 8] != gears[i][(top[i] + 2) % 8]) {
leftlimit = i;
}
else {
break;
}
}
// 오른쪽으로 연속해서 맞물린 톱니 탐색
for (int i = sel + 1; i < COUNT; ++i) {
// 전단계(왼쪽)의 톱니가 현재(오른쪽)의 톱니와 맞물려있는지 -값이 다른지- 확인
if (gears[i - 1][(top[i - 1] + 2) % 8] != gears[i][(top[i] - 2 + 8) % 8]) {
rightlimit = i;
}
else {
break;
}
}
// 자기 자신을 포함해서 왼쪽으로 나아가며 맞물린 바퀴들은 시계/반시계 번갈아가며 적용해줍니다.
int d = dir; // dir를 바꿔버리면 밑부분 오른쪽으로 탐색할 때 본래 방향을 모릅니다.
for (int i = sel; i >= leftlimit; --i) {
top[i] = Turn(top[i], d);
d = -d;
}
// 자기 자신을 제외하고(이미 한번 돌렸으니) 오른쪽으로 나아가며 번갈아가며 바꿔줍니다.
// 주의할 점 : 자기 자신 제외이므로 d를 처음부터 -dir로 설정한 다음 시작해야 합니다.
d = -dir;
for (int i = sel + 1; i <= rightlimit; ++i) {
top[i] = Turn(top[i], d);
d = -d;
}
return;
}
int main() {
vector<string> gears(COUNT);
vector<int> top(COUNT, 0);
for (auto it = gears.begin(); it != gears.end(); ++it) {
cin >> (*it);
}
int K;
cin >> K;
for (int i = 0; i < K; ++i) {
int sel, dir;
cin >> sel >> dir;
--sel; // sel이 1부터 시작하므로 0부터 시작하게 normalize
Simulate(gears, top, sel, dir);
}
int score = 0;
int mult = 1;
for (int i = 0; i < COUNT; ++i) {
if (gears[i][top[i]] == '1') {
score += mult;
}
mult *= 2;
}
cout << score;
return 0;
}
4. 팁
B형에 대해서는 팁이 좀 있는데, A형은 사실 할 말이 많지 않습니다.
위의 풀이에 다 녹아내었으니 실수하기 쉬운 부분, 함정 등을 잘 캐치해내는 연습을 해보세요.
- 문제풀이에 들어가는 시간은 생각보다 길지 않다. 디버깅으로 낭비하는 시간이 훨씬 길다. 따라서 문제 조건은 제대로 읽고 한번 더 읽어라.
- 시간 복잡도를 생각해야 되는 경우도 있다. A형은 브루트포스로 대부분 풀리지만, 아닐 가능성도 있다. 테스트케이스 당 총 반복횟수가 1억번이 넘어가면 실패 가능성이 상당히 높아진다. 하지만, 1억번을넘지 않는다면 더 효율적인 알고리즘 고민하며 시간 낭비하느니 그대로 구현하면 된다.
- 가능하면 C는 쓰지 않는것이 좋다. 언어 자체의 문법적 제약도 심하고, 좋은 점이 하나도 없다. 굳이 C++ 배우기 싫다면, 그냥 using namespace std; 한줄만 위에 추가하고 C언어처럼 그대로 써라. C 코드 그대로 써도 전혀 문제 없고, 오히려 가끔 변수 선언을 코드 중간에 한다든가 하는 실수를 했을 때 C++ 문법이 눈감아줄 것이다.
- C++의 std::vector는 사랑이다. 초기화도 매우 쉽고, 사이즈 조절도 내장 메소드로 간편하며, 대단히 효율적이고(단, 주의할 점은 여러번 반복하여 불리는 함수에 &레퍼런스가 아니라 value copy로 넘기면 시간복잡도가 무지막지하게 늘어난다. vector의 value copy는 굉장히, 무시무시하게 고비용의 작업이다.) C array의 상위호환이다.
- C++에서 문자열을 쓸 일이 있다면 string 클래스를 쓰는 것이 char[] C스트링보다 훨씬 좋다. cout / cin과의 호환성도 그렇고, 크기도 마음대로 바꿀 수 있으며 훨씬 안정적이다. 심지어 라이브러리 못 쓰는 B형에서도, iostream 헤더에 string이 내장되어 있으므로(!!!) string 클래스는 사용할 수 있다.
- 내실을 갖추는 공부를 하는 것이 좋다. 아무리 벼락치기해서 SW테스트에 운좋게 붙는다 해도, 면접 및 실무에서 다 들통난다. 그냥 알고리즘 문제만 잔뜩 푸는 것보단 웹서비스 프로젝트나 유니티, MFC, Python/pyqt 등 이용해서 실질적인 프로젝트를 해보는 것이 코딩 센스도 늘리면서 스펙도 쌓고 경험 및 스토리도 만드는 지름길이다.
5. 맺음말
맺음말은 독백.
삼전 등 시작으로 카카오, 라인, 네이버 등 대부분의 대기업/IT기업들이 코딩 테스트를 실시하기 시작한 것은 상당히 좋은 변화라고 생각한다.
기존에는 C언어 기초도 힘겹게 대충 배운 사람들이 이런저런 흔한 대학생 스펙쌓는 활동을 하곤 대기업 개발직군에 들어가는 경우가 많았다. 이 때문에 고급 개발자원이 양성되기 어려운 환경이었고, SI 하청 프로젝트의 방향으로 트렌드가 치중되어 있었는지도 모른다.
어쨌든 학력차별이 줄어들고 실력으로 승부할 수 있는 사회가 되어가는 건 좋은 게 아닐까 싶다.
물론 코딩 테스트 또한 사교육 열풍의 손아귀를 벗어날 순 없기에 이것도 조만간 GET 리퀘스트가 뭔지도 모르면서 코딩테스트만 연습한뒤 취업되는 웹개발자들이 양성되는 모습으로 변질되지 않을까 하는 걱정이 들지만, 남 삿대질할 시간에 내 기술스택을 쌓는 게 우선순위일 것 같다.
보너스 : 3-1번 퀴즈 정답
- C라면 포인터로 parameter를 정의한 뒤 argument로 넘길 때 주소를 넘깁니다. C++는 좀 더 깔끔한 방법이 있는데, int &val과 같이 parameter를 정의한 뒤 argument로 넘길 때 그냥 넘기면 됩니다. Java의 경우 Int형은 immutable하므로 불가하며, 굳이 써야겠다면 별도로 class를 정의한 뒤 class를 wrapper처럼 쓰면 됩니다.
- 삽입 정렬은 O(n^2) 복잡도를 가집니다. 정확히는 n^(n-1)/2번 연산이며, Big O 노테이션 규칙에 따라 차수를 제외하고 버립니다.
- 1억번은 일반적으로 1초가 걸린다고 가정하면 좋습니다(CPU 성능이 좋으면 적게 걸리지만, 최악의 경우를 가정하는 것이 좋으므로). 이는 for문으로 stack depth가 깊어지지 않으면서 구현했을 때의 경우고, 이를 재귀함수로 구현하여 재귀 콜스택이 1억번이 된다면... 일반적으로는 그렇게 되기 훨씬 전에 뻗어버립니다.
- 가장 구현하기 간단한 방법은, 좌->우, 상->하, 왼대각선, 우대각선으로 크게 4사이클을 확인하면 되며, 각 사이클에서는 순서대로 오목판 전체를 확인하면 간단합니다. 현재 totalLen과 prevColor(0 비어있음, 1 W 2 B)를 변수로 가지고, 다음 칸에 돌이 있으며 해당 돌색과 prevColor가 같으면 totalLen을 1 증가시키고, 5가 되면 탐색을 종료합니다. 육목은 해당사항이 없어야 할 경우, 다음 칸까지 확인하여 prevColor가 같지 않을 경우에만 탐색을 종료합니다. 또한, 당연한 이야기지만 prevColor가 같지 않을 경우 totalLen을 0 혹은 1(비어있다면 0)로 초기화시키고 prevColor를 현재 돌색깔(비어있으면 0)로 초기화시킵니다. 100*100 판에서는 40000번 탐색으로 확인 가능하며, 1억번에 훨씬 못 미치기 때문에 무리 없습니다.
- ..이건 정말 기초이므로 생략합니다. 웃고 싶은 분들은 머신러닝으로 FizzBuzz 풀이를 보시기 바랍니다.
- 당연한 말이지만 모든 약수는 다른 약수와 곱해 N이 되는 짝이 존재할 수밖에 없습니다.
또한, N은 sqrt(N)*sqrt(N)과 같으므로 sqrt(N)보다 큰 약수는 당연히 sqrt(N)보다 작은 약수와 짝이 될 수밖에 없습니다. 따라서 소수 여부를 판별할 때 sqrt(N)보다 큰 수까지 확인하는 것은 낭비입니다.
그러므로 N이 2부터 sqrt(N) 이하의 정수로 나눠떨어지는 경우가 있는지 확인하면 소수 여부 판별이 가능합니다. 주의할 점은, N이 1이거나 2일 때 예외처리를 해줘야 합니다. 이 예외처리를 할 생각을 못했다면 정말 열심히 공부하지 않는 이상 알고리즘 시험에서 상당한 어려움을 겪을 가능성이 높습니다. Edge case에 대한 심각한 강박증은 어느 개발자나 갖춰야 할 덕목입니다.
'Memoir > 2017 삼성전자' 카테고리의 다른 글
| 삼성전자 SW 테스트 B형 가이드 (5) | 2018.05.14 |
|---|---|
| 삼성전자 S직군 17년 전반기/하반기 합격 후기 (5) | 2017.12.22 |
