알고리즘 모음(C++)

문제 링크입니다! https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net DFS를 이용한 선택 + BFS를 이용한 탐색이 합쳐진 문제였습니다(연구소 문제의 심화문제 느낌이였습니다.) DFS에서 주의할 점이 Green, Red를 선택해야 하는데 겹치면 안된다는 것이였습니다. 따라서 저는 Green -> Red 로 선택해줬습니다. 예를들어 1, 2, 3, 4칸에 배양액을 놓을 수 있고, 초록색, ..

문제 링크입니다! https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net 간단한 BFS 문제였습니다. N -> G까지 A or B 연산을 통해서 최소 몇번을 통해서 갈 수 있는지를 물어보는 문제입니다. 99999보다 작다는 조건만 해주면 쉽게 풀 수 있는 문제였습니다. 문제 접근 방법 1. N에서 시작해 A, B 연산을 했을 때의 값을 찾는다. 2. 값들이 99999보다 작을 때, 이전에 방문하..

문제 링크입니다 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 1과 같이 DFS를 통해서 선택, BFS를 통해서 탐색을 하는 문제였습니다. 문제 조건과 출력예시는 위 링크를 참고해주세요! 문제 접근 방법 1. 입력과 같이 바이러스의 위치와 빈칸의 갯수를 저장한다. 2. 빈 칸의 갯수가 1개 이상일 때, 바이러스를 M개 만큼 선택해준다. 3. 바이러스가 M개 선택되었다면, BFS 탐색을 통해서 바이러스를 확산시킨다. 4. 빈 칸이 없다면 T를, ..

문제 링크입니다 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net BFS를 이용한 문제였습니다! 3차원 배열을 만든뒤, 0~8초까지의 벽의 움직임을 담고, 9방향 탐색을 하면 되는 문제였습니다. 문제 접근 방법 1. 벽의 위치를 vector를 이용해 저장합니다. 2. 벽의 갯수가 0개라면 1출력, 아니면 탐색을 시작합니다. 3. 0~8초까지 저장한 벽의 위치를 이용해 N초가 지났을때의 벽의 위치를 저장합니다. 4. 9방향 탐색을 통해서..

1000점 만점중 820점으로 통과했습니다. 시험에 대해서 간략하게 말씀드리면 10문제를 90분 안에 풀어야하며, 완전 구현 3문제, 간접 구현(빈칸 채우기, 틀린 곳 찾기) 7문제 있었습니다. 10문제에 90분에서 아셨겠지만, 삼성 SW 테스트 정도 난이도나 백준 골드 티어 난이도 문제가 1문제도 나오지 않습니다. 오히려 백준 실버 4 ~ 5, 알고리즘 완전 기초 문제들로만 구성되어 있습니다. 그래도 귀찮은 문제는 1개 정도는 있습니다. 그 문제는 안풀어도 통과이기에 패스하고 일찍 나왔습니다.( 검토 포함 40분~50분 정도 걸렸습니다.) 제 solved.ac 등급입니다. 보시려는 분 중에 티어가 골드만 되셔도 쉽게 통과할 수 있을 겁니다.(알고리즘을 알고있다는 전제하에) 팁을 간단하게 말하자면 DP,..

문제 링크입니다 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제였습니다. "RGB 거리1" 과는 다르게 N번과 1번의 색깔이 달라야한다는 조건이 추가되었습니다. 따라서 1번 집에 R,G,B를 선택했을때를 전부 확인한뒤, 최솟값을 비교해주면 됩니다! 문제 접근 방법 1. 1번 집의 R,G,B를 순서대로 선택한다. 2. R을 선택했을때 -> 2번 집의 G,B만 값을 구하고, R의 값에는 매우 큰 값을 넣는다. ..

문제 링크입니다 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net DFS를 통해서 벽을 선택한후, BFS를 통해서 탐색하는 문제였습니다. (문제는 너무 길어서 생략하겠습니다) 문제 접근 방법 1. 입력을 받음과 동시에 빈칸을 저장한다. 2. 빈칸 중에서 3개를 순차적으로 고른다. 3. 고른 빈칸에 벽을 세운뒤 BFS 탐색을 통해서 바이러스를 퍼트린다. 4. 안전 영역을 구한다. 5. 벽이 전부 선택될 때까지 반복한다. 문제 접근 방법 - 1번 for (int..

문제 링크입니다 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문자열을 사용한 BFS 문제였습니다 N을 입력받아서 K번 수를 바꾼뒤 최댓값을 출력하는 문제입니다. N을 자릿수를 바꿔야하기에 string으로 선언해서 문자열로 사용했습니다. 문제 접근 방법 1. 수의 위치를 바꿀 수 없을 경우를 찾아서 -1를 return 해준다. 2. 수를 K번만큼 바꾼 뒤, 최댓값을 찾아서 출력해준다. 문제 접근 방법 - 1번 if (N.size() == 1 || (N.size() == 2 && stoi(N) % 10 == 0))..

문제 링크 입니다 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net https://junseok.tistory.com/23 이 문제의 심화 문제 입니다. 백준 12015 - 가장 긴 증가하는 부분 수열2(복습) 문제 링크입니다 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다...

문제 링크입니다 https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net https://junseok.tistory.com/73 백준 2353 - 반도체 설계(C++) 문제 링크입니다 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 junseok.tist..

문제 링크입니다 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 선을 꼬이지 않고 연결할 수 있는 최대 갯수를 구하는 방법 위와 같이 연결되어 있다고 했을 때 1. 왼쪽을 기준으로 오름차순 정렬을 한다.(문제에선 이미 되어 있음으로 생략) 2. 오른쪽 수열에서 가장 긴 증가하는 부분 수열을 찾는다. ex) 4 2 6 3 1 5 -> 2 3 5 https://junseok.tistory.com/23 와 비슷한 lower_bou..

문제 링크입니다 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 가장 긴 증가하는 부분 수열 o(n log n) 문제였습니다. 저는 lower_bound를 구현했습니다! 문제 접근 방법 1. 수열을 입력받은 뒤 오름차순으로 정렬한다. 2. vector에 arr[0]의 값을 입력한 뒤, lower_bound를 실행한다. 3. vector의 크기를 출력한다. 4. 1번~3번을 반복한다. 문제 접근 방법 - 2번 void binary_search(..