전체 글

전체 글

    [알고리즘] 퀵소트(QuickSort) 구현 (C)
    Algorithm/개념 정리

    [알고리즘] 퀵소트(QuickSort) 구현 (C)

    수, 문자열 등 정렬이 필요한 상황에 퀵소트를 라이브러리 없이 구현하기 위함 정렬 조건 자체가 많더라도, while문 안에서 모두 해결이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include int arr[] = { 1, 10, 6, 9, 8, 2 }; void quickSort(int *, int start, int end); int main(void) { int size = sizeof(arr) / 4; printf("Before : "); for (i..

    [백준 1012] 유기농 배추 (C, DFS)
    Algorithm/백준(BOJ)

    [백준 1012] 유기농 배추 (C, DFS)

    문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 전형적인 DFS, BFS 기본 문제. C로 리마인드할겸.. 가로, 세로 입력은 순서 헷갈리지 않게 항상 주의하자~ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

    [백준 4963] 섬의 개수 (C)
    Algorithm/백준(BOJ)

    [백준 4963] 섬의 개수 (C)

    문제 링크 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net C언어로 연습할 겸 푼 문제. 새롭다 다시 익혀야겠다;; 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

    [프로그래머스] 베스트앨범 (Java)
    Algorithm

    [프로그래머스] 베스트앨범 (Java)

    문제 출처 : 링크 코딩테스트 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 play programmers.co.kr 장르와 노래는 해시 테이블을 직접 구현해 관리하고, 베스트앨범에 넣을 인덱스는 퀵소트를 만들어 뽑아냈다. 라이브러리 안쓰고 푸는 연습에 매우매우 좋은 문제..

    [백준 1197] 최소 스패닝 트리 (Java)
    Algorithm/백준(BOJ)

    [백준 1197] 최소 스패닝 트리 (Java)

    MST를 통해 풀어야 하는 문제다. MST에는 크루스칼과 프림 두가지 방법이 있다. dense가 많을 때는 프림이 더 효율적이다. 10만개의 간선이 들어오므로 프림으로 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer..

    [Pandas] 데이터 분석 (Google Colab 활용)
    파이썬(Python)

    [Pandas] 데이터 분석 (Google Colab 활용)

    [Pandas] 데이터 분석 DataFrame을 만들어 다루기 위한 설치 >>> pip install pandas >>> pip install numpy >>> pip install matplotlib pandas : DataFrame을 다루기 위해 사용 numpy : 벡터형 데이터와 행렬을 다룸 matplotlib : 데이터 시각화 데이터 분석 스칼라 : 하나의 값을 가진 변수 → a = 'hello' 벡터 : 여러 값을 가진 변수 → b = ['hello', 'world'] 데이터 분석은 주로 '벡터'를 다루고, DataFrame의 변수도 벡터 이런 '벡터'를 pandas에서는 Series라고 부르고, numpy에서는 ndarray라 부름 파이썬에서 제공하는 벡터 다루는 함수들 >>> all([1, ..

    [알고리즘] LCA(Lowest Common Ancestor)
    Algorithm/개념 정리

    [알고리즘] LCA(Lowest Common Ancestor)

    [알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상을 찾는 알고리즘 → 두 정점이 만나는 최초 부모 정점을 찾는 것! 트리 형식이 아래와 같이 주어졌다고 하자 4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2' 4와 6의 LCA는? → 첫 부모 정점은 root인 '1' 어떻게 찾죠? 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다. [depth : 정점] 0 → 1(root 정점) 1 → 2, 3 2 → 4, 5, 6, 7 parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다. // 1 ~ 7번 정점 (root는 부모가 없기 때문에 0) int parent..

    [CodeForce Beta Round #4] C. Registration system
    Algorithm/CodeForce

    [CodeForce Beta Round #4] C. Registration system

    문제 출처 : 링크 Problem - C - Codeforces codeforces.com 문제 자체는 어렵지 않다. 처음으로 등록되는 문자열은 "OK"로 출력하고, 만약 똑같은 문자열이 또 입력되면 숫자를 붙여서 출력해야한다. ex) Input 4 abacaba acaba abacaba acab output OK OK abacaba1 OK abacaba가 3번째에 또 들어오면서 abacaba1로 출력하는 모습을 볼 수 있다. 만약 한번더 들어오면 abacaba2를 출력하면 된다. 이 문제는 시간초과에 빠지기 쉬운 문제다. 왜냐하면 N의 값이 1~100000이다. 만약 브루트포스로 진행하면 N^2으로 100억번의 연산을 해야하는데 문제에 주어진 제한 시간 5초로는 불가능하다. 이 문제는 따라서 해시 테이..

    [CodeForce Beta Round #4] B. Before an Exam
    Algorithm/CodeForce

    [CodeForce Beta Round #4] B. Before an Exam

    문제 출처 : 링크 Input으로 요일 수(d)와 최대 시간(sumTime)이 주어진다. 그리고 d만큼 하루에 공부할 수 있는 최소 시간과 최대 시간이 각각 한 줄씩 들어온다. 모든 요일에 주어진 최소 시간만큼은 공부를 해야 하고, 최대 시간과 일치하는 공부 시간을 출력해야 한다. 주어진 요일의 공부시간동안 최대 시간만큼 할 수 없으면 "NO"를 출력하고, 가능하면 "YES"와 함께 요일별 공부시간을 출력해야 한다. 예) 2 5 0 1 3 5 d = 2고, sumTime = 5다. 이틀동안 5시간의 공부를 해야한다. 첫째날은 0~1시간 공부를 할 수 있고, 둘째날은 3~5시간을 공부할 수 있다. 첫째날에 1시간 공부 & 둘째날에 4시간 공부 or 첫째날 0시간 공부 & 둘째날에 5시간 공부 두가지 경우로..

    [CodeForce Beta Round #4] A. Watermelon
    Algorithm/CodeForce

    [CodeForce Beta Round #4] A. Watermelon

    문제 출처 : 링크 아주 간단한 문제다. input 값이 들어오면, 2명이서 나눠가질 때 둘다 짝수 값으로 가질 수 있으면 'YES' 아니면 'NO'를 출력해야한다. 예를 들면 2는 1과 1로 밖에 못나눠서 NO 6은 2와 4로 나누면 짝수라 YES 7은 짝수로 나눌 수 없어서 NO N이 1~100 사이에 수가 들어오므로, 1이 아닌 경우에 둘로 나눈 값이 모두 짝수로 나오는 경우가 있는지 판단하면 된다. 나는 N이 들어오면, for문에서 N을 2로 나누고 1씩 감소하며 두 수가 짝수인지 체크하는 방식으로 해결했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 package CodeForces; impor..

티스토리툴바