본문 바로가기
반응형

알고리즘303

BOJ 16236 : 아기 상어 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16236 아기 상어 구조체는 좌표와 몇 마리의 물고리를 먹었는지, 그리고 현재의 크기가 필요하다. typedef struct st1 { int r; int c; int eat; int size; }SHARK; SHARK babyshark; input을 받으면서 9인 경우에 아기 상어 구조체를 초기화 해주자. void input() { scanf("%d", &N); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { scanf("%d", &MAP[r][c]); if (MAP[r][c] == 9) { MAP[r.. 2021. 3. 6.
BOJ 2178 : 미로 탐색 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2178 BFS를 이용하여 MAP에 거리를 남길 수 있다. 이 문제의 경우는 벽이 0, 길이 1이므로, 1인 경우에 큐에 담고, visit을 체크한다. 다음과 같은 미로가 있다고 가정하자. 우리가 최종적으로 구해야할 지도의 모습은 아래와 같다. 도착점부터 칸을 세기 때문에 (1, 1)에서 (5, 5)까지 이동해야하는 칸은 총 9칸이다. 이제 BFS를 이용하여 거리를 재보자. 2차원 MAP 탐색의 기본은 단지번호붙이기와 비슷하다. 지금의 경우는 큐에서 pop할 때마다, 현재 위치 + 1을 기록하면 된다. ※ BFS 탐색 과정은 유니티를 이용해서 확인할 수 있다. 먼저 최초 시작점 (1, 1)을 queue에 담고, visit[1][1] = .. 2021. 3. 5.
BOJ 16235 : 나무 재테크 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16235 시뮬레이션 문제는 시키는대로 잘 구현하면 된다. 봄 : 나무의 나이만큼 양분 감소, 나무의 나이 1 증가, 어린 나무부터 양분 획득, 양분 부족시 사망. 여름 : 죽은 나무가 양분으로 나이 / 2 만큼 추가 가을 : 8방향 번식 나이 1의 나무가 생성 겨울 : 양분 추가 문제의 핵심은 나무가 중복될 수 있다는 것이다. 그리고 어린 나무부터 양분을 획득한다 조건에서 정렬이 필요할 것 같다. 무작정 구현했더니, time out이 나오게 되었다. /* time out */ void spring() { /* 나무를 나이 순으로 정렬 */ for (int r =.. 2021. 3. 4.
BOJ 16234 : 인구 이동 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16234 2차원 탐색은 보통 BFS를 이용한다. 2차원 MAP 탐색 기본 원리는 단지번호붙이기를 풀어보자. 단지번호붙이기와 다른 점은, queue에 담는 조건이 인접한 A[r][c]의 차이가 L 이상 R 이하인 경우로 바뀐 것이다. 어쨌든, 조건을 만족하는 경우 queue에 담으면서 영역을 확장해 나가면 된다. 그리고 선택된 영역을 visit으로 check해서 다음 BFS에 선택되지 않도록 한다. 먼저 r, c, visit배열에 대해 BFS로 영역을 만드는 하는 함수를 만들어보자. /* 순서대로 왼쪽, 위, 오른쪽, 아래 */ int dr[] = { 0,-1,0.. 2021. 3. 2.
BOJ 1182 : 부분 수열의 합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1182 비트 연산을 이용해 집합을 나타낼 수 있고, 각 집합을 다 더할수도 있다. set = 1 2021. 3. 1.
BOJ 11723 : 집합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/11723 bit를 이용하여 집합을 나타낼 수 있다. int는 32 bit이기 때문에, 32개의 원소를 가진 집합을 나타낸다. BOJ 11723은 집합 S의 원소가 20이므로 int로 선언하면 해결할 수 있다. 가장 낮은 자리의 비트를 1번 비트가 아닌 0번 비트라고 정의하자. 원소가 1 ~ 20이므로 0번 비트는 무시한다. 1) add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. 비트 연산 or을 이용한다. S |= (1 2021. 3. 1.
데이터의 추가, 삭제, 수정, 검색 - 해시 테이블 응용 삼성 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 : 단지번호붙이기 알고리즘 문제 전체 링크 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형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/5373 실제 큐브를 만들어서 직접 돌리면 된다. 시계/반시계 방향에 대해서는 아래처럼 구현하면 된다. if (clockwise == '+') { for (int r = 0; r < 3; r++) for (int c = 0; c < 3; c++) Cube[face][c][3 - 1 - r] = copy[face][r][c]; } else { for (int r = 0; r < 3; r++) for (int c = 0; c < 3; c++) Cube[face][3 - 1 - c][r] = copy[face][r][c]; } 실제 시험장에서 종이에 큐브를 그려가면서 .. 2021. 2. 27.
반응형

티스토리툴바