본문 바로가기
반응형

전체 글1066

BOJ 16236 : 아기 상어 (삼성 SW TEST A형) 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  아기 상어는 먹을 수 있는 물고기가 있는 경우, 움직여서 물고기를 먹어야 한다. 전체 코드 구조를 알아보자.. 2021. 3. 6.
BOJ 2178 : 미로 탐색 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2178  BFS를 이용하여 MAP에 거리를 남길 수 있다.이 문제의 경우는 벽이 0, 길이 1이므로, 1인 경우에 큐에 담고, visit을 체크한다. 다음과 같은 미로가 있다고 가정하자. 우리가 최종적으로 구해야할 지도의 모습은 아래와 같다. 도착점부터 칸을 세기 때문에 (1, 1)에서 (5, 5)까지 이동해야하는 칸은 총 9칸이다. 이제 BFS를 이용하여 거리를 재보자.2차원 MAP 탐색의 기본은 단지번호붙이기와 비슷하다.지금의 경우는 큐에서 pop할 때마다, 현재 위치 + 1을 기록하면 된다. ※ BFS 탐색 과정은 유니티를 이용해서 확인할 수 있다.먼저 최초 시작점 .. 2021. 3. 5.
BOJ 16235 : 나무 재테크 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16235 시뮬레이션 문제는 시키는대로 잘 구현하면 된다. 봄 : 나무의 나이만큼 양분 감소, 나무의 나이 1 증가, 어린 나무부터 양분 획득, 양분 부족시 사망.여름 : 죽은 나무가 양분으로 나이 / 2 만큼 추가가을 : 8방향 번식 나이 1의 나무가 생성겨울 : 양분 추가 문제의 핵심은 나무가 중복될 수 있다는 것이다.그리고 어린 나무부터 양분을 획득한다 조건에서 정렬이 필요할 것 같다. 무작정 구현했더니, time out이 나오게 되었다./* time out */void spring(){ /.. 2021. 3. 4.
BOJ 16234 : 인구 이동 (삼성 SW TEST A형) 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로 영역을 만드는 하는 함수를 만들어보자./* 순서대로 왼.. 2021. 3. 2.
유일한 수 두개 알고리즘 문제 전체 링크 judge.koreatech.ac.kr/problem.php?id=1074 유일한 수 문제의 응용 버전이다. 모든 수가 짝이 있으나 단 2개의 수만 짝이 없다. 유일한 수 문제대로 풀면 짝이 있는 수는 자연스럽게 제거할 수 있지만, 짝이 맞지 않는 두 수가 xor 연산되어 있어서 답을 구할 수 없게 될 것 같다. 하지만 여전히 xor 연산을 이용해서 문제를 해결할 수 있다. 먼저 두 수가 다르다는 것은, 최소 1 bit가 다르다는 뜻이 된다. 즉, 모든 N을 xor한 후, 어떤 다른 1 bit를 기준으로 1 bit가 있는 경우는 on에 xor을 1 bit가 없는 경우는 off에 xor을 하면 두 수가 분리된다. 예를 들어서 두 수가 3과 7이라고 하자. 0011(3)과 0111(.. 2021. 3. 1.
C, C++ - 최하위 / 최상위 비트 구하기 (Find MSB, LSB) C, C++ 전체 링크 삼성 C형 전체 링크 참고 - 비트 단위로 출력하기 다음과 같은 비트가 있다고 가정하자. 0010 0000 1100 0010 그러면 최하위 비트(Least Significant Bit)와 최상위 비트(Most Significant Bit)는 아래와 같다. 0010 0000 1100 0010 0000 0000 0000 0010 → 2 : 최하위 비트 (LSB : Least Significant Bit) 0010 0000 0000 0000 → 8192 : 최상위 비트 (MSB : Most Significant Bit) 최하위 비트 구하기 최하위 비트 추출법은 매우 간단하다. int lsb = x & (-x); // int lsb = x & (~x + 1) 2의 보수를 구하는 방법이기도.. 2021. 3. 1.
유일한 수 알고리즘 문제 전체 링크 judge.koreatech.ac.kr/problem.php?id=1007 문제의 조건을 보면 홀수개의 숫자가 입력이 되고, 그 중 단 하나만 다르다. 따라서 bit 연산 ^(xor)을 누적하면 단 하나의 숫자만 남게 된다. 어떤 숫자 N에 숫자 M bit를 반전시키고, 다시 M bit를 반전 시키면 N이 되기 때문이다. ( N = N ^ M ^ M ) 따라서 0부터 시작해서 누적하면 짝이 있는 숫자들은 자연스레 사라지게 된다. #include int T, N; int main(void) { scanf("%d", &T); for (int tc = 0; tc < T; tc++) { int ans; scanf("%d", &N); ans = 0; for (int i = 0; i < N.. 2021. 3. 1.
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.
반응형

티스토리툴바