tony9402

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명 밖에 없다... 지문 쓰는 능력이 그렇게 좋은 편(사실, 아직도 좋은 편이 아닌거 같다)이 아니여서 행렬에서 ..

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

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

운이 좋게 류호석님이 준비하신 코딩 테스트에 검수자로 참여했습니다. 소마 11기 활동을 하면서 검수활동을 시작해보려 했는데 호석님이 절 검수자로 뽑아주셔서 참여하게 되었습니다. 검수는 거의 처음이라 잘 해낼 수 있을지 걱정이 되었지만 하기 쉬운것부터 하나씩 했습니다. 골목 대장 호석 문제의 정해가 이분탐색 + 다익스트라인데 옛날에 최단경로에서 잘못짠 다익스트라로 고통을 받은 기억이 떠올라 다른 분들 소스코드를 보고 그 데이터가 없어서 추가하는 것부터 시작했습니다. (하지만 커팅 등 다른 풀이는 생각못하고 있었네요.. ) 문제를 보고 풀이 실수할만 부분들을 찾아 그 풀이가 통과되는지 등 데이터가 약하지는 않은지, 문제 지문 오류 등을 검수했습니다. 대회에 작은 이슈가 있었지만 이번 대회를 통해 검수할 방향..

[문제] 백준 3025 돌 던지기 [알고리즘] 시뮬레이션 [시간복잡도] $ O(N + R) $ [솔루션] 일단 딱봐도 시뮬레이션을 해야한다. 하지만 단순 시뮬레이션으로 소스코드를 짠다면 $ O(NR) $로 무조건 시간초과이다. 이를 어떻게 줄일지 아이디어를 생각해봐야한다. 아이디어 1 : 돌 던졌을때 직선으로 내려가는 부분을 잘 정리하면 시간초과가 해결될 것 같다. 결론부터 말하자면 이것도 시간초과이다. 벽의 분포로 인해 돌이 지그재그로 떨어지는 경우 돌 던지는 경우마다 $ O(R) $을 갱신하기 때문에 TLE이다. 아이디어 2 : 그렇다면 지그재그로 가는 경로도 잘 정리하면 될 것 같다. 이거 또한 $O(R)$의 시간복잡도를 가질 것이다. 따라서 시간초과. 아이디어 3 그렇다면 어떻게 짜야할까? 바로,..

SCCC 스터디 4일차 1月 14日 오늘은 기초 자료구조에 대해 공부했다. 1. list STL에 있는 list을 이용하여 구현해봤다. list를 이용한 문제가 잘 안나온다고 하는데 그렇게 어려운것도 아니고 간단한 자료구조이기도 하고 혹시 나오면 당황해서 못짜는 것보단 아는 것이 좋아 list를 이용해 백준에 있는 문제를 풀었다. 2. Graph Graph를 인접행렬로 표현 할 수 있고, 인접리스트로 표현 가능하다. 각자의 장단점이 존재한다. 어느정도 작을땐 인접행렬을 이용해 문제를 풀어도 되고 좀 클땐 인접리스트가 효율적이다. 3. Tree 트리에 가장 큰 특징은 사이클이 없는 연결 그래프라는 점이다. 즉, Tree는 Graph의 일종이다. 또한 트리는 정점이 n개가 있으면 간선은 n - 1개가 있다...

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

SCCC 스터디 3일차 정렬 - 힙 정렬 - 선택 정렬 - 삽입 정렬 - 버블 정렬 - 합병 정렬 - 쉘 정렬 - 퀵 정렬 - 카운팅 정렬 1. 힙 정렬 STL priority_queue를 이용하지 않고 힙 정렬 구현해보기 - 최대 힙 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) - 최소 힙 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) - 수 정렬하기2 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) 2. 삽입 정렬 - 수 정렬하기 ◐○○○○ - 수 정렬하기2 ●●●●● (수 정렬하기2에서는 삽입 정렬를 이용해서 절.대.로 맞았습니다!가 뜨지 못한다.) 3. 합병 정렬(merge sort) - 수 정렬하기2 ●●●○○ 4. 퀵 정렬 - 수 정렬하기2 ●●●○○ (퀵 정렬은 최..

SCCC 스터디 1일차 STL에 대해 설명을 듣고 간단한 문제를 풀며 공부했다. 내용 간단히 정리 1. memset string.h, memory.h 안에 있으며 초기화 할 값은 바이트 단위이다. (여기서 배운 내용은 아니지만 내가 알고 있는 꿀팁은 int형인 배열에 0x3F의 값을 초기화 한다면 배열에는 0x3F3F3F3F의 값이 들어간다.) int arr[1000];memset(arr, 0x3F, sizeof(arr)); arr[0] == arr[1] == arr[2] == ... == arr[999] == 0x3F3F3F3F 이는 다익스트라 등의 알고리즘에서 많이 사용한다. 2. math.h - 이 헤더파일 안에는 Hypot => sqrt(x^2 + y^2)의 값, 즉 두 점과의 거리를 구하는데 사..

문제 : 1,2,3 더하기 6유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다. 어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지.....