본문 바로가기

알고리즘

 (82)
[백준] 3190번 뱀 Python 문제풀이 주절주절... 최근 기업 코테 공부를 하면서 C++은 아닌 것 같다는 느낌이 팍 들어버렸슴다. 디버깅이 힘듬 문자열 다루기가 힘듬 짜다가 보면 코드 읽기가 어려워짐... 등등.. 또 개발 언어는 대부분 Python인데... C++은 알고리즘만을 위해 공부하는 느낌(?)이 들어서 앞으로는 Python으로 코테 공부를 진행하려 합니다.오늘 풀 문제는 삼성 기출이라고? 하는 백준 3190번 문제입니다. 문제 풀이 1) 뱀이 있는 좌표 표현 - 뱀의 좌표를 Queue를 이용해서 표현했습니다. 뱀의 머리부터 꼬리까지의 좌표를 Queue에 저장 2) 뱀이 이동 - 문제의 조건을 보시면 ' 뱀은 몸길이를 늘려 머리를 다음칸에 위치' 라는 말이 있습니다. 일단 먼저 Queue안에 다음 이동할 좌표를 넣습니다. - 다음..
[프로그래머스] 하노이의 탑 C++ 문제풀이 문제 풀이 하노이의 탑 문제는 n개의 원판을 1번 기둥에서 3번 기둥으로 옮기는 문제이다. n개의 원판을 (1 -> 3)으로 이동하려면 n-1개의 원판을 (1 -> 2) 로 옮기고, 마지막 원판을 (1->3) ,n-1개 원판을 (2->3)으로 옮기면 된다. 위 처럼 진행 되는 문제이다! 이를 재귀를 통해서 n == 1 일 때 까지 반복해서 풀면 된다. 소스 코드 #include #include #include using namespace std; vector answer; void hanoi(int start, int end, int target, int cnt){ if(cnt == 1){ answer.push_back({start, target}); } else{ hanoi(start, end, 6 -..
[백준] 9576번 책 나눠주기 C++ 문제풀이 문제 풀이 이번 소마 1차 코테 4번 문제를 시간이 부족해 못풀었는데, 오픈채팅방에서 이분매칭이라는 알고리즘 관련된 문제라고 해서 이분매칭에 대해 공부도 할 겸 풀어보았다. "이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘입니다." - 나동빈 각 사람이 원하는 항목이 정해져 있을 때 모든 사람 각각이 원하는 항목을 하나씩 선택하여 가장 많이 연결되는 경우를 찾는 문제입니다. 위와 같이 A라는 집단에서 B라는 집단의 항목들에 대한 선호도가 있을 때, 어떻게 해야 A집단과 B집단을 연결할 수 있을까를 푸는 문제라고 생각하면 된다.. 문제를 푸는 방식은 맨 위의 사람부터 오른쪽 물건에 대해 연결한다 그리고 2번째 사람이 연결을 하려는데 1번 사람이 1번 물건을 점유하고 있으므로 1번에게 다른 ..
[프로그래머스] 두 원 사이의 정수 쌍 C++ 문제풀이 문제 풀이 문제 풀이 자체는 그리 어렵지 않았다. 두 원 사이의 점이기 때문에 xy축 4분면에 동일한 점들이 생길것이다. 그러니깐 하나의 사분면을 구한 뒤 * 4를 해주면 되는 문제였다. for문을 통해 y를 하나씩 증가시키면서 x축상의 점의 갯수를 구했다. 그러나 테스트케이스 7,8,9,10에서 계속 실패해서 뭐지...? 하느라 시간이 오래걸렸다. 이유를 알고보니 y*y를 하는 과정에서 overflow가 발생한것이다. 이를 방지하기 위해 캐스팅이라는걸 사용했는데... 캐스팅이 뭐냐하면 int i = 10; long long c = i; // 묵시적 캐스트 long long c = (long long) i; // 명시적 캐스트 (c-style) 이런식으로 자료형 간 형변환시 사용되는 거라고 한다. (처음..
[프로그래머스] 달리기 경주 C++ 문제풀이 문제 풀이 맨 처음에는 vector의 함수인 find, erase, insert 함수로 풀었는데, 정답은 나오지만 몇몇 테스트케이스에서 시간초과가 발생했다. 어떻게 시간초과를 줄일 수 있을까 고민해본 결과 내 코드에서 find하는 작업과 순서를 바꾸는 erase, insert 작업이 비효율적인 것을 알게 되었다. Player의 순서를 찾는 과정을 HashTable인 map을 이용해 O(1)로 바꾸고 순서를 바꿔주는 과정인 erase, Insert를 swap 함수를 통해 바꾸니 시간초과 없이 모든 테스트케이스를 통과할 수 있었다. 소스 코드 #include #include #include #include using namespace std; map myMap; vector solution(vector pl..
[백준] 1753번 최단경로 구하기 C++ 문제풀이 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 출발점이 명시된 최소 간선 찾기 문제이므로 다익스트라를 이용해 문제를 해결했다. 다익스트라 설명은 이전 문제에 설명했으므로 생략한다. https://itcodeheaven.tistory.com/87 [백준] 1916번 최소비용 구하기 C++ 문제풀이 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 ..
[백준] 1916번 최소비용 구하기 C++ 문제풀이 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 최소 경로 찾기 문제에 자주 사용되는 알고리즘 2개가 있다. 1. 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 정점들간의 최단거리를 계산하는 알고리즘으로 시간복잡도가 O(N^3) 으로 크다. 2. 다익스트라 알고리즘 다익스트라 알고리즘은 한 정점으로부터 다른 모든 정점까지의 최단거리를 계산하는 알고리즘으로 O(ElogV)로 훨씬 빠르다 이 문제..
[백준] 16236번 아기 상어 C++ 문제풀이 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 시뮬레이션 관련해서 구현을 해본 적이 없어 많이 고민했다. BFS를 이용해서 푸는 건 알겠는데, 디테일한 작은 부분부분에서 계속 틀리더라... 풀이는 1) 현재 상어의 위치에서 가장 먼저 1마리를 먹을때까지 BFS를 수행 -> 만약 여러 마리를 먹을 수 있는 경우는 맨 위, 맨 위에서도 맨 왼쪽에 있는 물고기를 먹는다. 2) 1마리를 먹으면 BFS를 종료 후 다시 상어의 위치에서..

티스토리툴바