chunee

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

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)으로 푸는 방법. 두 가지 모두 살펴보고자 한다. 첫 번째, ..

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; ..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 구현 문제 연습을 위해 5달전에 풀었던 뱀 문제를 다시 풀었다. 어떻게 문제를 풀어야할지는 쉽게 감이 잡히지만 입력값도 많고 변수의 양이 많아 코드를 작성하는데 시간이 좀 오래걸렸다. 1시간 10분정도 걸린 것 같다. 코드 구현은 여러 조건을 고려해야 했다. 고려한 조건을 설명하겠다. N의 크기가 2~100 까지인데 벽까지 고려하여 배열의 크기를 arr[102][102]로 선언하였다. 즉, 만약 N이 1..

https://github.com/ndb796/python-for-coding-test GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com 난이도 하 문제인데 계속 고민을 하다가 정답을 봤다... 생각보다 코드는 짧은데 어려운(?) 문제였다..ㅎ sort(arr.begin(), arr.end()); int target = 1; for (int i =..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 전형적인 dfs, bfs 문제였다. 문제를 읽으며 세로 크기 N 과 가로 크기 M 의 범위가 3~8 사이인 것을 보고 벽이 놓일 수 있는 위치를 모두 구해본 뒤에 그 중 빈칸의 개수가 가장 많은 것을 구해야하는 것임을 알았다. 하지만 벽의 놓이는 경우의 수를 구하는 과정에서 까다로움을 느꼈고, permutation (순열) 이라는 개념을 이용하였다. 이번 문제에서 익힌 개념 next_permutation , ..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제를 읽자마자 bfs 로 풀어야됨을 알고 문제를 바로 풀었다. 하지만 메모리 초과가 계속 나서 배열의 크기를 봤는데 vector로 선언하여 문제 없었다... 그래서 오랜 고민 끝에 중복되는 연산이 있는지 확인하였다. 문제는 했던 연산을 반복하여 연산의 횟수가 늘어나기 떄문이였다. 도시가 도로를 통해 이동할 때 현재 이동한 ..