최근에 카카오, 라인 CS 필기 테스트를 보면서 기초 CS를 많이 까먹었음을 깨달았다.. 퀵 정렬만 공부하고 갔다가, 다른 정렬들도 무수히 물어봐서 식은땀을 좀 흘렸다..;;;;;;; 기껏 어려운 1차 코딩테스트 다 붙었는데, CS 때문에 다 떨어지게 생겼다. 지금.. 그래서 정렬 알고리즘부터 다시 정리해보기로! 했다. 정렬 알고리즘은 컴퓨터 공학에서 매우 중요한 문제 중 하나이다. 그리고 자주 써야 한다. 뭐 물론 라이브러리 호출해서 자주 쓰긴 하지만, 내부 구조를 이해해야 상황에 따라 적절하게 사용할 수 있다. 이번 포스트에서 살펴볼 정렬 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬이다. 💡 버블 정렬(Bubble Sort) 버블 정렬은 거의 모든 상황에서 최악의 성능을 보여..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 이번에도 구현(시뮬레이션) 어게인.. 생각보다 구현 속도는 뚝딱뚝딱 빨라지고 있다. 그런데 눈이 이상한지, != 라고 써야하는 부분을 == 라고 쓰지 않나, second라고 써야하는 부분을 first라고 쓴 부분도 있었다..;;; 이런 경우 뭐 어쩔 수 없이 천천히 코드 한 줄씩 찍어보며 파악하는 수밖에 없다.. 이번 문제는 어제 푼 주사위 문제와 유사하다. 대신 주사위에서는 주사위 면들의 ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 주어진 문제 그대로 구현하면 나름 쉽게 풀 수 있는 문제이다. 대신 문제 이해가 살짝 까다롭다. 로봇 청소기는 기본적으로 (현재의 방향에서) 왼쪽 방향(시계 반대 방향)으로 돌아간다. 여기서 관건은 어떻게 로봇 청소기를 회전시킬 것인가? 이다. 문제에서는 0 - 북쪽 1 - 동쪽 2 - 남쪽 3 - 서쪽 이라는 설정을 안내했다. 그리고 왼쪽방향으로 돌아가는 순서는 동쪽 → 남쪽 → 서쪽 → 북쪽..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 지금까지 풀었던 문제와 완전히 다른 유형이다..어려운 구현 그 자체이다. 우선 주사위 굴러가는 걸 어떻게 구현할 것인가가 관건이다. 이 때 잘 생각해보면 주사위를 공중에 띄워놓고 면들만 굴려서 바꿔치기 한다고 생각하면 문제가 간단해진다. 그래서 크게 남북/ 동서로 회전 방향을 2가지로 나뉘어 놓는다. 그리고 면들을 각 방향에 맞춰 ..

https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 스택을 양쪽으로 쓰면 될 것 같다고 예상은 했으나 문제 풀이를 하는 데에는 어려웠다. 높은 빌딩에 가려지는 걸 구현하면 된다. 한 스택은 빌딩의 왼쪽을 비추고, 다른 한 스택은 빌딩의 오른쪽을 비춘다. 한 빌딩은 기준이고, 한 빌딩은 추가 여부를 고려해야하는 빌딩이다. 우선 두 빌딩보다 낮은 빌딩들은 앞으로 쭉 보여질 일이 없기 때문에, 모두 스택에서 제거한다. 그리고 만약 추가여부를 고려하는..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 오랜만에 PS 하는데 헤맸다...ㅠㅡㅜ 우선 이게 DFS로 풀면 쉬운 문제라는 사실을 인지하지 못했다. 처음에 시도한 방법은 크게 2가지이다. 1) 다이나믹 프로그래밍 i개의 칸을 이용해 만든 조합에 덧대면 되지 않을까? → 실패 → 왜냐하면 이전 칸 중 해당 조합에 포함되지 않은 칸을 포함해야 최대가 되는 경우는? 모두 꼬인다.. 반례) 3/4/5/2/1 만약 내 식대로 문제를 풀면..