본문 바로가기

백준 문제 풀이

 (152)
백준 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차원 배열로 만들어서 풀이했는데 이것도 좋은 방법이다. 그러나 난 문제가 시키는대로 풀이했다. 이번에는 별..
백준 7579번 앱 (C++) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제를 보면 어떻게 접근해야할지 어려울 수 있다. 나도 처음에 dp라는 알고리즘 분류를 못봤다면 매우 어렵게 풀었을 것이다. 이 문제를 배낭 문제라고 판단해야할 프로세스는 다음과 같다. 1. 모든 경우의 수를 따져봐야한다. 그렇다면 경우의 수를 따질 수 있는 알고리즘을 검토한다. 2. 재귀, dfs 백트래킹, 브루트포스, dp - 재귀: N이 100이므로 사용할 수 없다. - dfs 백트래킹: 마찬가지로..
백준 11729번 하노이 탑 이동 순서 (C++) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이탑은 재귀문제에서 가장 기본적인 문제로 대학 강의에서 처음 배우게 된다. 그러나 나름 어려운 편이고 기본기를 정확히 하자는 의미로 하노이탑을 풀어봤다. 접근법 하노이 탑의 가장 기본적인 요소는 높이가 4인 하노이탑을 3번 막대로 옮기기 위해서는 맨아래 판을 제외하고 높이 3인 탑을 2번 막대로 옮기는 순서가 필요하다. 그러므로 Hanoi(4) -> Hanoi(3) 이렇게 포함이된..

티스토리툴바