알고리즘
-
💡파이썬 Disjoint-Set(Union-Find) 이론 및 예제| 자료구조 & 알고리즘/알고리즘 2023. 11. 29. 01:49
알고리즘 코딩 테스트를 준비하다 보면 다양한 자료구조와 알고리즘을 만나게 됩니다. 그 중에서도 Disjoint-Set(서로소 집합)을 활용한 Union-Find는 중상난이도 문제에서 자주 출제되는 유형 중 하나입니다. 이번 글에서는 Disjoint-Set, Union-Find의 개념과 파이썬으로 구현하는 방법에 대해 알아보겠습니다. Disjoint-Set(Union-Find)이란? 단순히 disjoint-set은 서로 다른 두 집합(서로소 집합)을 뜻함 서로 다른 집합을 모아 하나의 집합으로 만드는 Union-find 알고리즘에 사용됨 사용되는 case 그래프에서 서로 다른 정점을 연결하는 최소 신장 트리를 구하는 문제 서로 다른 집합을 합치는 문제 등 수행 연산 Union: 두 개의 집합을 하나로 합치..
-
💡코딩테스트 준비를 위한 효과적인 알고리즘 공부 방법| 자료구조 & 알고리즘/알고리즘 2023. 10. 21. 10:44
코딩 테스트는 개발자 진로를 희망하는 학생, 취준생, 직장인들이 부딪히는 난관입니다. 저 또한 비전공자로 취준을 시작해서, 수많은 코딩테스트를 치러 왔고, 마침내 최종합격하여 개발자로서 일하고 있습니다. 제 경험을 바탕으로 "코딩테스트 준비를 위한 효과적인 알고리즘 공부 방법"을 정리해볼까 합니다. 언어 선택 프로그래밍 언어는 아주 다양합니다. C, C++, Java, Python, JavaScript, Kotlin, Go, C#, Rust, Dart, Swift, Objective-C, 엄랭(ㅋㅋ), 등등...코딩테스트를 학습하려면 먼저 어떤 언어로 코딩할건지 정해야겠죠. 저는 취준할 때 조금 미련하게 했습니다. C, Python, Kotlin, Go, Java 다섯 가지 언어로 코딩테스트를 대비했습니..
-
💡 [알고리즘] 거품정렬, 선택정렬, 삽입정렬| 자료구조 & 알고리즘/알고리즘 2021. 10. 26. 09:06
Bubble Sort (거품 정렬) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 첫번째 라운드가 끝나면 가장 큰 데이터가 맨뒤 N번째에 있게 되어서 2회차는 N-1번째까지만 정렬하고 3회차는 N-2번째까지 정렬하는 식으로 정렬해요 총 라운드는 (배열 크기-1) 번 진행되고, 각 라운드별 비교 횟수는 (배열 크기-라운드 횟수)이에요 시간 복잡도 : 최선, 평균, 최악 모두 O(N^2) 공간 복잡도 : 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 추가적인 메모리 소비가 적어요 구현이 매우 쉬워요 안정 정렬, 제자리 정렬이에요 단점 다른 정렬 알고리즘에 비해 교환 과정이 많은 비효율적 알고리즘이에요 Selection Sort (선..
-
💡[BOJ 1915/ 코틀린] 가장 큰 정사각형 - DP문제풀이/BOJ 2021. 9. 3. 16:03
백준 1915_가장 큰 정사각형 | 문제 링크 대표적인 동적계획법/동적 프로그래밍 (DP:Dynamic Programming) 문제입니다. 문제 설명 n*m 크기의 0과 1로만 이루어진 이차원 배열이 주어집니다. 이 배열에서 (테두리, 내부 포함) 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제입니다. 입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. 출력 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. 전체 코드 fun main() { var n = 0 var m = 0 var maxLen = 0 readLine()!!.split(" ").let { n = it[0].toInt() m = it[1].toInt() } val m..
-
💡[BOJ 20922 / 코틀린] 겹치는 건 싫어 - 투 포인터문제풀이/BOJ 2021. 9. 3. 14:26
백준 20922_겹치는 건 싫어 | 문제 링크 투 포인터 기법을 활용한 문제입니다. 문제 설명 N개의 자연수로 이루어진 수열에서, 같은 수가 K번 이하로 반복되는 최장 연속 부분 수열을 구하는 문제입니다. N은 1~200,000 , K는 1~100 범위의 정수로 주어집니다.각 원소 ai는 1~100,000 범위의 정수로 주어집니다. 입력 첫째 줄에 정수 N과 K가 주어진다. 둘째 줄에는 a1,a2,...an이 주어진다. 출력 조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다. Main 함수 (전체 코드) import java.util.* fun main() { var N:Int = 0 var K:Int = 0 readLine()!!.split(" ").let { N = it[0].toInt() K ..
-
💡[BOJ 21608 / 코틀린] 상어 초등학교 - 구현문제풀이/BOJ 2021. 9. 2. 18:19
백준 21608_상어 초등학교 | 문제 링크 특별한 알고리즘이 아닌 단순한 구현 문제입니다. 문제 설명 N*N 교실에 1번부터 N²번까지의 학생이 한 자리씩 앉습니다. 각 학생의 친한 친구 4명씩을 사전 조사를 통해 파악해놨습니다. 각 학생의 만족도 총합이 가장 큰 좌석 배치 방법을 구하시오. 근처에 친한 친구가 0명이면 만족도는 0이고, 1명이면 1, 2명이면 10, 3명이면 100, 4명이면 1000이다. '근처, 인접'은 사방(四方)을 이야기한다. 규칙의 순서는 다음과 같다. 1. 빈 칸 중 친구가 인접한 칸이 가장 많은 칸으로 자리를 정한다. 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중 빈 칸이 가장 많은 칸으로 자리를 정한다. 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가..
-
💡 [BOJ 1018] 체스판 다시 칠하기카테고리 없음 2021. 6. 15. 11:11
문제) https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net [내 풀이] import sys N, M = map(int, sys.stdin.readline().split(" "))# 최초 보드의 행,열 갯수(N, M) 입력 board = list() ans = 64# 정답이 될 수 있는 가장 큰 값은 64 case1 = [[0 for i in range(8)] for j in range(8)] case1[0] = case1[2] = case1..
-
💡 [BOJ 1012] 유기농 배추문제풀이/BOJ 2021. 6. 15. 10:03
문제) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net [내 풀이] import sys # 재귀 제한(BOJ default 1000) 확장 sys.setrecursionlimit(10**9) # 첫줄 테이스케이스 개수 및 정보 입력 T = int(sys.stdin.readline()) for t in range(T): M, N, K = map(int, sys.stdin.readline().split(" ")) # table 초기화 table = [[0 fo..