chunee

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS 와 관련된 문제를 풀다가 알파벳 문제를 풀었다. A~Z 가 26개라는 개념을 알면 쉽게 풀리는 문제였다. 골드 4 문제치고 쉬운 문제지만 시간복잡도 관련하여 정리하고 싶어 글을 작성한다. 백준 내리막길 문제 (1520) 과 굉장히 유사한 문제이다. 내리막길 문제는 DFS 로 문제를 풀려다가 시간 초과의 장벽을 넘어서지 못했다.... 이 이유가 이 문제와 굉장히 유사한 것 같았다. (..

코드를 작성할때 정렬한 후에 중복된 원소의 값을 제거해야하는 문제가 나온다. 이 때 sort, unique, erase 를 사용하여 코드를 짜면된다. (#include 을 선언해야한다.) sort 는 그냥 정렬해주는 함수이다. unique vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수이다. 중복되지 않는 원소들을 앞에서부터 채워나가는 역할을 하기 때문에 남은 뒷부분은 그대로 vector 원소값이 존재한다. 반환 값이 vector의 쓰레기 값의 첫 번째 위치이다. erase erase 함수는 vector 배열에서 특정 원소를 삭제하는 함수이다. 즉 , v.erase(v.begin(), v.end()); 를 하면 v의 원소 모두를 제거해주는 것이다. ( 어디서 부터 어디까지 제거할지..

C++ STL 우선순위큐 라이브러리 #include 선언방식 priority_queue 변수명; -> 선언한 자료형 변수들을 비교함수에 따라 정렬하는 우선순위 큐를 선언 default로는 큰 수부터 작은 수까지 차례대로 정렬하지만 작은 수부터 큰 수까지 정렬하려면 priority_queue pq; 와 같은 방법이 있다. 원래 - 값을 줘서 작은 수 부터 나오게 하는 방법으로 항상 해왔는데 프로그래머스 문제를 풀면서 위와 같은 방식도 알면 좋은 것을 알았다. (밑에 있는 문제) https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr push(element) : 우선순위 큐에 원소를 삽입 pop(..

헤더파일을 사용한다. 기본 생성 방법은 map 변수이름; ex) map s1; ex) map s2; map 에 삽입을 하기 위해서는 insert가 필요하고 pair 객체를 인자로 받아야한다. (key 값과 value는 쌍을 이뤄서) s1.insert(pair(10,20)); s2.insert(pair

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 풀다가 못 풀겠어서 풀이를 봤다... 최장 길이 부분수열(LIS) 문제와 유사한 문제로 개념이 있어야 쉽게 풀리는 문제였다. 풀이는 생각보다 간단하여 금방 풀었다. 최장 길이 부분수열 (LIS) 를 푸는데 2가지 방법이 있다. 첫 번째, 시간 복잡도가 O(N제곱)으로 푸는 방법. 두 번째, 시간 복잡도가 O(NlogN)으로 푸는 방법. 두 가지 모두 살펴보고자 한다. 첫 번째, ..

문제를 풀다가 vector 배열을 비워야 할 경우를 많이 마주쳤다. 이때 바보같이 erase() 함수를 사용해서 하나씩 지웠다...ㅎ vector 배열을 비울 수 있는 함수는 clear #include #include using namespace std; int main() { vector arr; arr.push_back(1); arr.push_back(1); arr.push_back(1); arr.push_back(1); arr.push_back(1); arr.push_back(1); // 배열의 크기6 출력 cout

https://github.com/jungchunkim/python-for-coding-test GitHub - jungchunkim/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - jungchunkim/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전 github.com 최단 경로 문제임을 알고 처음에는 플로이드 방식으로 풀었다. 하지만 입력값이 각각의 칸이 개별임을 알고 다익스트라 방식으로 문제를 다시 풀었다. 하지만 원래 다익스트라는 노드가 1, 2, 3 ....

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 알고리즘 공부를 하다가 소수 찾는 방식이 필요한 문제를 만나 이를 공부하려고 백준 문제를 풀었다. 처음에는 소수 판정을 (만약에 N이라는 수)일 때 소수임을 알기 위해서 2부터 n-1까지의 숫자로 나눠서 파악했다. 하지만 연산량이 너무 많았고 나중에 N 이 커졌을 때는 시간 초과가 나타날 수 있음을 알았다. 연산량을 줄이기 위해 한 가지 수학적인 사실을 알았다. 소수는 2부터 √n까지의 정수로 나눠보면 알 수있다. 이를 이용하여 연산량을 줄여 문제를 풀 수 있었다...

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 처음에 문제를 이분탐색으로 하여 해당되는 숫자를 찾으면 그 숫자의 앞뒤로 같은 숫자가 있는지 확인하였다. 하지만 계속해서 시간 초과를 하여서 다른 방법을 선택하였다.. 생각해보니 이것이 코딩테스트다 Q27에 있는 방법과 같은 방식을 사용하면 된다. upper bound 와 lower bound를 사용하는 방법이다. upper_bound, lower_bound 란?..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐를 이용하는 전형적인 문제였다. 예전에 어디서 푼? 기억이 있어서 금방 풀었다. #include #include #include #include using namespace std; int main() { int N; cin >> N; //우선순위 큐 : 큰 수 부터 priority_queue arr; for (int i = 0; i < N; i++) { int num; ..