알고리즘 문제풀이

자료구조 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 자료구조 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 12. 자료구조 문제 (❌ 표시는 혼자 못푼 문제) 1. 1620번 나는야 포켓몬 마스터 이다솜 (실버4) 문제링크 2. 2164번 카드2 (실버4) 문제링크 더보기 문제 해석 N장의 카드에 1~N 번호가 적혀있음 1번 카드가 젤 위, N번카드가 젤 아래 순서로 놓여있음 카드가 한장 남을 때까지 아래 과정을 반복 1. 제일 위 카드를 바닥에 버림 2. 제일 위 카드를 제일 아래에 있는 카드 밑으로 옮김 N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하자. 제한: 2초 128MB 입력 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다. 출력 첫째 줄에 남게 되는 카드의 번호를 출..

분할정복 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 분할정복 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 11. 분할정복 분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 설명 출처 문제 (❌ 표시는 혼자 못푼 문제) 1. 2630번 색종이 만들기 (실버2) 문제링크 더보기 문제 해석 전체 종이의 크기는 NxN 종이를 자르는 규칙은 - 모두 같은 색으로 칠해져 있지 않으면 가로와 세로 부분을 잘라서 N/2 x N/2로 나눈다. - 나누어진 종이에 대해서도 모두 같..

백트래킹 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 백트래킹 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 6. 백트래킹 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다고 한다. DFS vs 백트래킹 - 백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 효율적이다. 하지만, N!의 경우의 수를 가진 최악의 문제에서는 여전히 지수함수의 시간복잡도가 걸려서 처리가 불가능할 수도 있다. 따라서, 가지치기를 얼마나 ..

문자열 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 문자열 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 8. 문자열 문자열을 이용하여 문제를 해결하는 알고리즘이다. 문제 (❌ 표시는 혼자 못푼 문제) 1. 10808번 알파벳 개수 (브론즈4) 문제링크 더보기 문제 해석 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오. 제한: 1초 256MB 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. 코드 ord(문자) : 문자의 아스키코드 번호 반환 chr(숫자): 숫자에 해당하는..

이진탐색(Binary Search) 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 이진탐색(Binary Search) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 7. 이진탐색(Binary Search) 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 시간복잡도는 logN이다. 단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 위 시간 복잡도를 가지게 된다. Python에서는 bisect라는 이진..

구현 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 구현 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 6. 구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 문제에서 거의 모든 문제가 '구현 문제'인데 가끔 구현이 어렵거나 구현에 초점이 맞추어진 문제들이 있다. 즉, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제라고 알고 있으면 된다. 구현알고리즘 숙지사항 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념 프로그래밍 언어의 문법을 정확히 알고 있어야 함 라이브러리 사용 경험을 늘려야 함 파이썬의 경우 자료형의 표현 범위 제한에 대해 깊게 생각하지 않아도 되지만 실수형 변수는 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음 크기가 1,..

동적계획법(DP) 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 동적계획법(DP) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 5. 동적계획법(DP) 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 다시 큰 문제를 해결할 때 사용하는 것. DP가 아닌 기억하며 풀기라고 부르기도 한다. (대표적인 문제: 피보나치 수열) dp 값을 구하는 규칙을 찾는 것이 가장 핵심인 문제이다. 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 이름의 의미는 없다. 벨만 리차드 씨가 멋있어보여서 그렇게 지은 것 일반적인 재귀 방식 또한 DP와 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용시 동일한 작은 문제들이 여러 번 반복되 비효율적인 계산이 될 수도 있다는 것이다. 사용조건 동일한 작은 문제들이 반복하여..

완전탐색(브루트포스) 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 완전탐색(브루트포스) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 4. 완전탐색(브루트포스) 브루트(Brute): 무식한 + 포스(Force): 힘 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 참고링크 문제 (❌ 표시는 혼자 못푼 문제) 2023. 12. 06. 2일차(4) 1. 2231번 분해합 (브론즈2) 문제링크 더보기 문제 해석 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합 = N+N각 자리수의 합 자연수 M의 분해합이 N일 경우..

너비 우선 탐색(BFS) 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 너비 우선 탐색(BFS) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 3. 너비 우선 탐색(DFS) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다. (주의!) 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다. BFS는 ..

깊이 우선 탐색(DFS) 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서   위 링크에서 깊이 우선 탐색(DFS) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.   2. 깊이 우선 탐색(DFS)루트 노드(혹은 다른 임의의 노드)에서 시작해서 다른 가지(branch)로 넘어가기 전에 현재 가지(branch)에 연결되어있는 애들을 완벽하게 탐색하는 방법미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.그래프..

그리디 알고리즘 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 위 링크에서 첫번째 순서인 그리디 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 1. 그리디 알고리즘 그리디(Greedy) : 욕심많은,탐욕스러운 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법. 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 현재 상황에서 '지금 당장 좋은 것!'만 고르는 것. 문제를 풀기위한 최소한의 아이디어를 적절히 떠올려야 풀 수 있다. 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념. 문제를 읽고 문제가 해결될 수 있는 경우의 수를 모두 생각해볼 것. 문제 (❌ 표시는 혼자 못푼 문..

코테 준비를 위한 알고리즘 공부 순서

코테준비과정에서 하루하루 푸는 문제를 업데이트하는 게시글입니다. 2023.9.25 코테 준비 시작!! 문제 조사 1. Jeong Jangoh 님이 만드신 자주 출제되는 유형과 풀어보면 도움이 많이 되는 문제 https://buly.kr/2qUsSAZ [Algorithm] 백준 문제 추천 devjeong.com 2. SW마에스트로 12기 지원대비 문제 풀이 https://www.acmicpc.net/workbook/view/10475 문제집: SW마에스트로 12기 지원대비 문제풀이 (1,2차) (bc1916) www.acmicpc.net 3. covenant 님이 만드신 코테 고득점 kit https://covenant.tistory.com/145 💊 코딩테스트 고득점 kit 20.04.04 20.04.2..