본문 바로가기

백준 문제 풀이

 (134)
백준 2073번 - 수도배관공사 (C++) https://www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 www.acmicpc.net 배낭문제임은 금방알아챘으나 문제 해결은 하지 못했다. 먼저, 이 문제를 정석적인 배낭문제처럼 2차원 배열로 해결하려하면 메모리 초과가 난다. 2차원 배낭 문제를 1차원으로 바꿔야하는데, 상당히 까다로웠다. 난이도 조절이 필요할 것 같은데.. 논리적으로 언제 파이프를 갱신할 수 있을지 살펴보면, 두개의 파이프가 딱 D와 맞아떨어질 때 갱신이 가능함을 알 수 있다. 그리고 중요한 건 dp[D]..
백준 1238번 - 파티 (C++) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이 문제는 "맞았습니다" 를 받는 것 자체는 다익스트라 알고리즘을 알고있으면 어렵지 않은 문제이다. 왜냐하면 문제 조건이 그렇게 까다롭지 않다. 1, 2, 3, 4 중 X = 2 라면 1~4까지 모두 다익스트라 알고리즘으로 2까지의 최단거리를 저장하고, 2에서 다른 곳으로 가는 방법들을 다익스트라로 저장하면 된다. 그러므로 노드가 4개이면, X 지점에서 다익스트라 한..
백준 2493번 - 탑 (C++) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 단순히 답만 구하려면 쉬운 문제이다. 그러나 그렇게 풀면 시간복잡도가 O(N^2) 이 되어버린다. 처음에는 큐를 사용하여 6 9 5 7 4 라면 맨 뒤부터 시작해서 큐에 4를 넣고 뒤에서부터 비교하며 7을 만났을 때 => 큐의 모든 값과 비교 4 제거, 7을 큐에 삽입 현재 큐 : ( 7 ) 5를 만났을 때 => 큐의 모든 값과 비교 7 을 놔두고 5를 삽입 현재 큐 : ( 7 , 5 ) 9를 ..
백준 20006번 - 랭킹전 대기열 (C++) https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 처음에는 정렬을 해두고 풀어도 되는 줄 알았는데 순서대로 게임을 진행해야하는 조건이 있었다. (진짜 문제좀 잘 읽자) 그리디 , 구현 문제였다. 처음에는 우선순위큐 문제인가 생각했는데 기준이 달라지는 것이 아니기 때문에 우선순위큐는 필요없다. 나는 게임방의 기준을 rooms 벡터에 담아두고 어차피 순서가 바뀌지 않기 때문에 그 순서대로 다음 레벨을 비교해서 문제를 풀었다. 구현을 연습하는데 좋은 문제..
백준 10159번 - 저울 (C++) https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 이전에 푼 키 순서 문제와 거의 같다. 이렇게 "순서"에 관련된 문제들은 위상정렬도 생각하게 된다. 위상정렬은 inorder와 outorder를 새면서 bfs돌며 순서를 정하는 방식이다. 아무튼, 이 문제에서 플로이드-워셜로 관계 찾는 기법을 복습해보았다. 초기화를 하고 dp를 사용해 각 정점이 경유하여 갔을 때 더 빠르게 갈 수있으면 갱신하는 것이 플로이드 워셜이다. 그..
백준 2458번 - 키 순서 (C++) https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 두 가지 방식으로 풀어낼 수 있다. 1. dfs 2. 플로이드-워셜 1. 먼저 1번 방법을 알아보자. 내 키의 순서를 알 수 있다는 의미는 모든 노드와 연관되어 있다는 뜻이다. 더 풀어보자면 n번 노드에서 출발했을 때 모든 노드를 방문한다는 의미이다. 하지만 이 그래프는 단방향 그래프이다. 그리고 작은 키 -> 큰 키 로 이루어져 있다. 그러므로 두가지 dfs를 진행하는 것이 정 해이다. 작은키 -..
백준 12919번 - A와 B 2(C++) https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 브루트포스, 재귀로 분류되어있는 문제이다. 문자열을 만들 수 있는 케이스는 두개가 있다. 그렇다면 재귀는 다음과 같이 이루어질 것이다. Recusstion(현재 문자열){ if(현재 문자열 == 목표 문자열) 함수종료 Recussiton(A를 더한 문자열) Recusstion(B를 더하고 뒤집은 문자열) } 이렇게 해도 답은 도출할 수 있다. 아마도 이 문..
백준 20055번 컨베이어 벨트 위의 로봇 (C++) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 시뮬레이션 + 구현문제이다. 약간 삼성틱한 문제인데 역량 기출문제는 아니었다. 별다른 알고리즘이 필요한 것은 아니고 그냥 구현이 피곤한 문제였다. 아이디어는 빠르게 떠올렸는데 두 부분에서 해맸다. 1. 2차원배열의 위치 변경 2. 문제를 조금 잘 못 읽음 다른 사람들은 1차원 배열로 만들어서 풀이했는데 이것도 좋은 방법이다. 그러나 난 문제가 시키는대로 풀이했다. 이번에는 별..

티스토리툴바