본문 바로가기
반응형

전체 글1307

퀵(Quick) 정렬 퀵(Quick) 정렬 - O(N logN) - pivot을 기준으로 하여 큰 값과 작은 값을 찾아 바꿔가며 정렬하는 것입니다. ▶ [예제] 퀵 정렬 구현 [예제] 퀵 정렬 구현 Problem Solving을 하다보면 주어진 원소를 정렬 시킬 필요가 있습니다. 물론 STL을 이용해서 구현할 수 있지만 해당 노트에서는 구조체 형태로 정렬하는 내용을 다룹니다. 상황 (조건) 특정 사람이 { zoosso.tistory.com 시뮬레이션 ① 기준 Pivot을 첫번째 원소로 설정합니다. ② 좌측에서 pivot 값보다 큰 값을 찾습니다. 우측에서 pivot 값보다 작은 값을 찾습니다. arr[left] = 8 / arr[right] = 2 ③ 찾은 두 값의 위치를 바꿔 줍니다. ④ 이러한 작업을 좌측에서 찾은 값이 .. 2021. 6. 4.
삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) - O(N2) 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하여 정렬 정위치에 삽입해야 하므로 기존에 있었던 원소를 뒤로 밀어주어야 합니다. ※ 대부분의 원소가 이미 정렬되어 있는 경우에는 효율적이지만, 그렇지 않은 경우 빈번한 이동 발생 [C 언어] - 오름차순 기준 # include int swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void insertionSort(int arr[], int n) { for (int i = 0; i 0 && arr[pivot - 1] > arr.. 2021. 6. 2.
[Windows] shutdown 명령어를 통한 컴퓨터 종료 예약 컴퓨터 (예약) 종료 (shutdown) 다운로드와 같은 작업이 끝나고 PC를 종료하고 싶은데, 그 순간까지 계속 기다릴 수 없다. Windows OS에서는 간단한 명령어를 통해서 PC를 강제 종료 및 예약 종료할 수 있다. 명령어는 명령 프롬프트 창에서 수행한다. 단축키: [시작] + [R] → 팝업창에서 "cmd" 입력 후 Enter 혹은 "명령 프롬프트"을 검색하면 된다. 강제 종료 shutdown -s -f -s = PC off -f = 사용자에게 경고없이 실행 중인 응용프로그램까지 강제 종료 (-s 만으로도 종료처리할 수 있지만 -f 옵션까지 해주어야 확실.) 예약 종료 shutdown -s -t {숫자} -t = 지정한 seconds(초) 이후에 종료한다. 초 단위로 계산되기 때문에 아래와 같.. 2021. 5. 31.
[ps] 여러 정수 기준에 따른 우선순위 비교 및 정렬 해당 게시글에서는 여러 정수형 데이터로 우선순위가 나눠질 때, 효율적으로 처리할 수 있는 방법을 제시합니다. 몇몇 문제에서는 2가지 이상 기준에 의해 정렬되거나 우선순위가 정해집니다. ▶ [BOJ] 21608 상어 초등학교 (삼성 코딩 테스트 문제) ▶ [BOJ] 21609 상어 중학교 (삼성 코딩 테스트 문제) 만약, 사전순 배열과 같이 문자열 비교가 필요한 경우에는 아래 게시글 참고 ▶ [ps] 문자열 사전 오름차순 비교 및 정렬 [ps] 문자열 사전 오름차순 비교 및 정렬 문제를 풀다보면 ID가 작은 기준으로 하되, 동일한 ID인 경우에는 알파벳 오름차순으로 우선순위를 가지도록 하는 조건이 있습니다. 여러 기준에 의해 우선순위가 결정되는 경우 입니다. 숫자를 zoosso.tistory.com 구조체.. 2021. 5. 30.
[ps] 문자열 사전 오름차순 비교 및 정렬 문제를 풀다보면 ID가 작은 기준으로 하되, 동일한 ID인 경우에는 알파벳 오름차순으로 우선순위를 가지도록 하는 조건이 있습니다. 여러 기준에 의해 우선순위가 결정되는 경우 입니다. 숫자를 비교하는 경우에는 단순 비교를 하면 되지만, 아래 두가지를 처음 구현한다면 쉽지 않습니다. 대표적인 문제로 S사 코딩 기출 문제가 있습니다. [BOJ] 백준 21608 상어 초등학교 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/21608 Approach BFS + 완전탐색을 구현하는 문제이다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-.. zoosso.tistory.com [BOJ] 백준 2.. 2021. 5. 30.
[BOJ] 백준 21610 마법사 상어와 비바라기 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/21610 Approach 21년 상반기 1번 문제로 구현 + 시뮬레이션 유형이다. ① 초기에 지정된 4개의 위치에서 구름이 생성된다. ② 생성된 구름이 주어지는 방향 d로 s 칸 이동한다. 이때, 경계선을 벗어나는것 없이 map[][]에서 순환되도록 조건이 있다. 행/열에 대해서 (N - 1) → (N) → (1) 혹은 (2) → (1) → (N) 구조가 된다. 이동이 끝나고는 해당 위치에 물을 증가시키고, 구름 위치(visited[][])를 표시한다. if문과 같이 조건문을 이용해서 처리할 수 있지만 위와 같은 수식을 이용한다면 구름에 도착한 곳을 알 수 있다. 해당 계산과정 원리.. 2021. 5. 30.
[ps] 순환되는 행렬 인덱스 (Index) N × N 행렬 탐색 문제를 풀다보면 1번 행(열)과 N번 행(열) 연결되는 경우가 있다. ▶ 1번 행 위에 N번행이 존재하고 / N번 행 아래에 1번행이 존재하는 경우 임의의 위치 (x, y)에서 상 / 하 / 좌 / 우 방향 중 한 가지 방향으로 k 칸 이동한다고 했을 때, ▶ 10 × 10 크기의 map[10][10] 변수가 주어지고, 인덱스 범위는 0 ~ 9 이다. K = K % N; int nextX = (cur.x + (dx[dir] * K) + N) % N int nextY = (cur.y + (dy[dir] * K) + N) % N (K의 수치가 크게 주어지는 경우 1 Cycle 기준으로 나머지 연산 처리) 도착하는 위치를 크게 아래 4가지 경우로 고려한다. - 증가해서 (우측 이동) 범위.. 2021. 5. 30.
맛집 탐방 관련 글 작성할 때 고려하는 내용 (음식점 리뷰) 해당 음식점/카페에 대한 객관적인 정보를 제공해야 것과 동시에 직접 경험해보면서 느낀 생각과 맛 평가가 있으면 좋습니다. 1) 가게 이름 - Main 사진 (썸네일 활용 가능) - 건물 외부 모습 (간판 같이 매장 이름이 보이도록) 2) 주소(위치 / 찾아오는 길) - 상세한 위치도 좋지만 대중교통을 이용한 접근 방법도 함께 명시 - 한 지역에 체인점이 여러개 일 수 있으므로 구분 - 지도와 함께 표시해주면 좋습니다. 3) 영업 시간 - 평일 / 주말 / Break Time / 정기 휴무 - Open ~ Close 타임 - Last Order 시간 4) 주차 가능 여부 - 주차 시설과 편의성 - 최대 수용 가능한 차량 대수 5) 예약 가능 여부 및 전화번호 - 전화 예약 혹은 App 예약 등 방법까지 명.. 2021. 5. 28.
Hash (양방향, 더미노드 1개, *head) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. ▶ Hash 구현 (양방향, 더미노드 0개, *head) Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법 과 Open Address 기법으로 해결할 수 있다. ▶ [해시] Hash란? ▶ [해시] Hash Chaining 기법 구현 구조체 정보 struct Node { int id; Node* prev,.. 2021. 5. 28.
freopen( )을 이용한 파일 입출력 freopen() 필요성 알고리즘 문제를 풀다보면 주어진 Input Data를 입력받아 Logic을 수행한 후 정해진 Output Data를 출력한다. scanf()나 cin 으로 표준 입출력 하는 경우에는 계속해서 Copy & Paste해야 하는 번거로움이 있다. 이러한 작업을 쉽게 해주는 것이 파일 입출력이다. freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); [리소스 파일] 하위에 "input.txt"와 "output.txt" 파일을 둔다. (파일명은 임의로 설정하면 된다.) 해당 파일은 프로젝트에서 .cpp와 같은 경로에 있는 것을 확인할 수 있는데 다른 위치에 두는 경우에는 그것에 맞춰서 경로를 지정할 수 있다. #inc.. 2021. 5. 24.
반응형

티스토리툴바