세상을 바꾸는 데이터

문제 링크: https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ★문제풀이 Point★ 1. 계속해서 이동하는 벽을 어떻게 추가하고 삭제하는지 고민 필요(set, pop, appendleft) 2. 캐릭터가 이동한 다음, 벽이 이동하는 순서로 진행 3. 너비 우선 탐색(bfs)으로 구현 풀이 과정: 이 문제는 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보는..

문제 링크: https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 유형: 구현, 시물레이션 ★문제풀이 Point★ 1. 나무의 정보를 3차원 리스트로 담기 (행, 열, 나이) 2. 문제를 꼼꼼히 읽으면서 사계절별로 구현 3. 사계절 중에 여름 양분 처리 중요 풀이 과정: 이 문제는 K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하는 전형적인 시물레이션 문제이다. 구현, 시물레이션 문제는 문제를 꼼꼼히 ..

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 이 문제는 2019 카카오 신입 공채 1차 기출문제, 이코테 기출 25번 문제입니다. 풀이 유형: 구현, 정렬 ★문제풀이 Point★ 1. O(NlogN)의 시간으로 풀면 통과 가능한 문제 2. 문제에서 주어진대로 구현하면 되는 문제 풀이 과정: 이 문제는 실패율의 정의에 따라서 실수 없이 구현을 잘해주면 되는 문제이다. 시간 제한이 1초, stag..

문제 링크: https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 이 문제는 "이것이 코딩 테스트다" 책 유형별 기출문제 23번에 해당한다. 풀이 유형: 정렬 ★문제풀이 Point★ 1. 시간 복잡도를 생각한 후 문제 풀기 2. 리스트의 원소들을 정렬할 때는 람다(lambda) 함수 이용 풀이 과정: 이 문제는 정렬 문제를 공부하는데 필수로 풀어야 할 문제이다. 문제에서 조건을 살펴보면 N이 최대 100,000이고 시간제한이 1..

문제 링크: https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 플러드 필(Flood fill) ★문제풀이 Point★ 1. 0으로 인접해 있는 위치들을 같은 그룹으로 묶어준다. (플러드 필 = 색칠 알고리즘 이용) 2. 각 그룹별로 0의 개수가 몇 개인지 딕셔너리에 저장한다. 3. 벽으로 된 위치를 상하좌우를 돌며 인접한 그룹들을 구한 뒤, 그룹에 ..

문제 링크: https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시물레이션 ★문제풀이 Point★ 1. 벽을 부술 수 있는 경우는 단 1번! 2. 2차원 리스트가 아닌 3차원 리스트로 풀어야 한다. 풀이 과정: 이 문제는 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하는 문제이다. 단, 벽을 부술 수 있는 개수가 최대 1개임이 핵심이다. 필자는 다음 포..

정렬 알고리즘은 데이터를 특정한 기준에 따라서 정렬하기 위해 사용하는 알고리즘입니다. 대표적인 정렬 알고리즘의 동작 아이디어를 한 문장으로 정리해보겠습니다. 정렬 알고리즘 핵심 아이디어 선택 정렬 가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법이다. 삽입 정렬 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법이다. 퀵 정렬 기준 데이터(Pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 계수 정렬 특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법이다. 대표적인 정렬 라이브러리를 성능에 따라서 비교해보겠습니다. 정렬 알고리즘 평균 시간복잡도 공간 복잡도 특징 선택 정렬 O(N^2)..

문제 링크: https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 이 문제는 "이것이 코딩 테스트다" 책 유형별 기출문제 21번에 해당한다. 풀이 유형: 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시물레이션 ★문제풀이 Point★ 1. 모든 나라의 위치에서 상, 하, 좌, 우로 국경선을 열 수 있는지 확인(bfs) 2. 같은 연합끼리 인구를 동일하게 분배 풀이 과정: 이 문제는 각 나라의 인구수가 주어졌을 때, 인구 이동이 ..