전체 글

[알고리즘] 버블 정렬(Bubble Sort)

버블 정렬이란 ? 버블 정렬은 이름처럼 데이터가 아래로부터 서서히 올라오는 것 같은 모습이라 해서 버블 정렬이라고 이름을 붙였다. 해당 알고리즘은 데이터들을 순회하면서 이웃 요소들끼리 데이터를 교환하며 정렬을 수행합니다. 구현하기 쉬운만큼 성능은 그만큼 안좋기 때문에 실제로는 사용이 거의 불가능한 수준이므로 공부용이 아니라면 볼일이 거의 없을것이다. 버락 오바마는 2008년 대선 캠페인을 위해 구글 플렉스를 방문했을때, 청중 앞에서 에릭 슈미트가 그에게 32비트 정수 백만 개를 정렬하기 위한 가장 효율적인 방법을 물었을때 버락오바마는 이렇게 대답했습니다. "버블 정렬은 아닌 것 같네요." 원리 버블 정렬은 아래와 같은 알고리즘으로 동작합니다. 첫 번째 요소부터 시작해서 첫 번째 요소와 두 번째 요소, 두..

[백준(BOJ) / C][Silver Ⅴ] 1343번 : 폴리오미노

문제 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 풀이 해당 문제는 '재귀함수'를 사용하여 풀었습니다. board[idx]가 ' . ' 이라면 해당 idx를 넘어가며 1를 더해줍니다. 만약 아니라면 'X'라는 뜻이므로 'X'가 아닌 배열까지 length값을 올려줍니다. 이렇게 하는 이뉴는 해당 'X' 문자열의 길이를 알수있기 때문입니다. 이렇게 알게된 'X'의 길이가 홀수라면 채워넣을수있는 방법은 없다는 뜻이기에 '-1'을 출력하며 컴파일을 종료시키고 아니라면 PrintPoli 함수를 호출하여 해당 result 배열에 집어 넣습니다. 여기서 값..

[백준(BOJ) / C][Bronze Ⅰ] 2869번 : 달팽이는 올라가고 싶다

문제 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 풀이 처음에는 반복문을 사용하여 풀면 되겠다고 생각했고 너무 쉽다고 생각했는데, 결과는 시간 초과로 실패... 그 이유를 보니 0.25초안에 1,000,000,000 라는 큰 숫자를 다 처리하기에는 너무나도 모자란 시간이기에 이건 수학적으로 접근해야겠다고 생각했다. 아침에는 A 만큼 가고 밤에는 B 만큼 떨어진다. 그렇다면 하루에 올라가는 거리는 A-B, 그리고 마지막 날에는 안떨어지기떄문에 총 올라가야하는 거리는 V-B 이다. 그렇다면 ( V - ..

[백준(BOJ) / C][Silver Ⅳ] 10773번 : 제로

문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 매 컴파일 마다 배열의 숫자가 달라지므로 동적할당을 이용하였습니다. 숫자가 배열에 들어갈때마다 현재 배열의 위치가 어디인지 확인하는 변수를 만들었고 숫자가 나가고 들어갈떄마다 1를 더하거나 뺐습니다. Queue 를 생각하고 풀면 쉽게 풀리는 문제입니다. 소스코드 #include #include int main(void) { int length = 0, ..