[업데이트 중...]
최신 문제들 풀이 : https://2heedu.tistory.com/169
19 하반기, 19 상반기, 18 하반기, 18 상반기 관련 문제 : https://2heedu.tistory.com/169
옛날 코드들은 코드를 작성한지 꽤 시간이 지나서 좋지않은 코드가 많습니다. 참고해주세요.
다시 풀면서 수정해나가겠습니다.
삼성 SW 테스트 (S직군 인적성) 관련 알고리즘 문제들을 정리하였다.
백준 사이트에 있는 기출 문제와 SWEA에 있는 모의 SW 테스트 문제를 정리하였다.
문제의 분류는 직접 푼 방법으로 나누어 보았고, 난이도는 주관적인 기준이다.
문제 정리
[완전탐색]
시험 감독 (기출) / 백준 13458 / 난이도 1
보물상자 비밀번호 (모의 기출) / SWEA 5658 / 난이도 2
[시뮬레이션]
주사위 굴리기 (기출) / 백준 14499 / 난이도 2
핀볼 게임 (모의 기출) / SWEA 5650 / 난이도 2
로봇 청소기 (기출) / 백준 14503 / 난이도 2
활주로 건설 (모의 기출) / SWEA 4014 / 난이도 2
경사로 (기출) / 백준 14890 / 난이도 2
특이한 자석 (모의 기출) / SWEA 4013 / 난이도 2
톱니바퀴 (기출) / 백준 14891 / 난이도 2
미생물 격리 (모의 기출) / SWEA 5644 / 난이도 2
감시 (기출) / 백준 15683 / 난이도 3
드래곤 커브 (기출) / 백준 15685 / 난이도 3
벽돌 깨기 (모의 기출) / SWEA 5656 / 난이도 3
줄기세포배양 (모의 기출) / SWEA 5653 / 난이도 3
원자 소멸 시뮬레이션 (모의 기출) / SWEA 5648 / 난이도 3
무선 충전 (모의 기출) / SWEA 5644 / 난이도 3
[브루트포스 / 백트레킹]
요리사 (모의 기출) / SWEA 4012 / 난이도 2
스타트와 링크 (기출) / 백준 14889 / 난이도 2
숫자 만들기 (모의 기출) / SWEA 4008 / 난이도 2
연산자 끼워넣기 (기출) / 백준 14888 / 난이도 2
치킨 배달 (기출) / 백준 15686 / 난이도 2
보호 필름 (모의 기출) / SWEA 5644 / 난이도 2
벌꿀채취 (모의 기출) / SWEA 5644 / 난이도 2
연구소 (기출) / 백준 14502 / 난이도 2
사다리 조작 (기출) / 백준 15684 / 난이도 2
디저트 카페 (모의 기출) / SWEA 5644 / 난이도 2
등산로 조성 (모의 기출) / SWEA 5644 / 난이도 2
점심 식사시간 (모의 기출) / SWEA 5644 / 난이도 3
테트로미노 (기출) / 백준 14500 / 난이도 3
[BFS]
홈 방범 서비스 (모의 기출) / SWEA 5644 / 난이도 2
[DP]
수영장 (모의 기출) / SWEA 1952 / 난이도 3
퇴사 (기출) / 백준 14501 / 난이도 3
코드 및 설명
완전탐색
시험 감독 (기출) / 백준 13458 / 난이도 1
각 방을 전부 탐색하며 필요한 감독 수를 계산한다. 인원 수 - B를 해주고 최소의 C를 구하여 더해준다.
[코드] : http://2heedu.tistory.com/40
보물상자 비밀번호 (모의 기출) / SWEA 5658 / 난이도 2
4개의 면이 있음을 유의하고 전체 경우를 탐색한다. 탐색하며 값을 벡터에 넣고 정렬한 후 정답을 구한다.
[코드] : http://2heedu.tistory.com/114
시뮬레이션
주사위 굴리기 (기출) / 백준 14499 / 난이도 2
주사위 배열을 만들어서 계산해준다. 범위 밖에 나갈 때 좌표를 옮기지 않는 것과 처음의 입력 x와 y가 행과 열임에 주의한다.
[코드] : http://2heedu.tistory.com/155
핀볼 게임 (모의 기출) / SWEA 5650 / 난이도 2
모든 핀볼 시작 가능 점에서 답을 구해 최대 값을 구한다. 각 블럭과 웜홀에 대해 경우를 나누어 순차적으로 시뮬레이션 한다.
범위에 벗어나는 경우 블럭 5와 같기 때문에 고려한다.
[코드] : http://2heedu.tistory.com/110
로봇 청소기 (기출) / 백준 14503 / 난이도 2
주어진 조건에 따라 방향 전환, 갈 수 없는 경우를 잘 나누면 쉽게 시뮬레이션 가능하다.
[코드] : http://2heedu.tistory.com/42
활주로 건설 (모의 기출) / SWEA 4014 / 난이도 2
가로와 세로에 대하여 각각 계산을 한다. 시뮬레이션을 돌며 옆과 비교하여 계산을 해준다.
[코드] : http://2heedu.tistory.com/43
경사로 (기출) / 백준 14890 / 난이도 2
가로와 세로에 대하여 각각 계산을 한다. 예전에 짠 코드라 너무 하드코딩 된 감이 있다.
[코드] : http://2heedu.tistory.com/26
특이한 자석 (모의 기출) / SWEA 4013 / 난이도 2
조건에 따라 경우를 나누어 회전과 변경을 해준다.
[코드] : http://2heedu.tistory.com/25
톱니바퀴 (기출) / 백준 14891 / 난이도 2
조건에 따라 경우를 나누어 회전과 변경을 해준다.
[코드] : http://2heedu.tistory.com/25 와 동일
미생물 격리 (모의 기출) / SWEA 5644 / 난이도 2
순서대로 시뮬레이션을 한다. 주의할 곳은 3개 이상이 합쳐질 때 크기 비교이다.
[코드] : http://2heedu.tistory.com/73
감시 (기출) / 백준 15683 / 난이도 3
카메라가 보는 방향에 따라 연산을 빠르게 하기 위해 배열에 미리 저장을 하였다.
[코드] : http://2heedu.tistory.com/78
드래곤 커브 (기출) / 백준 15685 / 난이도 3
세대가 증가할 때의 규칙을 찾아야한다.
0방향을 기준으로 다른 방향은 시작 방향 값 만큼만 더해서 %4를 해주면 같으므로 하나만 계산하면 된다.
[코드] : http://2heedu.tistory.com/157
벽돌 깨기 (모의 기출) / SWEA 5656 / 난이도 3
모든 경우를 시뮬레이션 한다. 이때 이어진 부분을 없애는 것을 dfs를 이용하여 계산한다.
벽돌을 없애고 다음 단계로 가기위해 떨어뜨리는 것은 큐를 이용하였다.
[코드] : http://2heedu.tistory.com/132
줄기세포배양 (모의 기출) / SWEA 5653 / 난이도 3
최악의 경우에 대비해 넉넉하게 시작점을 175, 175로 한 후 450만큼의 배열을 할당하였다.
활성화, 비활성화를 고려해주기 위해 애초에 곱하기 2를 하여 0이 되면 계산을 하였다. 큐에 담아 순차적으로 시뮬레이션 했다.
[코드] : http://2heedu.tistory.com/133
원자 소멸 시뮬레이션 (모의 기출) / SWEA 5648 / 난이도 3
순차적 시뮬레이션 말고도 수학적으로 풀 수 있다.
각 원자들에 대해 i=0에서 N-1까지, j=i+1에서 N까지 돌며 2개의 원자가 충돌 가능한지 판단하고 가능하면 충돌 시간과 2개의 원자를 벡터에 쌓는다. 모든 충돌 가능 경우를 판단 후 벡터에 쌓인 것을 충돌 시간 순으로 오름차순 정렬하여
순서대로 터트리고 이전 시간에 이미 터진 충돌은 제외한다.
[코드] : http://2heedu.tistory.com/111
무선 충전 (모의 기출) / SWEA 5644 / 난이도 3
움직이는 순서대로 시뮬레이션 한다. 여러 개의 충전 지점이 겹치는 경우를 꼼꼼히 고려하여야 한다.
[코드] : http://2heedu.tistory.com/112
브루트포스 백트레킹
요리사 (모의 기출) / SWEA 4012 / 난이도 2
브루트포스로 2 분류로 나누는 모든 경우를 계산하여 최댓값을 구한다. 벡터로 팀을 나누고 각 팀에 대한 값을 계산한다.
[코드] : http://2heedu.tistory.com/32
스타트와 링크 (기출) / 백준 14889 / 난이도 2
브루트포스로 2 분류로 나누는 모든 경우를 계산하여 최댓값을 구한다. 각 팀에 대한 값을 계산한다.
[코드] : http://2heedu.tistory.com/8
연산자 끼워넣기
브루트포스로 통해 각 연산자를 조합하여 모두 계산하다.
[코드] : http://2heedu.tistory.com/9
숫자 만들기 (모의 기출) / SWEA 4008 / 난이도 2
브루트포스로 통해 각 연산 기호들의 조합을 모두 계산한다.
[코드] : http://2heedu.tistory.com/30
치킨 배달 (기출) / 백준 15686 / 난이도 2
치킨 집의 M개수 만큼의 조합을 모두 만들며 백트래킹한다. dfs로 조합을 만들고 확인을 한다.
시간을 줄이기 위해 미리 모든 집과 치킨집의 거리를 계산한 후 사용한다.
[코드] : http://2heedu.tistory.com/158
보호 필름 (모의 기출) / SWEA 5644 / 난이도 2
백트레킹으로 모든 경우에 대해 연산을 돌린다. 문제를 주의 깊게 읽을 필요가 있다.
[코드] : http://2heedu.tistory.com/29
벌꿀채취 (모의 기출) / SWEA 5644 / 난이도 2
백트레킹으로 모든 경우에 대해 연산을 돌린다. 문제를 주의 깊게 읽을 필요가 있다.
[코드] : http://2heedu.tistory.com/31
연구소 (기출) / 백준 14502 / 난이도 2
브루트포스로 전체를 돌며 0인 곳에 3개씩 1로 만든다. 3개를 만들고 나면 2의 좌표를 돌며 바이러스를 퍼트리면서 안전영역을 구한다.
[코드] : http://2heedu.tistory.com/7
사다리 조작 (기출) / 백준 15684 / 난이도 2
브루트포스로 모든 사다리 경우를 만든다. 각 경우마다 확인한다.
[코드] : http://2heedu.tistory.com/3
디저트 카페 (모의 기출) / SWEA 5644 / 난이도 2
시간 복잡도를 줄이기 위해 방향 하나만 정해서 탐색을 하며 최소 개수만큼만 탐색한다.
[코드] : http://2heedu.tistory.com/28
등산로 조성 (모의 기출) / SWEA 5644 / 난이도 2
dfs의 개념을 정확히 알고 등산로가 될 수 있는 부분을 탐색한다.
[코드] : http://2heedu.tistory.com/27
점심 식사시간 (모의 기출) / SWEA 5644 / 난이도 3
계단에 사람들이 들어가는 경우의 조합을 다 계산한다. 계산 할때 시간에 유의한다.
[코드] : http://2heedu.tistory.com/71
테트로미노 (기출) / 백준 14500 / 난이도 3
브루트포스로 각 블럭을 구현하고 모든 경우 중 가장 큰 값을 찾는다. 그러나 개수가 작아서 배열로 가능한 경우를 미리 다 짜서
19개의 경우로 그냥 값을 탐색하였다.
[코드] : http://2heedu.tistory.com/41
BFS
홈 방범 서비스 (모의 기출) / SWEA 5644 / 난이도 2
bfs로 다이아 몬드 형태로 퍼지는 걸 연산한 후 각 비용을 계산한다.
[코드] : http://2heedu.tistory.com/33
DP
수영장 (모의 기출) / SWEA 1952 / 난이도 3
브루트포스로도 풀 수 있지만 dp로 간단한 점화식으로 답을 구할 수 있다.
-1개월과 -3개월의 dp값을 이용한 점화식을 세워 각 월까지의 min값을 구한다.
[코드] : http://2heedu.tistory.com/23
퇴사 (기출) / 백준 14501 / 난이도 3
dfs로도 풀 수 있지만 점화식 구현을 통한 dp를 통해 일 별로 계산을 했다.
[코드] : http://2heedu.tistory.com/38
모든 문제 관련 출처
- 백준 SW 테스트 기출 문제 : https://www.acmicpc.net/workbook/view/1152
- SWEA 모의 SW 테스트 문제 : https://www.swexpertacademy.com/main/searchAll/searchMore.do?category=CODE&keyword=%EB%AA%A8%EC%9D%98+sw
작성자 : 히더