문제 바로가기 (백준) 완전탐색 문제였고 아직 시간복잡도에 대한 개념이 덜 잡혀있음을 깨달았다. 13Cm의 조합은 100,000을 넘지 않으므로 시간 초과 없이 문제를 해결할 수 있다. (문제에서 치킨집 개수의 범위를 정해준 것은 분명 이러한 이유가 있었기 때문인 점 기억하기!) 13Cm을 파이썬 조합 라이브러리를 이용해 코드를 간결하게 만들 수 있다. 치킨집 중 M개를 고르는 모든 경우에 대해 치킨 거리의 합을 계산하여(완전 탐색) 치킨 거리의 최솟값을 구한다. 1️⃣ 무한대 표현(INF) : 최단 경로 알고리즘에서 도달할 수 없는 노드에 대한 최단 거리 = 1e9 ex. temp = 1e9 2️⃣ 조합(Combination) from itertools import combinations # combi..
기초 100제는 알고리즘 문풀에서 많이 사용되는 기본 코드 유형과 관련된 문제(특히 구현 implementation 관련)들로 이루어져 있다. 자신감을 기르기에 딱 좋은 사이트이다. 🌳 기억하면 좋을 구현 팁들 input().split(':')를 사용하면 입력받은 값을 콜론 ':' 기호를 기준으로 자른다. input().split()는 공백을 기준으로 입력값을 자른다. print(a, b, sep=':')를 사용하면 콜론 ':' 기호를 사이에 두고 a:b 형식으로 값을 출력한다. (sep은 seperator를 의미함) 키보드로 입력되는 것들은 기본적으로 문자열로 인식되고, 문자열끼리 더하기(+)하면 두 문자열이 합쳐 연결된(concatenate) 결과를 만들어 낸다. 10진수 int 형의 숫자를 %x, ..
🧨 백준 9370번 - 미확인 도착지 문제 난이도 : 골드2 (어렵다 어려워) 문제 링크 : www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 #include #include #include #include #include using namespace std; struct edge { int to, length; }; int dijkstra(const vector& graph, int source, int target) ..
🧨 백준 10282번 - 해킹 문제 난이도 : 골드4 문제 링크 : www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 #include #include #include #include #include using namespace std; struct edge { int to, length; }; int cnt = 0; int dijkstra(const vector& graph, int source, int target) { vect..
🧨 백준 1707번 - 이분 그래프 문제 난이도 : 골드4 (낮은 정답률에는 이유가 있다) 문제 링크 : www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 🧨 알고리즘 선택 및 C++ 코드 메모리초과, 런타임에러(Segfault, OutofBounds)에 틀렸습..
🧨 백준 10026번 적록색약 문제 난이도 : 골드5 문제 링크 : www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 유기농배추 문제와 크게 다를 거 없고, 대신 0과 1의 이분법이 아니라 0, R, G, B를 구분해야 하는 정도가 조금 더 난이도 있다고 볼 수 있다. 여태까지 그래프 관련 문제들 계속 BFS로 구현했어서 이번에는 재귀를 사용한 DFS로 구현했다. 조금 어렵다고 생각했는데 막상 짜보니 별거 아닌 거 같다..
🧨 백준 1012번 - 유기농 배추 문제 난이도 : 실버2 문제 링크 : www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 2178번 미로탐색 문제와 비슷하게 2차원 좌표를 이용해 위치 이동을 해야하므로 상하좌우 dx, dy 배열을 사용했다. 재귀를 사용하는 DFS는 뭔가 거부감이 있어서 일단 BFS로 구현했다. (DFS로 짜도 상관없는 거 같다) 처음에 대체 어디에 배추가 있는지 알아야 지렁이를 놓든 말든 할거 아닌가 싶어서 이를 표시해..
🧨 백준 2178번 미로탐색 문제 난이도 : 실버1 문제 링크 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 처음 문제를 봤을 땐 좀 낯설었다. 뭔가 너비우선탐색을 사용하는 거 같은데 어떻게 사용할지 한참 고민했다. 미로에서 칸 이동을 해야 하므로 어쩔 수 없이 상하좌우 대소비교가 들어가야했다. 그래프 탐색을 이용한 문제는 대부분 원하는 값만을 구하려고 하면 어렵게 느껴진다. 갈 수 있는 모든 칸에 대해 지나야 하는 최소 칸 수를 계산해야 (N, M)..
