유자의 코딩모험

해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘. 주어진 배열 중에 최솟값을 찾고 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1)/2만큼의 비교가 일어나기 때문에 n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자..

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 가장 큰 값을 배열의 맨 끝에 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다. 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라 지어졌다고 한다. 구현 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이므로 O(n^2) 정렬이 되어있든지 안되어있든지 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 구현이 매우 간단하고 소스코드가 직관적이다. 추가적인 메모..

Object Oriented Programming (OOP) 객체 지향 프로그래밍은 컴퓨터 프로그래밍 패러다임 중 하나로, 프로그래밍에서 필요한 데이터를 추상화시켜 상태와 행위를 가진 객체를 만들고 그 객체들 간의 유기적인 상호작용을 통해 로직을 구성하는 프로그래밍 방법 클래스, 객체, 인스턴스 클래스 (class) 객체를 만들어 내기 위한 설계도 혹은 틀 어떤 문제를 해결하기 위한 데이터를 만들기 위해 추상화를 거쳐 집단에 속하는 속성(attribute)와 행위(behavior)를 변수와 메서드로 정의한 것 객체 (object) 소프트웨어 세계에 구현할 대상 물리적으로 존재하거나 추상적으로 생각할 수 있는 것 중, 자신의 속성을 가지며 다른 객체와 식별가능한 것 고유한 속성과 함수로 구성된 클래스를 통..

GET과 POST는 HTTP 메서드로 클라이언트에서 서버로 무언가를 요청할 때 사용한다. 그렇다면 각 방식의 특징과 GET과 POST의 차이점은 무엇일까? GET 클라이언트에서 서버로부터 정보를 조회하기 위해 설계된 메서드 요청하는 데이터가 HTTP Request Message의 Header 부분에 URL로 담겨서 전송됨 URL 끝에 ?와 함께 이름과 값으로 쌍을 이루는 요청 파라미터로 포함되어 전송되는데 이 부분을 쿼리 스트링(query string)이라고 한다 예시) http://www.example-url.com/resources?name1=value1&name2=value2 URL에 데이터가 담겨가기 때문에 전송할 수 있는 데이터의 크기가 제한적이다 데이터가 URL에 그대로 노출되므로 보안이 필요..

21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 문제 문제를 간략히 설명하면 다음과 같다. 선생님이 정한 학생의 순서와 각 학생이 좋아하는 학생에 대한 정보가 주어진다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, | r1 - c1 | + | c1 - c2 | = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접하다고 한다. 즉, 상하좌우칸을 인접하다고 말하는 것이다. 학생의 자리를 정할 때는 지켜야 하는 규칙이 있다. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로..

20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제풀이 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하는 문제다. 이중 for문으로도 해결할 수도 있지만 시간복잡도가 O(n^2)이기 때문에 시간초과가 발생할 가능성이 크다. 이럴 때는 투 포인터를 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 먼저 과정을 정리해보자면, 다음과 같다. left, right 모두 0에서 시작한다. cnt[arr[right]]이 K 미만이면 cnt 증가시키고 수열 길이를 갱신한 다음 right++..

2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제풀이 모든 육지에 대해서 BFS를 수행해서 각 육지에서 인접한 육지로 이동하면서 가장 긴 시간이 걸리는 육지를 찾는다. 각 육지의 최대 이동 시간을 비교했을 때 가장 큰 이동 시간이 보물이 묻혀 있는 두 곳 같의 최단 거리로 이동하는 시간이 된다. 코드 C++ 코드 Kotlin 코드

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 배추밭에 대한 정보를 담은 map 배열과 방문 여부를 표시하는 visited 배열을 초기화한다 배추가 심어져 있는 땅을 찾는다 DFS를..