KoreanFoodie's Study

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다! 해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 코드에 대한 설명은 주석을 참고해 주세요 :) 문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu 해답 코드 : // java import java.util.ArrayList; import java.util.Scanner; import java.io.FileInputStream; import java.util.Stack; /* 사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다. 이러한 상황에서도 동..

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다! 해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 코드에 대한 설명은 주석을 참고해 주세요 :) 문제 링크 : www.acmicpc.net/problem/14500 해답 코드 : // c++ #include int T, N, M; int input[501][501]; int visit[501][501] = { 0, }; int answer = 0; typedef struct point { int x, y; }point; // STACK 정의 point STACK[5]; int top = -1; point pop() { return STACK[top--]; } void push(int x, int y) { STACK[++t..

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다! 해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 코드에 대한 설명은 주석을 참고해 주세요 :) 문제 링크 : www.acmicpc.net/problem/15684 해답 코드 : #include int N, M, H, minCnt = 9999999, map[31][11]; // 자기 자신과 매칭되는 사다리인지 판단하는 함수 bool checkLadder() { for (int i = 1, pos; i

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다! 해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 코드에 대한 설명은 주석을 참고해 주세요 :) 문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 해답 코드 : // c++ #include using namespace std; int price[4]; // 각 이용권 별 요금 int dayOfMonth[13]; // 이용 계획 int minMonth[13]; // 각 달을 이용하는 데 필요한 최소 이용 금액. int d[13]; int min(int a, int b) { return (a < b) ? a ..

Heap sort python code implementation Heap sort 파이썬 코드를 작성해 보자. 힙 정렬(Heap Sort) 힙은 2진 트리인데, Min-heap(최소값이 루트 노드에 있음. 부모 노드가 자식 노드보다 작아야 함.)과 Max-heap(최대값이 루트 노드에 있음. 부모 노드가 자식 노드보다 커야 함.) 위키 피디아의 설명을 참고해 보자. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. 가장 큰 수(루트에 위치)..

Quick sort python code implementation 퀵소트(Quicksort)를 파이썬 코드로 구현해 보자. 퀵 소트(Quick sort) 퀵 소트는 배열을 파티션을 이용해서 반으로 나누고, 다시 이전 배열을 반으로 나눈 방식을 재귀적으로 적용한다. 파티션은 일반적으로, 제일 끝 배열의 원소를 pivot으로 잡고, 해당 pivot값보다 작은 값은 왼쪽으로 몰아 넣고, 큰 값은 오른쪽으로 몰아넣는다. 이 과정을 재귀적으로 반복하면, 각 파티션마다 O(n) 타임이 걸리고, 총 파티션은 평균적으로 O(logn) 타임이 걸리므로, 총 시간은 O(nlogn)이 걸리는 것을 알 수 있다. 위키피디아의 설명을 참고해 보자. 파티션은 다음과 같이 작동한다. 수도 코드를 살펴보자. function par..

Merge sort python code implementation merge sort 파이썬 코드를 작성해 보자. 병합 정렬(Merge Sort) 위키피디아의 설명을 참고해 보자. 병합 정렬은 다음과 같이 작동한다. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 병합 정렬의 핵심은, 문제를 푸는 방법론을 사이즈를 반으로 쪼갠 녀석에 적용해서 정렬을 완료한 후, 정렬이 완료된 반쪽짜리 2개를 다시 합침으로써 정렬을 마친다는 것이다. 즉, merge_sort함수는 2개의 merge..

Bubble sort python code implementation. 버블 정렬을 파이썬 코드로 구현해 보자. 버블 정렬 (Bubble Sort) 위키피디아의 정의를 참고해 보자. : 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 예시를 통해 버블 정렬이 어떻게 동작하는지 알아보자. 버블 정렬은 매우 단순한데, 그냥 처음부터 2개씩 짝을 지어 값을 비교한 후, 작은 녀석은 앞으로, 큰 녀석은 뒤로 보내면 된다. (55, 07)은 (07, 55)로, (55, 78)은 그대로, (78, 12)는 (12..

Insertion sort python code implemetation 삽입 정렬을 파이썬 코드로 구현해 보자. 삽입 정렬 (Insertion sort) 위키피디아에 나온 정의를 참고해 보자. 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이..

selection sort python code 선택정렬을 파이썬 코드로 구현해 보자. 선택정렬(Selection sort 기본 설명) 위키피디아에 있는 정의를 참고해 보자. 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 그림으로 표..