tony9402

1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 이 문제는 주어진 문자열 순으로 구현을 하면 되는 문제이다. 주어지는 문자열의 최대 길이는 50으로 101x101 크기의 배열을 만들어 (50, 50)에서 출발하여 주어진 문자열 대로 이동하고 방문한 점을 .으로 방문하지 않은 점을 #으로 출력하면 된다. 미로를 출력하는 범위는 .을 포함하는 가장 작은 직사각형의 크기 및 위치를 관리하면 된다. import sys def input(): return sys.stdin.readline().rstrip() N = ..

4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 로봇 청소기의 시작 위치, 더러운 칸을 정점으로 잡아 새로운 그래프를 만들어 TSP를 해결하면 되는 문제이다. 정점의 개수는 11개(로봇 청소기 위치 + 더러운 칸의 개수)이기 때문에 11!(=39,916,800)가 작아 완전탐색을 돌릴 수 있다. 간선은 A에서 B로 이동할 때 거리를 의미하므로 이 부분은 BFS로 미리 구해놓으면 된다. 아래 코드는 TSP를 계산할 때 완전탐색을 이용하였다. 이를 더 빠르게 돌아가게 하고 싶다면 TSP 관련 알고리즘을 공부하고 적용하면 ..

2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 주어진 집에 대한 정보에서 '!'에 거울을 45도로 설치하여 '#'에서 다른 '#'으로 빛이 이동할 수 있도록 해야한다. 이때, 설치할 거울의 최소 개수를 계산하면 된다. 아래 코드는 좋은 코드가 아니다. 이 문제는 N의 제한이 50으로 작기 때문에 결론적으로 보면 큰 문제가 없는 솔루션이다. 내가 생각하는 좋은 풀이는 한칸씩 이동하면서 체크하는 방식이 아닌 거울을 설치해서 빛의 이동방향이 바뀌기 전까지 쭉 보면서 계산하는 방식으로 하는게 좋은 풀이..

꾸준히 블로그를 쓰기 위해 간단한 백준 문제를 풀고 풀이를 간단히 올리려 한다. 5545번: 최고의 피자 첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄 www.acmicpc.net N가지의 토핑을 적절히 선택하여 단위 금액당(1원 당) 열량이 가장 높은 값을 찾는 문제이다. 문제 상에서 "최고의 피자"는 단위 금액당 열량이 가장 높은 값을 의미한다. 모든 토핑의 가격은 B원으로 토핑의 열량이 가장 큰 것부터 보면서 "최고의 피자"를 찾으면 된다. 토핑을 추가할 때 값이 떨어진다면 해당 토핑 전까지만 선택하면 된다. ..

올해 소프트웨어 마에스트로 11기 활동이 끝나고 활동 중에 못했던 알고리즘, 자료구조 공부를 하고 있다. 몇일 전에 트라이 자료구조를 공부하려고 공부하고 트라이 관련 문제를 쭉 풀었다. 이 글은 내가 공부했던 것을 정리하는 글이다. (난 트라이 이론을 정리는 안하고 트라이 구현 및 문제 풀이 위주로 작성한다.) 이 글에서는 트라이를 맨 처음에 짠 코드에서 최적화 시킨 코드까지 어떤 과정을 거쳤는지 정리한다. 1. 포인터를 이용한 구현 with map 처음부터 간단하게 짜기 힘들다. 포인터를 이용해서 먼저 직접 짜보는게 좋다. 나도 트라이 이론만 보고 혼자 포인터를 이용해서 짰었다. 빌드 과정은 완전한 O(NL)이 아니라 map을 사용하기 때문에 log 26 (더미노드 없다고 생각하면) 정도가 붙겠지만....

백준에서 알고리즘 풀다가 최근에 다시 코드포스를 참가하면서 느낀점은 CP 실력이 더더욱 나빠졌다는 것이다. 따라서 실력을 상승시키기 위해 난이도를 정해놓고 빠른 시간에 풀 수 있도록 연습을 하려 한다. 처음은 간단하게 난이도 1000 ~ 1400 정도의 문제를 2시간 제한시간을 주고 풀기 시작하고 점차 너무 쉽거나 난이도를 올려도 될때는 문제 수를 늘리거나 난이도를 상향하여 계속 진행할 것 같다. [문제] Codeforces 1385 C [문제 유형] Greedy [시간복잡도] $O(n)$ [풀이] 배열 A에서 A의 접미사 ( $1 \le i \le n, ; [ a_{i} , a_{i+1} , ... , a_{n}]$ ) 중 $a_{i} \le a_{i+1} ... a_{i+k} \ge a_{i+k+1}..

이 글은 지속적으로 업데이트가 될 예정입니다. 알고리즘 공부를 제대로 해보려고 한다. 공부를 시작하기 전에 들어본 적 있는 자료구조 및 알고리즘을 나열해보려고 한다. 간단한 종류로 나눈다면 아래와 같다. 문자열 수학 트리 그래프 정렬 다이나믹 프로그래밍 네트워크 플로우 아래 Bar는 내가 아는 정도를 표시하는 것이다. 문자열 KMP 알고리즘 라빈카프 알고리즘 트라이(Trie) 아호코라식 접미사 배열(Suffix Array) Z 알고리즘 Hashing LCP Manacher 트리 트리 순회 이진 검색 트리 우선순위 큐 유니온 파인드 세그먼트 트리 펜윅 느리게 갱신되는 세그먼트 트리 머지소트 트리 세그먼트 트리 비츠 스플레이 Persistent Segment Tree LCA(최소 공통 조상) Heavy-Li..

SCCC 스터디 5일차 1月 16日 (수학 어렵다.........................) 1. 수학1 에라토스테네스의 체 - N 이하의 소수를 빠르게 찾는 알고리즘이다. 소수의 배수를 없애는 방식으로 진행한다. 자세한 내용은 여기에서 참고하면 될 것이다. 이 방법을 이용하면 시간복잡도는 O(n log log n)이다. 유클리드 호제법 - 최대공약수(GCD)를 빠르게 구하는 알고리즘이다.나머지 연산을 이용해서 빨리 구할 수 있는데 이에 대한 자세한 내용은 여기에서 참고하면 될 것이다. 에라토스테네스의 체 - 소수인지 판별하는 방식은 거의 동일하지만 소스코드를 작성할때 살짝 다른게 있다. 다른 곳에서 계산과정 중 오버플로우를 방지하기 위해서 사용한다고 들었다. - 에라토스테네스 1. 에라토스테네스의 ..

SCCC 스터디 5일차 1月 15日 오늘은 미세먼지로 인해 전날 스터디 모임이 취소가 됬다. 그래도 배울 내용은 적어 홈스터디로 진행됬다. 1. 분할정복 분할정복은 Divide and Conquer로 문제를 같은 유형의 여러 작은 문제들로 나눈 뒤, 그 작은 문제들의 답을 이용해서 문제를 해결하는 방식을 말한다. 분할정복을 이용하면 시간 복잡도를 줄일 수 있다. 예를 들어, 1부터 100까지 더하는 것을 공식을 이용하지 않고 더한다면 아주 간단하게 O(n)로 더할수는 있다. 하지만 분할정복을 이용하면 O(log n)으로 더 줄일 수 있다. 1 + 2 + 3 + ... + 51 + 52 + 53 + ... + 99 + 100 이를 한번 Divide(분할)을 해보자. 1 + 2 + 3 + ... + 50 +..

C++ 환경에서 코딩을 하면 STL이라는 것을 사용할 수 있다. STL에는 queue가 기본적으로 만들어져있다. 또한 이 queue을 상황에 따라 편하게 선언을 할 수 있다.STL을 이용하여 n을 입력받고 1부터 n까지의 값을 queue에 넣고 queue에 있던 모든 값을 출력해보는 간단한 소스코드를 작성해보자. 12345678910111213141516171819202122232425#include#include using namespace std; queue q; int main(){ int n; cin >> n; //scanf("%d",&n); for (int i = 1; i