문제 출처 : 코드트리_방화벽 설치하기 티어 : 골드4 유형 : 백트래킹, BFS 출제 : 2017년 상반기 오후 2번 주의사항 : 백트래킹같은 재귀함수 문제는 디버깅이 어려우므로 주의할 것. 첫 번째 문제와 비슷한 난이도로 출제된 두 번째 문제입니다. 첫 문제는 BFS, 두 번째 문제는 BFS가 섞인 재귀 문제를 내니 이때부터 그래프 문제를 본격적으로 내기 시작했다는 것을 알 수 있겠습니다. 현재에도 반드시 한 문제는 포함하고 있으므로, 그래프의 마스터가 되는 것을 목표로 공부해봅시다! 생각의 흐름 놓을 수 있는 벽이 최대 3개이므로, 빈 칸들 중에서 벽을 놓을 곳 3개를 고르는 조합 문제라고 생각을 했습니다. 따라서 벽을 놓을 수 있는 후보들을 wall cand list에 담고, 반복문을 이용하여 w..
삼성전자 코딩테스트 기출문제/Python
문제 출처 : 코드트리_자율주행 자동차 티어 : 골드5 유형 : 시뮬레이션 출제 : 2017년 상반기 오후 1번 주의사항 : 분기를 나누는 기준을 명확히 할 것. 설명이 정말 친절하죠? 혹시 이해를 못할까봐 영상자료까지 준비해주다니요. 실제 시험에서도 그래주면 좋으련만 독해력도 문제의 일부라고 주장을 하니, 백준의 로봇 청소기 문제에 대한 설명을 읽고도 이해할 수 있도록 감을 익히도록 합시다. 생각의 흐름 visited 배열을 따로 관리하기보다는 graph의 값을 도로도 인도도 아닌 값으로 바꿈으로서 구분하자고 계획했습니다. 그래프의 바깥이 모두 인도라고 가정되었으므로 범위를 고려하지 않고, 벽의 여부만 체크해도 되겠다고 생각했습니다. 4방향을 순차적으로 탐색하며, 모든 방향이 특정 조건을 만족했을 때 ..
문제 출처 : 코드트리_외주 수익 최대화하기 티어 : 실버3 유형 : 백트래킹 출제 : 2017년 상반기 오전 2번 주의사항 : 없습니다. 골드가 두 문제 배치된 오후와 다르게 실버문제가 출제되었습니다. 이런걸 보면 운이 참 중요하기도 하다는 것을 느낍니다. 이번 문제도 푸는 방법이 크게 두 가지로 나뉘는데요, 하나는 백트래킹, 나머지 하나는 dp입니다. 후술하겠지만 최대 휴가일이 몇 천일, 몇 만일이 아니라 15일 뿐이므로(ㅠㅠ) 여기서는 백트래킹으로 풀이하겠습니다. 생각의 흐름 문제를 딱 보자마자, 각 날짜별로 최대화된 수익을 기록하는 dp문제구나, 라는 생각이 들었습니다. 하지만 휴가일의 최대가 15일인점으로 미루어보아 백트래킹으로 더 쉽게 구현할 수 있겠다고 생각하여 백트래킹을 이용하기로 했습니다..
문제 출처 : 코드트리_테트리스 블럭 안의 합 최대화 하기 티어 : 골드4 유형 : 시뮬레이션 출제 : 2017년 상반기 오전 1번 주의사항 : 일반적인 백트래킹으로는 풀리지 않음에 유의할 것! 문제가 참 짧죠? 풀 수 있는 방법이 매우 다양한 문제입니다. 저는 브루트포스로 두 번, 백트래킹으로 두 번 총 네 가지 방법으로 풀었지만 비트마스킹 등의 기술도 쓸 수 있는, 그때그때 배웠던 것들을 써먹기 좋은 문제입니다. 이번 풀이는 백트래킹을 이용하였습니다. 생각의 흐름 처음에는 일반적인 깊이 4짜리 백트래킹으로 구현하자고 마음먹었습니다. 그러면 현재 위치에서 네 방향의 빈 칸을 찾아 블럭이 확장하게 되고, 모든 블럭을 만들 수 있을거라 생각했기 때문입니다. 하지만 이런 형태로 백트래킹을 구현했더니 바로 틀..
문제 출처 : 코드트리_2048 게임 (2048 (Easy)) 티어 : 골드2 유형 : 시뮬레이션, 백트래킹 출제 : 2016년 하반기 통합 2번 주의사항 : 블럭을 합치는 순서에 주의할 것. 바로 전년도와 더불어 4방향의 중력 구현을 수행해야했던 문제입니다. 2개의 사탕을 바로 풀 수 있을 정도의 실력이시라면 크게 어렵지 않았을거라고 생각합니다. 이 기술은 앞으로도 자주 출제되므로, 잘 다룰 수 있도록 기본기를 다집시다. 생각의 흐름 격자 판이 최대 다섯 번 까지만 움직이기 때문에 백트래킹 문제라고 생각을 했습니다. 깊이가 더 깊었다면 극한의 가지치기를 요구하는 문제이거나, 혹은 백트래킹 문제가 아니었을 겁니다. 글로벌 변수로 그래프를 사용하는 방법도 있지만 재귀를 통해서 그래프를 전달하는 형식으로 백..
문제 출처 : 코드트리_정육면체 굴리기 티어 : 골드4 유형 : 시뮬레이션, BFS 출제 : 2016년 하반기 통합 1번 주의사항 : 주사위 구현방법을 확실히 정하고 들어갈 것! 주사위를 어떻게 구현할지에 따라 난이도가 달라지는 문제입니다. 저는 다행히 아이디어로 풀어냈지만, 생각이 나지 않는다면 노가다로라도 주사위의 움직임을 구현해야합니다. 하드코딩이 보통 속도와 메모리가 더 적게 들 뿐더러, 풀기만 하면 되는게 삼성 코딩테스트 아니겠어요? 생각의 흐름 저는 이 문제를 보고, 주사위를 위/아래 방향으로 굴리면 양 옆면이 변하지 않고, 양 옆으로 굴리면 위/아래면이 변하지 않는다는 사실을 이용해 전개도를 이용하기로 했습니다. 그래서 row, column이라는 두가지의 큐를 이용해 주사위의 움직임을 구현하..
문제 출처 : 코드트리_2개의 사탕 티어 : 골드1 유형 : 시뮬레이션, BFS 출제 : 2015년 하반기 통합 2번 주의사항 : 중력구현과 사탕이 동시에 나가는 상황 삼성에서 1번에 브론즈 문제를 내고, 바로 출제한 골드1 난이도의 문제입니다. 1번을 풀고 싱글벙글 웃으며 2번 문제를 열어보았을 지원자들의 표정이 눈에 선합니다. 시키는대로 구현하면 되는 문제이지만, 섣불리 코드를 짜다가는 놓치는 케이스가 빈번하게 발생하는 문제입니다. 주의사항에 적은 두 가지가 대표적으로 많이 실수하는 부분이므로, 문제를 꼼꼼히 읽고 코드를 짜도록 합시다. 생각의 흐름 최대 10번 밖에 움직이지 않으며 최소 횟수를 출력하는 문제이기 때문에 백트래킹보다 디버깅이 용이한 큐를 사용하자고 다짐했습니다. 반복문이 끝날 때까지,..
문제 출처 : 코드트리_바이러스 검사 티어 : 브론즈2 유형 : 그리디 출제 : 2015년 하반기 통합 1번 주의사항 : 팀장이 한명씩 있어야 함에 주의 2015년 하반기는 삼성 그룹에서 SW직군에게 첫 코딩테스트를 실시한 시기이며, 초기 실험군답게 이례적으로 브론즈 난이도의 문제가 나온 해이기도 합니다. 플래티넘도 심심치않게 보이는 요즘과 비교해보면 불공평하다고 생각할 수도 있지만, 당시에는 파이썬의 사용이 불가능해서 지원자들이 느꼈던 난이도가 좀 다르지 않았을까 싶어요! 그래도 브론즈는 좀 부럽네요. 생각의 흐름 검사 팀장은 한 가게당 한 명씩 반드시 존재해야 한다 했으므로, 각 가게의 손님 수에서 검사 팀장이 검사할 수 있는 수를 빼준 후, 0 이하가 되면 더 이상 검사가 필요 없으니 넘기고, 양수..
