본문 바로가기
728x90

전체 글83

[C++] 백준 N-Qeen (9663), 재귀, DFS, 백트래킹 문제 https://www.acmicpc.net/problem/9663 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 복사 8 예제 출력 1 복사 92 풀이 이전 Queen들의 이동 방향성을 체크하는 것이 주된 키 2차 배열로 모두 체크하는 것 보다, 경향(기울기)을 파악해서 1차원으로 체크하면 O(1)로 체킹할 수 있다. 백트래킹을 이용하여 재귀적으로 DFS를 수행한다. 코드 알게 된 점 백트래킹을 통한 재귀의 과정에 대해서 .. 2023. 10. 8.
[DL] 오토인코더(Autoncoder) 본 포스팅은 DMQA 오픈 세미나 자료 및 영상을 참고하여 정리하였습니다. http://dmqm.korea.ac.kr/activity/seminar/330 고려대학교 DMQA 연구실 고려대학교 산업경영공학부 데이터마이닝 및 품질애널리틱스 연구실 dmqa.korea.ac.kr 1. 오토인코더란 무엇일까? 정의 : 레이블이 없는 비지도학습에 주로 사용되는 신경망 형태이다. 구조 : Encoder와 Decoder가 bottleneck 구조를 이룸 Encoder : 입력 데이터를 의미있게 함축된 representation한다. Decoder : Encoding 된 representation을 다시 원본 데이터로 복원 reconstruction loss : 입력 데이터와 복원 데이터의 차이를 학습하여, loss를.. 2023. 8. 23.
[c++] 백준 벽 부수고 이동하기 3(16933), bfs, 반례모음 문제 https://www.acmicpc.net/problem/16933 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 .. 2023. 8. 22.
[c++] 백준 벽 부수고 이동하기 2(14442), bfs, 반례모음 문제 https://www.acmicpc.net/problem/14442 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤.. 2023. 8. 21.
[c++] 백준 숨바꼭질 4(13913), bfs, 반례모음 문제 https://www.acmicpc.net/problem/13913 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다. 반례모음 24 300 10 24 2.. 2023. 8. 18.
[c++] 백준 말이 되고픈 원숭이(1600), bfs, 반례모음 문제 https://www.acmicpc.net/problem/1600 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포.. 2023. 8. 16.
[c++] 백준 숨바꼭질 3(13549), bfs, 반례모음 문제 https://www.acmicpc.net/problem/13549 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 반례모음 10000 0 10000 2 7 1 1 17 1 4 6 1 0 1 1 0 3 2 0 0 0 1 32 0 3 22 1 5 7 2 1 10000 3 1.. 2023. 8. 16.
[DL] Batch Normalization이란? 효과? ICS? Smoothing? 이 포스팅은 아래 강의를 정리 및 일부항목을 추가한 것입니다. 매우 유익하고 설명이 자세하니 참고 바랍니다. https://www.youtube.com/watch?v=58fuWVu5DVU Batch Normalization 효과 ① 학습 수렴속도가 빠르다. - 적은 epoch으로도 사용하지 않는 것 대비 높은 성능을 달성 ② 가중치 초기화(weight initalization)에 대한 민감도를 감소시킨다. - 모델을 학습할 때, 하이퍼파라미터의 변경은 모델의 수렴을 크게 좌우하지만, BN을 사용하면 덜 정교한 하이퍼파라미터 세팅이더라도 정상적으로 수렴한다. 예를 들어 learning-rate를 크게 잡아 모델이 학습이 안되는 경우에 BN을 적용시 정상적으로 수렴하는 것을 볼 수 있다. ③ 모델의 일반화(.. 2023. 8. 15.
[c++] 백준 다리 만들기(2146), BFS, 반례모음 문제 https://www.acmicpc.net/problem/2146 회색은 땅, 하얀색은 바다. 땅간의 연결 가능한 최단거리를 구하시오. 반례모음 5 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 2 5 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 6 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 5 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 2 4 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 4 풀이 풀이가 2가지 있습니다. 1) BFS기반 정석적인 풀이 - 땅의 영.. 2023. 8. 9.
[c++] 백준 빙산(2573), BFS, 반례모음 문제 https://www.acmicpc.net/problem/2573 해마다 위의 그림처럼 빙산이 녹습니다. 숫자를 제외한 빈 공간은 모두 0(바다)으로, 1년이 지나면 인접한 빙산을 녹이는데, 0의 개수만큼 녹습니다. 처음 빙산이 분리될 때, 몇 년이 지났는지를 출력하시오 분리되지 않고 모든 빙산이 녹을 때는 0을 출력. 반례 5 5 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 4 4 0 0 0 0 0 3 1 0 0 1 3 0 0 0 0 0 1 5 7 0 0 0 0 0 0 0 0 3 3 2 3 3 0 0 4 0 4 0 3 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0 5 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0.. 2023. 8. 7.
[Pytorch] nn.Parameter()로 grad 확인하기 troch graph에서 특정 노드로 흘러오는 역전파 값을 확인하고 싶을 때 유용하게 사용할 수 있습니다. torch는 requiers_grad=True를 통해 연산된 텐서들을 autograd로 추적할 수 있지만, leaf node가 아닌 변수들의 gradient는 None으로 바뀌게 됩니다. 이러한 변수들의 gradient를 남기기 위해서 retain_grad()를 사용합니다. x_stage1로 전달되는 미분값의 확인을 위해 params를 더해줍니다. 더해주는 연산은 역전파가 동일하게 흐르므로, 전파되는 미분값의 크기를 대략적으로 파악할 수 있습니다. 이를 통해, 계수의 조절과 loss가 적절한지 등 실험설계의 방향성을 잡는데 좋습니다. 2023. 8. 6.
Cost Function은 무엇이며, 알고 있는 cost function에 대해서 말해주세요 cost function(=loss function)은 모델이 최적의 파라미터를 찾도록 사용자의 의도에 따라 올바른 학습방향을 안내해주는 함수입니다. Task에 따라 그 목적이 상이할 수 있는데, 예를 들어 지도학습의 classification에서는 정답과의 차이를 cross entropy loss를 통해 모델이 카테고리를 분류할 수 있도록 하는데, 이때 학습되는 방향은 정답에 대한 예측값과 정답이 아닌 예측값에 대해서 미분방향을 반대로 주어서 분리되도록 학습합니다. 결국 CE loss가 최소가 되도록 합니다. 이와 유사한 loss function으로는 MAE, MSE, BCE, KLD가 있습니다. 이와 반대로 loss function의 값을 최대가 되도록 하는 loss는 negative pair los.. 2023. 8. 4.
728x90

티스토리툴바