간타타 공부장 간타타 공부장

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 visited = [[False for i in range(101)] for j in range(101)] res = 0 def get_dist(point1, point2): return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]) def dfs(r, c, dist, count): global res if res < dist: return if len(points) == count: re..

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 1, 관심이 있는 정보는 어차피 skill 문자열에 있는 문자들이기 때문에 조사하고자 하는 문자열을 순회하여 skill에 있는 문자들만 뽑아내고 skill에 있는 인덱스를 벡터로 다시 만들어서 조사를 한다. 2, 벡터를 순회하면서 인덱스 숫자가 순차적으로 늘어나는지 확인한다. #include #include using namespace std; vector renewal(string skill, string search) { vector result; int str_size = search.size(); for (int i = 0; i < str_size; ..

programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 어떠한 사람들은 4차원 배열을 통하여 해결하였으나 나는 비트마스킹을 이용하여 문제를 해결하였다. 1, 해당 위치에서 이미 지나간 길의 정보를 저장하여야 하는데 map 이차원 배열에 해당 위치에서 위로 간 경우 1, 아래로 간 경우 2, 왼쪽으로 간 경우 4, 오른쪽으로 간 경우 8 을 저장하여 주고 & 연산자를 이용하여 지금 해당 위치에서 이동하려고 하는 길이 이미 지난 길인지 판별을 해 주웠다. *주의 할 점 - 지금 위치와 다음 위치 둘 다 이미 지나간 길에 대한 정보를 갱신 - 범위를 넘어 섰는지 확인 소스코드 #include #include usin..

programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 요즘은 dfs, bfs 단독으로 문제가 나오기 보다는 그래프 탐색을 이용하혀 한번 더 알고리즘 개념을 이용한 문제들이 종종 있는것을 볼 수 있다. 이번에는 그래프 탐색과 MST(최소비용 신장 트리) 개념을 합친 문제를 풀어 보았다. 나중에 프림스 알고리즘과 크루스칼 알고리즘에 대하여도 정리를 하여 포스팅을..

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 생각보다 간단한 문제였는데 고민을 오래했다. *실패한 방법 O(n^2) 풀이법 1, 왼쪽 상단에서 오른쪽 하단으로 이어지는 대각선을 생각하였다.(어차피 대칭이므로 어느 선을 그어도 동일) 2, 정사각형의 왼쪽 하단과 오른쪽 상단의 점을 구한 후 두 점이 대각선의 아래에 있나 위에 있나 판별하여 갯수를 세어줌 => 결론은 시간초과와 약간의 실패 기록들..

programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 1, DP로 풀었을 시 O(n^2)이기 때문에 시간초과 결과로 실패 2, 투포인터 알고리즘을 이용하여 O(N+M)으로 해결 소스코드 #include #include #include #include #include using namespace std; vector solution(vector gems) { vector answer; set jewelry; set search; pair check; map count; int v..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 아이디어 1, 활성화시킬 바이러스들을 next_permutation함수를 이용하여 택하고 bfs방법을 이용하여 퍼지는 시간을 구하였다. 2, 백트레킹 방식을 이용하여 탐색을 하다가 현재 구해놓은 최소 시간 이상 탐색을 실행할 시 실행을 중지하고 다음 케이스를 bfs방식으로 탐색을 하였다. 3, 문제의 조건에서 모든 영역에 바이러스가 있으면 종료가 됨으로(비활성화 된 바이러스도 바이러스다.) 빈칸의 수만큼 ..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 아이디어 1, 상어의 위치, 속력, 이동방향, 크기를 구조체로써 관리하고 현재 상어들을 벡터로써 관리를 하였다. 2, 3가지의 simulation함수를 이용하여 구현을 해 주웠다. 1) 낚시꾼의 이동을 바꾸고 해당 낚시꾼이 있는 위치에서 어느 상어가 가장 위에 있는지 판별 2) 낚시꾼이 상어를 잡고 해당 상어는 관리하는 벡터에서 삭제를 시켜 주웠다. 3) 벡터를 순회하면서 상어..