본문 바로가기

백준 문제 풀이

 (152)
백준 13023번 ABCDE (C++) https://www.acmicpc.net/problem/13023  백트래킹을 연습하기에 좋은 문제이다. 백트래킹은 모든 경로를 검색하며 1번 노드를 방문하고 여기가 아니면 돌아가는 식으로 이뤄지는 알고리즘이다. 코딩테스트에도 빈출이니 철저히 연습해놔야한다. 백트래킹은 완전탐색에 자주 사용되고 유연하게 사용할 수 있어야한다.  이 문제는 결국은 어떤 정점에서 시작할 때 시작하여 최대 노드의 개수가 자신을 포함해 5개라면 정답이된다. 가지를 쳐내면 된다. 그런데 사실 이렇게 생각을 처음에는 했지만 이러면 결국 모든 정점에서 백트래킹을 해야하는데... 시간초과가 안날수가 없는데 안나더라...? 대체 왜 안나는 걸까 #include #include using namespace std;vector graph[..
백준 7682번 - 틱택토 (C++) https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 두가지 풀이법이 있다. 틱택토의 모든 조건을 따져 지금 들어온 틱택토가 유효한지 확인하는 방법과 모든 시뮬레이션을 해보고 들어온 틱택토가 있는지 확인하는 방법이다. 이전의 방법은 많은 블로그에서 소개하고 있기 때문에 난 두번째 방법으로 해보았다. 시간 복잡도는 9^9 로 충분히 가능하다. 그리고 문자열을 방문표시해야하는 짜증이 있었는데 이것을 셋으로 표현했다. 맵으로 표현했을 때 안되는 이유가 ..
백준 - 3687번 성냥개비 (C++) https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 개인적으로 이런 문제를 굉장히 싫어한다. 못풀면 그냥 내 능지문제가 되는 것 같은 문제들.. 하지만 문제를 편식해선 좋은 개발자가 될 수 없다! 무튼, 이 문제는 특이하다. 최대 개수는 그리디로 최소개수는 dp로 구해야한다. 이러한 유형의 문제는 먼저 문제의 조건에 맞도록 수를 나열해보면서 규칙을 찾거나 풀이법을 고민하는 것이 올바른 방법이다. 1개로는 아무것도 만들 수 없으니 스킵한다. 성냥개수 가장 ..
백준 - 4179번 불! (C++) https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 이 문제를 읽고 생각났던 것은 3차원 배열을 선언하여 그 상태 자체를 확인해야한다고 생각했다. 그러나 그러지 않아도 되었다. https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는..
백준 17835번 - 면접보는 승범이네 (C++) https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 처음보는 유형의 다익스트라였다. 파티 문제처럼 역방향을 받아 다른 노드까지의 거리를 구하는 문제는 접한적이 있었기 때문에 핵심 아이디어는 캐치할 수 있었으나, K의 범위가 결국 N까지 올라올 수 있기 때문에 K번 다익스트라 처리를 하면 시간초과를 받을 수 밖에 없다. 여기서 처음 본 테크닉은 처음 다익스트라를 시작할 때 하나의 지점만 넣고 시..
백준 - 1525번 퍼즐(C++) https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 퍼즐의 모든 상태를 queue에 넣어서 관리하는 것이 관건인 문제이다. 퍼즐을 2차원 배열이나 벡터로 만들어 관리하면 되는 문제이지만 이렇게 진행할 경우 방문처리를 진행하는 것이 쉽지 않고 무엇보다 이 문제는 메모리를 상당히 조금 주기 때문에 메모리 초과가 날 가능성이 매우높다. 먼저 방문처리는 겨우 3x3배열이기 때문에 9자리라서 문자열을 사용한 map을 사용하였다. (set도 가능하다. set이 더 좋을듯.) 그리고 중요한 퍼즐관리인데, 퍼즐을 2차원 벡터로 보관하지말고..
백준 1823번 수확 (C++) https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 비슷한 문제를 몇 개 풀어본적이 있어서 비교적 쉽게 풀 수 있었다. 최댓값을 보고 생각해야하는 것은 bfs이다. 그러나 N의 개수를 보고 빠르게 접는다. 양방향을 보고 생각해야하는 것은 투포인터, 이분탐색, dp이다. 그리고 모든 방법을 고려해야하기 때문에 이분탐색과 투포인터는 제외시켜야한다. 그래서 남는 선택지는 dp이다. 두가지 선택지가 존재한다. 앞을 먼저 수확하거나 뒤를 먼저 수확하거나. 이것을 코드로 바꿔보면 dp[left..
백준 9024번 두 수의 합(C++) https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 문제를 보자마자 이분탐색 투포인터가 떠올라야한다. 난 누적합도 떠올랐는데 이 문제는 모든 조합을 확인하면 TLE임을 알았고 간격의 차이에 따라 계산을 걸러낼 수 있는 양 끝 시작 투포인터를 사용해야한다고 생각했다. 2 3 10 14 29 가 있다고 하자. 그렇다면 두 수의 합은 lo++를 할 수록 커지고 hi-- 할수록 작아진다. 그러므로 두 수의 합이 k보다 작다면 더 크게 만들어 줘야하니까 lo..

티스토리툴바