세상을 바꾸는 데이터

문제 링크: 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)..

안녕하세요! 오늘은 백준 알고리즘을 공부한 방식에 대해 정리해보고, 앞으로 어떤 계획을 가지고 공부할지 계획을 세워보는 시간을 가져보았습니다. 먼저 저의 깃허브 프로필과 solved.ac 계정입니다. 깃허브 프로필: https://github.com/dataexpert-moon dataexpert-moon - Overview Obstacles don't have to stop you. If you run into a wall, don't turn around and give up. Figure out how to climb it, go through it, or work around it. - dataexpert-moon github.com solved.ac 계정: https://solved.ac/pro..

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

문제 링크: https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ★문제풀이 Point★ 1. 총 돌의 개수는 고정이다. 2. 총 돌의 개수가 3의 배수가 아니라면 어떤 수를 쓰더라도 모든 그룹에 있는 돌의 개수를 같게 만들 수 없다. 풀이 과정: 이 문제는 강호가 모든 그룹에 있는 돌의 개수를 같게 만들려고 할 때 가능하면 1을, 불가능하다면 0을 출력하는 문제이다. 먼저 돌의 총합이 ..

문제 링크: https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 앞서 풀은 이모티콘 문제와 유사하다. 이모티콘 문제는 다음 포스트를 참고하자. https://data-flower.tistory.com/80 [백준 14226번] 이모티콘 - 파이썬 문제 링크: https://www.acmicpc.net/problem/1422..