삼성기출 [알고리즘] 백준 15684 삼성 문제고 구현 문제다. 다음과 같이 사다리가 주어질때 i번째 최종적으로 i번째에 도착할 수 있도록 사다리를 추가하는 문제다. 역시나 범위도 깔끔하지 못해서 잘 정해줘야한다. 사다리를 그래프로 보면 dfs로 빈칸에 사다리를 추가해주면서 종료조건인지 체크해주면 된다. 그래프 크기를 HxN이라고하면 시간 복잡도는 HxN에 종료조건을 체크하는 함수가 그래프를 돌며 swap해줘야해서 HxNx3에 ... 삼성기출구현알고리즘시뮬레이션구현 [BOJ / C++] 14889 스타트와 링크 (삼성 기출) 문제풀이 N명의 사람 중, 스타트/링크로 나뉘어진 모든 조합을 구한 후 차이를 계산해서 그 중 제일 작은 것을 출력해야 한다. 조합을 구하기 위해 res배열을 0으로 초기화하고, 전형적인 조합 dfs를 사용하면서 2/N개의 원소를 1로 만들어준다. 총 2/N개가 선택되었을 때 res배열엔 2/N개의 1과 2/N개의 0이 있을 것이다. 1인 것을 스타트팀, 0인 것을 링크팀으로 하여 능력치 차... psbojBacktracking삼성기출bruteforceBacktracking [알고리즘] 백준 15685 선이 일정한 규칙으로 증가하는데 규칙대로 선을 이어보고 선으로 이루어진 박스를 체크하는 문제다. 결국 요구하는건 주어진 규칙대로 선을 그릴 수 있냐고 묻는 문제다. 지렁이가 각 세대를 증가하면서 길이가 점점 2배가 된다. 그리고 각 움직임에는 방향성이 존재한다. 처음에 접근한 방법은 각 방향을 기록해보고 세대를 증가할때 다시 거슬러 가는 방법이었다. 회전이라는 말때문에 처음에 당황했는데 방향... 삼성기출구현알고리즘시뮬레이션구현 [알고리즘] 백준 14889 N개 팀중에서 N/2개를 뽑아 팀을 정하고 나머지 N/2명의 팀과 점수가 최소가 되게하는 문제다. 결국 핵심은 N개중에서 N/2를 뽑는것이다. 조합으로 생각해볼수 있을거같다. python 을 사용했다면 combination을 사용했을테지만 C++로 라이브러리 사용없이 직접 구현해보았다.(c++도 순열과 조합을 표현하는 permutation이 있긴하다.) 처음 시도하였을때 너무도 자연스럽게 트... 삼성기출구현알고리즘시뮬레이션구현 [BOJ] 19237 - 어른 상어 초기는 모든 상어가 자기 위치에 냄새를 뿌린다. 1초마다의 이동 상어가 K번 이동하면 (k초뒤) 냄새는 사라진다. 이동 후 한칸에 여러 상어가 있으면 가장 번호가 작은 상어만 살아남는다 (1번이 제일 쎔) 이동 방향은 1 위, 2 아래, 3 왼쪽, 4 오른쪽으로 정의한다. 1번에 만족하는 칸이 없으면 내 냄새가 있는 칸 만약 만족되는 칸이 여러개면, 입력으로 주어진 바라보는 방향 마다의 특정... 알고리즘boj구현삼성기출boj [BOJ] 17144 - 미세먼지 안녕! 이 문제로 골4가 되었습니당 ~ ㅋ r*c 크기의 집에 공기청정기를 설치하려고 한다. A_{r,c} Ar,c 는 (r,c)칸의 미세먼지 양을 의미한다. 공청기 위치를 제외한 모든 칸에 부여된다. 1초간 다음과 같은 일이 일어난다. 미세먼지의 확산 : (r,c)의 인접한 4방향으로 A_{r,c} Ar,c //5만큼의 미세먼지가 확산 -> 벽이거나 공청기면 해당 칸으로는 확산 x A_{r,c} ... boj삼성기출알고리즘구현boj [BOJ] 19238 - 스타트택시 각 칸은 빈칸 또는 벽이고, 택시가 빈칸에 있는 경우, 상하좌우 중 빈칸인 칸으로 이동이 가능하다. 목표는 M명의 승객 태우기, 항상 최단 경로로 이동한다.승객을 태우고 목적지에 도착하면 연료가 충전되고, 연료가 바닥나면 운행을 종료한다. 승객 M명은 빈칸인 출발지에서 빈칸인 목적지로 이동하려고 한다. 한번에 한명씩만 총 M번의 운행을 해야한다. 현재 택시에서 최단거리에 위치한 승객을 먼저 ... bojDFS/BFS알고리즘삼성기출DFS/BFS [백준 15685번 드래곤 커브] C++ [15685번] 새로 찍히는 점을 기준으로 지금까지 저장했던 방향을 역순으로 돌면서 새로운 점을 찍어주면 되는 간단한 문제였다. 필자는 초반에 좌표를 저장해서 찍어야하는 문제로 풀이 방향을 잡아나갔으나 구현이 녹록치 않아 다른 방법을 생각해 본 결과 방향을 이용하면 풀린다는 결론을 얻었다(1시간 반 정도 쓴 것 같다). 2차원 배열 map[101][101]을 생성하고 제일 처음 주어지는 x,... 코딩테스트C삼성기출C [백준 16234번 인구 이동] C++ [16234번 인구 이동] 개인적으로 플레5 난이도의 큐빙보다 어려웠다. [5373 큐빙] 아이디어를 떠올리기까지는 오래 걸리지 않았다. 2중 for문으로 나라 전체를 돌면서 BFS(혹은 DFS)를 통해 마치 바이러스가 퍼지듯이 연합을 찾아주고, 각각의 연합에 맞게 평균 인구 수를 대입해준다. 더 이상 인구 이동이 일어나지 않을 때까지 반복하고 며칠 간 이동이 일어났는지 출력하면 된다. 주의... 코딩테스트삼성기출CC [20055번 컨베이터 벨트 위의 로봇] - C++ [20055번 컨베이터 벨트 위의 로봇] C++의 <algorithm> 헤더 파일에 존재하는 rotate 메서드를 사용하면 상당히 간단한 문제였다. rotate 메서드 사용법에 대해 궁금하다면 링크를 참고하면 될 것 같다. 제일 처음에 로봇을 올리지 않고 컨베이어 벨트가 회전한 후, 첫 로봇을 올린다는 언급이 있었으면 고민 거리가 하나 줄었을 것 같다. 항상 내리는 위치에 로봇이 도착하면 무... 코딩테스트C삼성기출C [BOJ] 15684 - 사다리 조작 dfs를 활용해서 백트래킹을 하려고 했다. 테케는 전부 맞게 나오는데 시간초과가 떴다 ^_ㅠ 대체 어디를 줄여야 할까,, 고민하다가 dfs도는 부분에서 매번 (0,0)부터 탐색하는게 아닌, 이전에 검사했던 부분 이후부터 탐색하도록 바꿨다. pypy3으로 아슬아슬하게 통과 ^_ㅠ... 구현알고리즘삼성기출bojboj
[알고리즘] 백준 15684 삼성 문제고 구현 문제다. 다음과 같이 사다리가 주어질때 i번째 최종적으로 i번째에 도착할 수 있도록 사다리를 추가하는 문제다. 역시나 범위도 깔끔하지 못해서 잘 정해줘야한다. 사다리를 그래프로 보면 dfs로 빈칸에 사다리를 추가해주면서 종료조건인지 체크해주면 된다. 그래프 크기를 HxN이라고하면 시간 복잡도는 HxN에 종료조건을 체크하는 함수가 그래프를 돌며 swap해줘야해서 HxNx3에 ... 삼성기출구현알고리즘시뮬레이션구현 [BOJ / C++] 14889 스타트와 링크 (삼성 기출) 문제풀이 N명의 사람 중, 스타트/링크로 나뉘어진 모든 조합을 구한 후 차이를 계산해서 그 중 제일 작은 것을 출력해야 한다. 조합을 구하기 위해 res배열을 0으로 초기화하고, 전형적인 조합 dfs를 사용하면서 2/N개의 원소를 1로 만들어준다. 총 2/N개가 선택되었을 때 res배열엔 2/N개의 1과 2/N개의 0이 있을 것이다. 1인 것을 스타트팀, 0인 것을 링크팀으로 하여 능력치 차... psbojBacktracking삼성기출bruteforceBacktracking [알고리즘] 백준 15685 선이 일정한 규칙으로 증가하는데 규칙대로 선을 이어보고 선으로 이루어진 박스를 체크하는 문제다. 결국 요구하는건 주어진 규칙대로 선을 그릴 수 있냐고 묻는 문제다. 지렁이가 각 세대를 증가하면서 길이가 점점 2배가 된다. 그리고 각 움직임에는 방향성이 존재한다. 처음에 접근한 방법은 각 방향을 기록해보고 세대를 증가할때 다시 거슬러 가는 방법이었다. 회전이라는 말때문에 처음에 당황했는데 방향... 삼성기출구현알고리즘시뮬레이션구현 [알고리즘] 백준 14889 N개 팀중에서 N/2개를 뽑아 팀을 정하고 나머지 N/2명의 팀과 점수가 최소가 되게하는 문제다. 결국 핵심은 N개중에서 N/2를 뽑는것이다. 조합으로 생각해볼수 있을거같다. python 을 사용했다면 combination을 사용했을테지만 C++로 라이브러리 사용없이 직접 구현해보았다.(c++도 순열과 조합을 표현하는 permutation이 있긴하다.) 처음 시도하였을때 너무도 자연스럽게 트... 삼성기출구현알고리즘시뮬레이션구현 [BOJ] 19237 - 어른 상어 초기는 모든 상어가 자기 위치에 냄새를 뿌린다. 1초마다의 이동 상어가 K번 이동하면 (k초뒤) 냄새는 사라진다. 이동 후 한칸에 여러 상어가 있으면 가장 번호가 작은 상어만 살아남는다 (1번이 제일 쎔) 이동 방향은 1 위, 2 아래, 3 왼쪽, 4 오른쪽으로 정의한다. 1번에 만족하는 칸이 없으면 내 냄새가 있는 칸 만약 만족되는 칸이 여러개면, 입력으로 주어진 바라보는 방향 마다의 특정... 알고리즘boj구현삼성기출boj [BOJ] 17144 - 미세먼지 안녕! 이 문제로 골4가 되었습니당 ~ ㅋ r*c 크기의 집에 공기청정기를 설치하려고 한다. A_{r,c} Ar,c 는 (r,c)칸의 미세먼지 양을 의미한다. 공청기 위치를 제외한 모든 칸에 부여된다. 1초간 다음과 같은 일이 일어난다. 미세먼지의 확산 : (r,c)의 인접한 4방향으로 A_{r,c} Ar,c //5만큼의 미세먼지가 확산 -> 벽이거나 공청기면 해당 칸으로는 확산 x A_{r,c} ... boj삼성기출알고리즘구현boj [BOJ] 19238 - 스타트택시 각 칸은 빈칸 또는 벽이고, 택시가 빈칸에 있는 경우, 상하좌우 중 빈칸인 칸으로 이동이 가능하다. 목표는 M명의 승객 태우기, 항상 최단 경로로 이동한다.승객을 태우고 목적지에 도착하면 연료가 충전되고, 연료가 바닥나면 운행을 종료한다. 승객 M명은 빈칸인 출발지에서 빈칸인 목적지로 이동하려고 한다. 한번에 한명씩만 총 M번의 운행을 해야한다. 현재 택시에서 최단거리에 위치한 승객을 먼저 ... bojDFS/BFS알고리즘삼성기출DFS/BFS [백준 15685번 드래곤 커브] C++ [15685번] 새로 찍히는 점을 기준으로 지금까지 저장했던 방향을 역순으로 돌면서 새로운 점을 찍어주면 되는 간단한 문제였다. 필자는 초반에 좌표를 저장해서 찍어야하는 문제로 풀이 방향을 잡아나갔으나 구현이 녹록치 않아 다른 방법을 생각해 본 결과 방향을 이용하면 풀린다는 결론을 얻었다(1시간 반 정도 쓴 것 같다). 2차원 배열 map[101][101]을 생성하고 제일 처음 주어지는 x,... 코딩테스트C삼성기출C [백준 16234번 인구 이동] C++ [16234번 인구 이동] 개인적으로 플레5 난이도의 큐빙보다 어려웠다. [5373 큐빙] 아이디어를 떠올리기까지는 오래 걸리지 않았다. 2중 for문으로 나라 전체를 돌면서 BFS(혹은 DFS)를 통해 마치 바이러스가 퍼지듯이 연합을 찾아주고, 각각의 연합에 맞게 평균 인구 수를 대입해준다. 더 이상 인구 이동이 일어나지 않을 때까지 반복하고 며칠 간 이동이 일어났는지 출력하면 된다. 주의... 코딩테스트삼성기출CC [20055번 컨베이터 벨트 위의 로봇] - C++ [20055번 컨베이터 벨트 위의 로봇] C++의 <algorithm> 헤더 파일에 존재하는 rotate 메서드를 사용하면 상당히 간단한 문제였다. rotate 메서드 사용법에 대해 궁금하다면 링크를 참고하면 될 것 같다. 제일 처음에 로봇을 올리지 않고 컨베이어 벨트가 회전한 후, 첫 로봇을 올린다는 언급이 있었으면 고민 거리가 하나 줄었을 것 같다. 항상 내리는 위치에 로봇이 도착하면 무... 코딩테스트C삼성기출C [BOJ] 15684 - 사다리 조작 dfs를 활용해서 백트래킹을 하려고 했다. 테케는 전부 맞게 나오는데 시간초과가 떴다 ^_ㅠ 대체 어디를 줄여야 할까,, 고민하다가 dfs도는 부분에서 매번 (0,0)부터 탐색하는게 아닌, 이전에 검사했던 부분 이후부터 탐색하도록 바꿨다. pypy3으로 아슬아슬하게 통과 ^_ㅠ... 구현알고리즘삼성기출bojboj