[백준] 3190번 뱀 Python 문제풀이

주절주절... 최근 기업 코테 공부를 하면서 C++은 아닌 것 같다는 느낌이 팍 들어버렸슴다. 디버깅이 힘듬 문자열 다루기가 힘듬 짜다가 보면 코드 읽기가 어려워짐... 등등.. 또 개발 언어는 대부분 Python인데... C++은 알고리즘만을 위해 공부하는 느낌(?)이 들어서 앞으로는 Python으로 코테 공부를 진행하려 합니다.오늘 풀 문제는 삼성 기출이라고? 하는 백준 3190번 문제입니다. 문제 풀이 1) 뱀이 있는 좌표 표현 - 뱀의 좌표를 Queue를 이용해서 표현했습니다. 뱀의 머리부터 꼬리까지의 좌표를 Queue에 저장 2) 뱀이 이동 - 문제의 조건을 보시면 ' 뱀은 몸길이를 늘려 머리를 다음칸에 위치' 라는 말이 있습니다. 일단 먼저 Queue안에 다음 이동할 좌표를 넣습니다. - 다음..

• format_list_bulleted 알고리즘
• · 2024. 4. 18.

[프로그래머스] 하노이의 탑 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 -..

• format_list_bulleted 알고리즘
• · 2024. 2. 27.

[백준] 9576번 책 나눠주기 C++ 문제풀이

문제 풀이 이번 소마 1차 코테 4번 문제를 시간이 부족해 못풀었는데, 오픈채팅방에서 이분매칭이라는 알고리즘 관련된 문제라고 해서 이분매칭에 대해 공부도 할 겸 풀어보았다. "이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘입니다." - 나동빈 각 사람이 원하는 항목이 정해져 있을 때 모든 사람 각각이 원하는 항목을 하나씩 선택하여 가장 많이 연결되는 경우를 찾는 문제입니다. 위와 같이 A라는 집단에서 B라는 집단의 항목들에 대한 선호도가 있을 때, 어떻게 해야 A집단과 B집단을 연결할 수 있을까를 푸는 문제라고 생각하면 된다.. 문제를 푸는 방식은 맨 위의 사람부터 오른쪽 물건에 대해 연결한다 그리고 2번째 사람이 연결을 하려는데 1번 사람이 1번 물건을 점유하고 있으므로 1번에게 다른 ..

• format_list_bulleted 알고리즘
• · 2024. 2. 26.

[프로그래머스] 두 원 사이의 정수 쌍 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) 이런식으로 자료형 간 형변환시 사용되는 거라고 한다. (처음..

• format_list_bulleted 알고리즘
• · 2024. 2. 22.

[프로그래머스] 달리기 경주 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..

• format_list_bulleted 알고리즘
• · 2024. 2. 13.

[백준] 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번: 최소비용 구하기 첫째 ..

• format_list_bulleted 알고리즘
• · 2024. 2. 4.