공부용

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 이걸 Dummy라고 부르는 지는 모르겠는데, 뱀을 이용해서 사과를 먹을 때 마다 길이가 길어지는 그런 류의 게임들을 얘기하는 것 같다. 비슷한 게임을 유튜브에서 찾아보니까 https://www.youtube.com/watch?v=kZr8sR9Gwag 이런 게임이 있다. 혹시나 처음 보시는 분들은 유튜브 영상을 보시면 좀 더 이해가 쉬울 것 같다. 뱀은 처음에 (1,1)에서 시작하며,오른쪽을 보고 있다. ..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 시뮬레이션 + BFS를 이용하는 문제이다. 12*6 크기의 필드에 R,G,B,P,Y 총 5개의 뿌요와 빈 공간을 나타내는 '.' 문자까지 총 6개의 문자가 주어질 때 가능한 연쇄의 횟수를 출력하면 된다. 특정 뿌요를 기준으로 같은 색의 뿌요가 4개이상 상하좌우로 연결되어있는 경우 터지는데, 이를 연쇄라고 한다. 터질 수 있는 뿌요가 여러 개라면 한 번에 터져야 하고, 한 ..

+) 글 작성에 앞서! 내가 짠 코드보다 훨씬 간결하고 효율적인 코드가 있다. https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/12100.cpp 바킹독님 코드인데, 직접 4방향으로 돌려보지 않고 배열을 회전시키는 방법이다. 이 코드가 덜 직관적이긴 하지만 좀 더 효율적인 코드를 찾으시는 분들은 읽어보면 좋을 것 같다. https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 ..

+) 추가! 다 풀고나서 바킹독님 강의를 보고 알게된건데, 스티커를 받자마자 바로 붙일 수 있으니까 굳이 배열에 저장할 필요 없이 스티커를 받고 바로 대보면 된다! 다음에 비슷한 문제가 있으면 이렇게 풀어봐야겠다. https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 시뮬레이션 문제이다. 그냥 문제에 나온 그대로 구현하면 정답을 받는다. 물론 그대로 구현하는게 어렵다... n*m 크기의 노트북에 r*c크기의 스티커 k개를 붙이는데, 붙이는 과정은 다음..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 1~49번까지의 번호가 있는 로또중에서 k개를 뽑아서(6

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 예전에 재귀에 대해서 거의 모를 때 무작정 풀었다가 정말 고생했었던 기억이 난다. 2N*2N을 Z모양으로 탐색한다는 건 왼쪽 위,오른쪽 위,왼쪽 아래,오른쪽 아래순으로 간다는거다. 예를 들어 문제 예시의 2*2 사각형을 보면 0,1,2,3 순이다. 그리고 잘 보면 r행 c열을 구할때 직접 따라가보지 않더라도 구할 수가 있다. 예를 들어 n=2,r=3,c=1이라면 순서대로 따라가도 11이겠..

바킹독님 강의를 천천히 들으면서 공부중인데 이제 재귀파트에 왔다. 전에 포스팅했던 (https://pl-are.tistory.com/34) 문제는 재귀 연습문제 1번이었고, 이 문제는 그냥저냥 풀만했다. 하 근데... 이 문제가 진짜 어렵다. 이 문제를 풀면서 내가 재귀를 아직 이해하지 못했고, 절차지향적으로 사고하고 있었다는걸 깨달았다. n이 3일때, 4일때, 5일때 각각 해보면서 순서대로 따라가는건 할 수 있는데, n이 6일때, 7일때... 100일때는? 귀납적으로 사고하지 않으면 풀수가 없다. 고려해야할 사항이 너무 많아서... 열심히 쳐다보고 적어보면서 나름대로 이해하려고 노력한 과정을 적어보려고 한다. 우선 하노이 탑 문제에 대해 간략하게 설명을 하자면 3개의 탑이 있고, 이 중 1번째 탑에 원..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 가장 간단하게 생각하는건 a를 b번 곱한다음 c로 나눈 나머지를 구하는건데, 범위가 2^32-1이라 BIGINTEGER나 __int128같은 자료형을 쓰지 않는 이상(아니 아마 쓰더라도) 오버플로가 날거고, a에 a를 곱하고 c로 나눈 나머지에 다시 a를 곱하고 c로 나눈 나머지를 구하고...로 구한다고 하더라도 b번 곱하는데 O(b)면 시간초과가 날것이다. 이 문제는 바킹독님 강의의 이 부분을 참고해서 풀면 도움이 많이 된다. 12^58 % 67 = 4, 12..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 모든 빙판이 물과 닿으면 녹는다고 할때 (닿는다는 기준은 상하좌우로 물이 인접해있을 경우) 백조 두 마리가 만나는데 며칠이 소요되는가를 구하는 문제이다. 우선 알아두면 좋은게, 백조가 있는 칸도 물로 취급한다. 즉 1 7 LXX.XXL 같은 입력이 들어오면 정답은 1이다. 설명이 애매해서 추가해줬으면 좋겠는데 (https://www.acmicpc.net/board/vi..

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 예전보다 어려운 난이도의 BFS 문제를 풀 수 있게 된건 좋은데, 맞다 싶으면 무조건 제출하고 보는 경향 때문에 자꾸만 정답률이 낮아지는게 신경쓰인다. 엄청난 틀렸습니다를 보고야 깨달은거지만, 이 다음 문제부터는 예제만 맞다고 무조건 내고 보지 말고 자체 디버깅이나 다양한 반례를 만들어보고 내는 습관을 가져야겠다고 생각했다... 다른 BFS 문제(특히 불!이나 불:https://www.acmicpc.net/p..