택시짱의 개발 노트

링크 https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간 www.acmicpc.net 풀이 지훈이가 불이 도달하기 전에 미로를 탈출할 수 있는지 없는지를 구하는 문제이다. 최단경로를 찾는거기 때문에 먼저 BFS를 이용하여 문제를..

링크 https://programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 구하는 문제이다. 문제를 보았을 때 DFS, BFS 둘 중에 한 개로 탐색을 해야 된다는 것을 알 수 있습니다. 그런데 일단 노드간에 사이클이 있기 때문에 DFS를 이용하여 탐색을 하게되면 1 - 3 - 4 - 2 - 5와 같이 탐색을 진행할 수 있어 가장 멀리 떨어진 노드를 구하기가 쉽지 않아 집니다. 그러므로 BFS 탐색을 이용하여 노드를 하..

링크 https://programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제이다. 먼저 선수간의 승패로 방향 그래프 2개를 만들 었습니다. 첫 번째 그래프는 내가 이긴 사람으로 향하는 그래프, 두 번재 그래프는 내가 진 사람으로 향하는 그래프, 그리고 문제에서는 선수의 수가 100이하 이기 때문에 그래프에서 최단 거리를 구하는 알고리즘 ..

링크https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODESW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com풀이 상원이가 친구들에게 줄 수 있는 초대장의 개수를 구하는 문제이다. 상원이가 초대장을 줄 수있는 경우는 친한친구와 친한친구의 친한친구 까지 줄수 있다. 이때 저는 친한 친구의 친한 친구를 어떻게 찾아야 될까 고민하다 dfs나 bfs를 이용하여 친구의 친구를 찾으면 되겠다 생각했습니다 그래서 친한 친구들을 인접리스트로 ..

링크 https://programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 문제이다. 먼저 구명보트를 효율적으로 이용하여 사람을 구출하는 방법을 생각해야 되는데 효율적인 방법은 구명보트가 수용 가능한 무게에 최대한 가깝게 사람을 태우면 된다. 어떻게 해야 효율적인 무게를 찾을 수 있을까 저는 사람들의 무게를 오름차순으로 정렬을 하고 무게가 가장 작은 사람과 무게가 가장 큰 사람을 함께 보트에 태울 수 있는지..

링크https://programmers.co.kr/learn/courses/30/lessons/64062프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이 디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 구하는 문제이다. 먼저 돌의 높이만큼 친구들을 한 번씩 건너게 해서 몇 명의 친구들이 건너갈 수 있는지 찾을 수 있다.그런데 돌의 높이가 2억까지 되기 때문에 효율성 테스트에서 틀릴 확률이 매우매우 높게 된다. 그래서 이분탐색을 이용하여 ..

링크 https://programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 각 고객에게 배정되는 방 번호를 순서대로 배열에 담는 문제이다. 아마 union_find (disjoint_set) 알고리즘을 알고 계신 분들은 문제 접근에 어려움이 없지 않았을까 라는 생각을 했습니다. 일단 전체 방의 개수가 k개인데 k는 10의 12 제곱 이하이다. 그러므로 방의 개수대로 배열을 만드는 것은 불가능하다는 것을 알 수 있다. 그래서 map을 이용하여 고객이 배정받은 방을 저장할 수..

링크 https://programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 당첨에서 제외되어야 할 제재 아이디 목록은 몇 가지 경우의 수가 가능한 지 구하는 문제이다. user_id와 nanned_id 배열의 크기가 최대 8 이하 이므로 완전 탐색을 이용하여 모든 가능한 조합을 구해서 풀면 될 거 같았다. 그래서 dfs(백트래킹) 를 이용하여 하나씩 비교를 하도록 했다. 일단 user_id와 banned_id의 목록의 길이가 같아야 비교를 할 수 있고 길이가 같다면 문자열..