tony9402

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

3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 길이가 $K + 1$인 $[l, r]$ 구간을 잡고 슬라이딩 윈도우로 보면서 $[l, r]$ 구간에서 $l$ 번째와 문자열의 길이가 같은 것의 개수를 세주면 된다. import sys def input(): return sys.stdin.readline().rstrip() N, K = map(int, input().split()) S = [input() for i in range(N)] cnt = [0 for i in range(21)] an..

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으로 작기 때문에 결론적으로 보면 큰 문제가 없는 솔루션이다. 내가 생각하는 좋은 풀이는 한칸씩 이동하면서 체크하는 방식이 아닌 거울을 설치해서 빛의 이동방향이 바뀌기 전까지 쭉 보면서 계산하는 방식으로 하는게 좋은 풀이..

22949번: 회전 미로 탐색 $4k$×$4k$의 크기인 미로가 있다. 이 미로의 최상단 왼쪽을 $(1, 1)$, 최하단 오른쪽을 $(4k, 4k)$로 하자. $\{(y, x) | 4×i < y ≤ 4×(i+1), 4×j < x ≤ 4×(j+1), (0 ≤ i, j < k)\}$ 를 만족하는 영역이 하나의 구역으 www.acmicpc.net (내가 만든 문제라 해설이 길다... 다른 문제는 간단히 쓸 예정...) 내가 만든 문제이다. 배열 돌리기와 미로 탐색을 적절히 섞으면 적당한 난이도가 나올 것이라 생각하고 만들었지만 실제 찍힌 티어는 골드 1 ~ 플레 5 정도였고, 지금까지 푼 사람이 8명 밖에 없다... 지문 쓰는 능력이 그렇게 좋은 편(사실, 아직도 좋은 편이 아닌거 같다)이 아니여서 행렬에서 ..

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

학습 돌릴 거 돌리다가 무의식적으로 백준을 들어갔더니 새로운 문제가 쏟아졌다. 그중에 주사위 굴리기 2라는 제목을 보고 뭔가 삼성 기출인 거 같아서 한번 풀어봤다. 역시 주사위 전개도가 주어지고 이를 잘 돌려야하는 문제이다. 노가다로 할 수도 있겠지만.... 이런 문제 같은경우는 인덱스를 잘 활용하면 좀 더 수월하고 실수 없이 풀 수 있다. 위 그림 중 왼쪽 그림은 주사위 전개도에서 각 면에 인덱스를 붙인 사진이고 오른쪽 사진은 각 면이 어떤 방향을 바라고 보고 있는지 적어놓은 것이다. 위 그림은 문제에서 주어진 주사위 전개도 모양이다. 이를 잘 이용해서 동서남북 방향으로 어떻게 변화하는지 체크를 한 후 코딩만 하면 된다. 아래 4개의 그림들은 위 전개도에서 동서남북 방향으로 이동했을 때 변화된 전개도의..

톡방에서 얘기를 하다가 갑자기 블로그에 써놔야겠다는 생각이 들어서 작성하게 되었다. (다시 보니 저기에서 ^가 빠졌긴 했지만 그래도 올바르지 않은 문법이다.) 위에 있는 답변을 많이 볼 수 있는데 올바르지 않은 문법이다. 아래 올바른 문법이랑 올바르지 않은 문법을 적어놨다. char ch[10000]; scanf("%[^\n]", ch); // 올바른 문법 char ch[10000]; scanf("%[^\n]s", ch); // 올바르지 않은 문법 자세한 내용은 아래 링크를 확인하면 된다. http://www.cplusplus.com/reference/cstdio/scanf/ scanf - C++ Reference function scanf int scanf ( const char * format, ....

(소스코드 중요 부분만 있습니다.) A. Dislike of Threes Tag : 구현 Time Complexity : 전처리 $O(1666)$, 테스트 케이스 당 $O(1)$ 3으로 떨어지는 수와 수의 일의 자리에 있는 숫자가 3인 경우를 제외한 나머지의 개수를 세면 된다. 입력으로 주어지는 수의 범위는 1000까지이므로 수가 1000개 뽑힐때까지 전처리하면 된다. (전처리 안 해도 충분히 돈다.) vector v; bool chk(int x) { if(x % 3 == 0) return false; x %= 10; if(x == 3) return false; return true; } int main(){ fastio(); for(int i = 1, cnt = 0; cnt < 1000; i++) { ..

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