본문 바로가기
반응형

전체 글1066

데이터의 추가, 삭제, 수정, 검색 - 해시 테이블 응용 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 해시 테이블의 기본을 응용하여, 추가/삭제/수정에 대해 알아보자. 어떤 게임의 DB에 아래와 같은 데이터가 있다고 가정해보자. 이 게임은 ID가 중복으로 있을 수 있다. 운영자는 이 DB를 관리해야하는데, 다음과 같은 기능이 필요하다. 1) 새로운 DB를 추가. 2) 현재 DB 중 특정 DB 삭제. (ID가 xxx인 DB 삭제, JOB이 wizard인 DB 삭제 등) 3) 현재 DB 중 특정 DB 수정. (JOB이 yyy인 DB에서 SERVER를 nova로 변경 등.. 2021. 2. 28.
BOJ 2667 : 단지번호붙이기 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2667 2차원 배열의 구역을 BFS, queue를 이용해 나눠보자.집인 곳을 발견하면, 집 주변의 영역을 찾아야 한다. BFS를 이용해 푸는 방법은 다음과 같다. 1) 집이 아니면(0) 넘어간다. 2) (r, c)가 집이면 queue에 담고 visit[r][c] = 1 로 체크한다. (다음에 다시 담지 않게 하기 위해)3) (r, c)의 4방향이 집이고 visit이 0이면 queue에 담는다.  이때, queue에 담으면서 집의 개수(영역의 크기)를 센다.4) 최종 영역의 개수를 return 한다.5) 2) ~ 3)을 queue가 빌 때까지 한다. ※ BFS 탐색 과정.. 2021. 2. 27.
BOJ 5373 : 큐빙 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/5373 실제 큐브를 만들어서 직접 돌리면 된다.시계/반시계 방향에 대해서는 아래처럼 구현하면 된다.if (clockwise == '+') { for (int r = 0; r 실제 시험장에서 종이에 큐브를 그려가면서 어떤 규칙이 있는지 확인해보는 것이 좋다. 그리고 U / D / F / B / L / R의 경우는 반대편의 면을 제외하고 변경하면 된다.예를 들어 U인 경우 UP과 DOWN을 제외하고 하나씩 변경하면 된다.물론 미리 원본 copy를 복사해둬야 한다.case UP: if (clockwise.. 2021. 2. 27.
BOJ 15686 : 치킨 배달 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15686  input을 받을 때, 치킨집과 집의 좌표를 받아두자.void input(){ scanf("%d %d", &N, &M); for (int r = 0; r  이제 선택할 치킨집 리스트를 만들어야 한다.살아남는 치킨집 리스트를 만들고, 그 치킨집에 대해 최소값을 갱신하면 된다.DFS를 이용해서 만들어보자.void DFS(int L, int chickenCount){ if (chickenCount > M) return; if (L > ccnt) /* 치킨집 보다 많으면 종료 */ { .. 2021. 2. 25.
BOJ 15685 : 드래곤 커브 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15685  방향을 먼저 모두 만들고, 시키는 대로 그리면 된다. 먼저 움직이기 위한 배열 dy, dx를 선언하자. 0: x좌표가 증가하는 방향 (→)1: y좌표가 감소하는 방향 (↑)2: x좌표가 감소하는 방향 (←)3: y좌표가 증가하는 방향 (↓)int dy[] = { 0, -1, 0, 1 };int dx[] = { 1, 0, -1, 0 }; 이제 moveList를 만들자.드래곤 커브의 규칙대로 처음 방향이 3인 경우, moveList는 아래와 같이 만들어진다.(직접 그려보자) L = 0 : 3.. 2021. 2. 25.
BOJ 15684 : 사다리 조작 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15684 먼저, 사다리를 구성하는 MAP 주변을 벽(3)으로 만들자.그리고 사다리 설치는 1 → 2로 설치하자.void input(){ scanf("%d %d %d", &N, &M, &H); for (int r = 0; r 이렇게 사다리를 설치하면, MAP에서 1을 만날 때 2로 이동, 2를 만나면 1로 이동할 수 있다. 이제 사다리 게임을 진행해서 모두 그대로 내려오는지 check하는 함수를 만들자. 1) 1번 사다리는 MAP[1][1]에서, N번 사다리는 MAP[1][N]에서 출발한다.2) 그리.. 2021. 2. 24.
BOJ 15683 : 감시 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/15683  먼저 모든 카메라가 방향을 가르키게 하기 위해, input에서 camera의 좌표를 따로 저장해두자.그리고, 5번 카메라의 경우는 방향이 없으므로 따로 모은다.MAP의 경우는 모두 6으로 만든 후, (1, 1)부터 MAP을 만들자. 주변을 미리 벽으로 만들면, 경계 조건을 체크하지 않아도 되기 때문이다.void input(){ scanf("%d %d", &N, &M); for (int r = 0; r  이제 camera 좌표와 방향을 넣으면 벽이 나올 때 까지, '#'으로 만드는 함수를 .. 2021. 2. 24.
BOJ 15666 : N과 M (12) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15666  N과 M (11)과 동일하지만, 다음으로 올 숫자가 크거나 같아야 하므로,DFS에 start를 이용해서 이전 숫자를 기억하면 된다.#include int N, M;int list[10];int possible[10000 + 100]; /* 가능한 번호의 수 10000 */int input[10]; /* input 저장 */void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0, 1).. 2021. 2. 23.
BOJ 15665 : N과 M (11) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15665  같은 수를 여러번 골라도 되기 때문에 중복되는 입력은 큰 의미가 없다.중복되지 않은 총 수를 count하여 N을 바꾸자.이때, N과 M (10)과 달리, possible은 중복을 체크하는 용도로만 사용한다.int count = 1;for (int i = 1; i  N이 변경되었으므로, visit관련 코드는 모두 필요가 없다.#include int N, M;int list[10];int possible[10000 + 100]; /* 가능한 번호의 수 10000 */int input[10]; /* input 저장 */void outputList(){ for (i.. 2021. 2. 23.
반응형

티스토리툴바