메이쁘

https://www.acmicpc.net/problem/1159 1159번: 농구 경기 문제 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 www.acmicpc.net 진짜 오랜만에 다시 백준 문제를 풀기 시작했다. 복귀 문제?! 쉽기 때문에 별도의 해설 및 알고리즘 설명은 생략하겠다. 간단하게 말하자면, 같은 문자의 개수를 파악하는 문제들은 'a', 'A' 와 같이 시작 문자의 아스키코드를 파악하여 (여기서는 'a' 가 시작문자이므로, 'a' 는 97 이다.) 해당 문자 - 'a' 를 배열의 index로 보고 해당 index의 원소를 counting하면 된다. 만약,..

안녕하세요. Matrix chain multiplication(행렬 최소 곱셈 알고리즘) 길죠. 간단하게 설명드리겠습니다! Matrix chain multiplication(행렬 최소 곱셈 알고리즘) 이란? - M : Matrix(행렬), d : dimension(차원) - Matrix는 1 ~ 4 까지 4개가 존재하고, dimension은 0 ~ 4 까지 5개가 존재한다고 하자. - 각 Matrix의 왼쪽 dimension 은 행, 오른쪽 dimension 은 열이다. - 위 알고리즘이 성립하기 위한 필수 조건은 위 그림처럼 1) 이전 Matrix의 열 과 다음 Matrix의 행 이 같다. 2) 이전의 이전 Matrix의 열과 이전 Matrix의 행이 같다. 이다. *** 행렬의 곱셈을 위한 조건과 동..

https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 문제 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. � www.acmicpc.net 이진 탐색 분류로 되어있는데 그리디로 해결한 문제. 생각보다 쉽지만 처음 규칙을 찾는데 조금 걸렸다. 핵심은 - 시작 인덱스를 1로 가정하고, 입력받은 책의 맨 앞에서부터 끝까지 하나씩 시작 인덱스와 비교한다. - 비교했을 때, -> 시작 인덱스 + 1 보다 더 크다면 -> 해당 값 과 시작 인덱스 차이만큼 별도 값에 더한 후, 시작 인덱스를 해당 값 으로 변경한다. -> 시작 인덱스 +..

https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 www.acmicpc.net 착한 제목에 그렇지 못한 문제.. 이진탐색 보다는 탐욕에 가까운 문제로 골머리 한시간 썩히다가 해설을 참고하니 그리디로 더 쉽게 풀 수 있었다. 핵심 - 못 주는 사탕의 개수는 고정되어 있다. M개의 사탕을 줄 수 있고, 각 사람들이 원하는 사탕의 개수 총합을 SUM 이라고 할 때 못 주는 사탕의 개수 = SUM - M - 위에서 못주는 사탕의 개수로 공략한다. 이 때, 분노게이지를 낮추기 위해선 한..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B�� www.acmicpc.net 이분 탐색 문제인데 정답률에 비해 난이도는 높았었던 문제. 진짜 생각이 안나서 해설을 참고했었다. 핵심은 이거다. - 정렬된 배열 : K번째에 해당할 것 같은 수 (행렬 내 범위. 1 ~ K) *** 최댓값을 n * n 이 아닌 K로 잡는 이유는 K번 째에 해당하는 수는 절대 K를 초과하지 않기 때문에 탐색 시 시간 절약을 위해서다. *** K를 초과하지 않는 이..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 문제 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 �� www.acmicpc.net 이진 탐색 문제이다. 한글 번역이 헷갈리게 되어있어 문제 풀이 또한 헷갈렸었다..ㅠㅠ 하지만 타 문제에 비해 어렵진 않았던 문제. 핵심 - 돈이 남아도 횟수(M) 를 채우기 위해 넣고 빼기 가능. -> 이 말은 즉슨, M번 이하만 채워도 M번과 동일하게 임의로 넣고빼면서 맞출 수 있다. -> M번 이하인 인출 비용 중 최솟값 구하기. - 정렬된 배열 : 인출 금액 (1원 ~ 최대 사용 금액 * M ..

안녕하세요. 이는 면접 대비 맞춤 포스팅입니다. 그럼, 바로 진행하겠습니다. 삽입 정렬이란 ? - 손 안의 카드를 정렬하는 방법과 유사한 알고리즘이다. - 처음에는 두 번째 원소부터 시작하는데, 해당 원소를 꺼내든다. 그 후, 그 앞의 원소들과 하나씩 비교하여 삽입할 위치를 정한다. *** 만약, 앞의 원소보다 크기가 크면 종료한다. - 종료 시 그 지점에 원소를 넣고, 나머지 원소들은 한 칸씩 뒤로 밀려난다. - 장점 -> 배열 원소의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 정렬들보다 유리할 수 있다. -> 대부분의 원소가 정렬된 상태에서는 매우 효율적일 수 있다. (이는 선택, 삽입, 버블 정렬 한정) - 단점 -> 비교적 많은 원소들의 이동을 요구한다. -> 원소 수가 많고 원소 크기..

안녕하세요. 이는 면접 대비 맞춤 포스팅입니다. 그럼, 바로 진행하겠습니다. 버블 정렬이란 ? - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. - 인접한 두 원소를 검사하여 크기 순서를 맞춘다. (SWAP) - 장점 -> 구현이 매우 간단함. - 단점 -> 일반적으로 SWAP(원소 자리 바꿈)이 MOVE(이동) 보다 복잡하기 때문에 거의 쓰이지 않음. -> 시간복잡도가 정렬 알고리즘 중 가장 높다. (비효율적) *** 시간복잡도 == Best : n^2, Avg : n^2, Worst : n^2 알고리즘 간단코드 -> 이런 방식으로 두 개의 for문이 필요하며 내부에는 SWAP을 진행함. 알고리즘 그림설명 코드를 바탕으로 진행되는 버블 정렬이다. 1) 인접한 두 원소 선택해서 크기 비교 -> 큰 ..

https://www.acmicpc.net/problem/3079 3079번: 입국심사 문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관�� www.acmicpc.net 이진 탐색 문제이다. 중요한 점이 있다면 심사대가 비었다고 바로 심사받는 것이 아니라, 자율적으로 쉬면서 바로 안가도 된다 는 것이다. 그렇기 때문에 이진탐색을 사용한다. - 정렬된 배열 : 모든 M명이 심사받는 데 걸린 시간 (1초 ~ 심사 최장 시간 * M명 초) - 구하는 방법 : mid 초 / 각 심사대 심사 시간 -> mid 초 내에 해당 심사대에서 심사받을 수 있는 최대 인원 수 - 그래서,..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 이진탐색과 BFS가 섞인 문제이다. 구하려는 값 : 두 공장의 이동중량 최댓값. 두 공장의 이동중량 : A공장에서 B공장까지 이동하는데 A공장에서 싣은 무게로 B공장까지 갈 수 있는 무게를 뜻함. 범위가 극도로 넓고, 시간 제한이 1초 이며 최댓값을 구하라는 뜻은 한 값이 아닌 여러 값이 정답으로 나올 수 있다는 뜻 이기 때문에 이진탐색을 사용했다...