공부용

https://www.acmicpc.net/problem/1967트리의 지름 찾기: 아무 점에서 가장 멀리 가는 점을 찾고, 그 점에서 가장 멀리 가는 점을 찾으면 끝! 친구한테 문어 인형으로 설명해줬던 기억이 난다.문어 인형의 아무 다리나 잡고 높이 들어서 가장 멀리 있는 다리를 찾고, 그 다리를 잡고 다시 높이 들어서 가장 멀리 있는 다리를 찾아서 이으면 그게 트리의 지름이었다고 했었는데 덕분에 나도 기억이 난다이 문제는 가중치가 있기 때문에 어느 점이든(나는 루트로 했다) DFS를 해서 가중치가 가장 높은 경로를 선택하고, 해당 정점에서 다시 가중치가 가장 높은 경로를 구하면 되고, 이때 구한 경로의 가중치의 합이 답이 된다.#include using namespace std;#define fast..

문제 링크 배열 돌리기 3 설명 N*M 크기의 배열을 다음 6가지 방법으로 돌리는 문제 1. 배열 상하 뒤집기 2. 배열 좌우 뒤집기 3. 배열 오른쪽 90도 회전 4. 배열 왼쪽 90도 회전 5. 배열 4분할 후 각각을 오른쪽 90도 회전 6. 배열 4분할 후 각각을 왼쪽 90도 회전 접근 제한은 다음과 같음 2 ≤ N, M ≤ 100 1 ≤ R ≤ 1,000 N, M은 짝수 1 ≤ datas[i][j] > n >> m >> r; for (int i = 0; i > originals[i][j]; } } } vector rotate(int op,vector boar..

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..