알고리즘135 [알고리즘] 정렬 & 탐색 알고리즘 😋 들어가기 앞서 이번에 알고리즘 스터디를 새롭게 시작했다. 내 입맛대로 그러면서 이전에 공부했던 것을 복습하는 시간을 가지기 위해서 한번 싹 정리해볼까 한다. 내가 가장 기본이라 생각하는 정렬, 탐색 알고리즘부터 시작해볼까 한다. 🎯 목표 정렬 알고리즘의 종류를 익히고, 각각의 시간복잡도와 구현법을 익힌다. 이분탐색 알고리즘을 이해한다. 🪜 정렬 알고리즘 이름 그대로 주어진 데이터를 정렬하는 알고리즘이다. 7가지 알고리즘이 기본이고, 응용에 따라서 추가적인 알고리즘이 존재한다. 1️⃣ 선택 정렬 선택한 값을 모두 비교해서 알맞은 자리를 찾는 정렬 알고리즘이다. 즉, 선택한 값 다음에 오는 모든 값을 비교해서 가장 작은 값과 위치를 바꾼다. 시간복잡도 : O(n^2) public void selectio.. 2023. 4. 28. [Python] 백준 3079번 : 입국심사 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 💡 문제 풀이 이분탐색 문제이다. 이번 이분탐색 문제에서 중심이 되는 값은 주어진 시간에 얼마나 많은 사람들이 통과할 수 있을까이다. 최대 범위(모든 사람이 가장 오래걸리는 심사대)에서 최소 범위(0)부터 이분탐색을 진행한다. 모든 입국 심사대를 확인하는데, 주어진 시간으로 얼마나 많은 사람들이 통과할 수 있는지만 보면 된다. ✔️ 느낀 점 이분 탐색은 항상 헷갈리는 문제이지만 어떤.. 2023. 4. 27. [Java] 백준 19637번 : IF문 좀 대신 써줘 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 💡 문제 풀이 기본적인 이분탐색 문제이다. 칭호와 값의 매핑을 위해서 Map을 사용했고, 그중 비교가 빠른 HashMap을 사용했다. 중복을 제외해서 Map에 넣고 이분탐색을 위해 필요한 배열을 스트림으로 정렬해서 넣었다. 이후는 이분탐색으로 찾으면 된다! 시간복잡도는 아무리 커야 O(nlogn)이다. ✔️ 느낀 점 자바로 알고리즘을 푸는 건 너무 어렵다.. 2023. 4. 26. [Python] 백준 17140번 : 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 💡 문제 풀이 구현 문제이다. R 연산과 C 연산은 대상만 다를 뿐 똑같은 로직을 가진다. 따라서, 배열의 열과 행을 바꿔줌으로 추가적인 로직 구현을 할 필요가 없다. 연산을 하다 보면 처음 크기보다 작아져서 오류가 뜨는 경우가 있다. 예외처리를 통해서 그런 경우는 넘어가도록 하게 해야 한다. ✔️ 느낀 점 zip() 함수를 사용하면 정말 2차원 배열을 쉽게 뒤집을 수 있다. 이번 문.. 2023. 3. 8. [Python] 백준 16234번 : 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 BFS를 기반으로 한 구현 문제이다. 문제에서 요구하는 답은 인구 이동이 몇 번 일어났는지가 아니라 인구 이동이 일어난 날짜이다. 따라서, 단순하게 몇번 실행되었는지 보다 날짜를 기준으로 카운트하는 게 중요하다 ✔️ 느낀 점 중요한 점을 놓쳐서 코드를 깨작깨작 계속 수정햇던 문제이다. 시간 복잡도는 생각한대로 해결되었다! 💻 코드 import sys ; input = .. 2023. 3. 6. [Python] 소프티어 : 플레이페어 암호 https://softeer.ai/practice/info.do?idx=1&eid=804&sw_prbl_sbms_sn=162388 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 전형적인 구현 문제이다. key에 맞춰서 5x5 짜리 판을 초기화해 주고, 특정 알파벳의 위치를 저장한 테이블을 초기화한다. 이후 2자리로 잘라준다음 요구사항에 맞춰서 구현하면 된다. 주의할 점은 X가 단 하나 남았을 경우 XX가 만들어진다는 점과 J를 사용하지 않는다는 점이다. ✔️ 느낀 점 크게 어려울 것 없는 문제였다. 💻 코드 import sys ; input = sys.stdin.readline from collections import deque ALPHABET = ".. 2023. 3. 5. 이전 1 2 3 4 5 ··· 23 다음
