본문 바로가기
반응형
SMALL

알고리즘 문제 풀이/Baekjoon

3425, 5373 - 고스택, 큐빙 / 구현능력문제 https://www.acmicpc.net/problem/3425 3425번: 고스택 문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하 www.acmicpc.net https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브.. 더보기
2842 - 집배원 한상덕 (더블 포인터, DFS) https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 www.acmicpc.net 이 문제 진심 개 같아요. 그냥 개 같아요. 문제가 개 같다는건, 극찬입니다. 비슷한 예로 '게임 ㅈ같이 하네' 라는 문구도 상대방.. 더보기
3190 - 뱀 (시뮬레이션) https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 최근 알고리즘 공부의 열기가 식어서... 열을 올리기 위해 쉬운 시뮬레이션 문제를 가져왔습니다. 참 신기한게, 1년 전만 하더라도 푸는데 오래 .. 더보기
1927 - 최소 힙 (Heap) https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. www.acmicpc.net Heap을 까먹은지가 좀 된거 같아서, 다시 공부할 겸 힙과 관련된 쉬운 문제 들고 왔습니다 !! Heap... 다들 아시죠? 우선순위 큐를 만들 때 필요한 자료구조입니다. 항상 헷갈리는 부분이 Heap도 자료구조이고 우선순위 큐도 자료구조인데, 자료구조를 위한 자료구조라.. 더보기
2869 - 달팽이는 올라가고 싶다 (이분 탐색) https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽 www.acmicpc.net 오랜만에 머리쓰는 문제를 풀었습니다. 이분 탐색 문제인데.. 사실 처음엔 이 문제보고 어떻게 이분 탐색이지 고민을 좀 했었.. 더보기
5446 - 용량 부족 (Trie, 정적 풀이) https://www.acmicpc.net/problem/5446 더보기
13505 - 두 수 XOR (Trie) https://www.acmicpc.net/problem/13505 13505번: 두 수 XOR N개의 수가 주어졌을 때, XOR한 값이 가장 큰 두 수를 찾는 프로그램을 작성하시오. 즉, A1, A2, ..., AN 중에서 i ≠ j이면서 Ai XOR Aj 가 가장 큰 것을 찾아야 한다. www.acmicpc.net Trie를 계속해서 조져봅시다. 두 수 XOR, 이 문제는 Trie 문제인 것을 모르면, Trie까지 생각하기 힘든 문제입니다. 저는 심지어, Trie 문제인 것을 알고 봤는데도 어떻게 응용을 해야하는지 하루 내내 생각을 할 정도였어요 ㅠㅠ... 아직 한 참 모자랍니다. 어찌됐건, 이 문제에 어떻게 Trie를 끼얹을 수 있을까요? 결국 XOR이 최대한 크려면, 비교하려는 두 수의 같은 자릿.. 더보기
5670 - 휴대폰 자판 (Trie, 정적 풀이) https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 문제 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드 www.acmicpc.net 대놓고 트라이 써라는 문제입니다. 원래는 동적으로 필요할 때마다 만들어서 문제를 풀려고 했다가, 어차피 프로 시험에서 정적으로 문제 .. 더보기
반응형
LIST

티스토리툴바