본문 바로가기

분류 전체보기

 (249)
[BOJ] 16235. 나무 재테크 문제 나무 재테크 (https://www.acmicpc.net/problem/16235) 풀이 1. 초기 접근 문제조건 해석 역시 삼성 문제는 뭔가 글이 많다. 세세하게 잘 읽어야한다. 두번 세번 읽어줘야 한다. 문제를 잘 읽고 코딩하자. 삼성 문제의 대표적인 시뮬레이션 문제다. 문제에서 주어진 대로 그냥 짜기만 하면 된다. 핵심은, 과연 올바른 자료구조로 잘 구현할 수 있는가? 다. 알고리즘 정말 문제에 나온대로 하나씩 코딩하면 된다. 핵심은, 나이가 어린 나무들부터 양분을 섭취해야하는데, 이를 위해 deque 를 썼다. 자세한 건 코드 주석 참조. 코드 from collections import deque dxs = [-1, -1, 0, 1, 1, 1, 0, -1] dys = [0, 1, 1, 1, ..
[BOJ] 16236. 아기 상어 문제 아기 상어 (https://www.acmicpc.net/problem/16236) 풀이 1. 초기 접근 문제조건 해석 일단 문제조건이 뭔가 되게 복잡해서, 잘 읽어야한다. 삼성 문제 특징이다. 이동할 수 있는 각 경우는 상하좌우 4가지 방향이 있고, 한 번에 1칸 이동할 수 있다. 우리는 최종 이동까지의 시간을 구해야 한다. BFS 문제다. 알고리즘 일단 진짜로 문제를 잘 하나하나 읽고, 예제로 주어진 케이스들을 손으로 풀면서, 내가 잘 이해했는지 확인해보자. 그럼 다음과 같이 차례대로 생각해볼 수 있다. 먼저 자기보다 크기가 작은 물고기들을 찾는다. 그 중, 가장 가까운 애들부터 먹으러 가서 먹는다. 지금까지 먹은 횟수가 현재 내 크기만큼 되는지 체크한다. 만약 내 크기만큼 된다면, 내 크기를 한..
[BOJ] 13460. 구슬 탈출 2 문제 구슬 탈출 2 (https://www.acmicpc.net/problem/13460) 풀이 1. 초기 접근 문제조건 해석 판이 주어지고, 스텝에 따라 판 위에 구슬의 위치가 규칙적으로 달라진다. 목표하는 위치에 도달하기 위한 "최소" 스텝을 구해야 한다. BFS 문제다. 알고리즘 이번 문제는 조금 까다로웠는데, step by step 으로 하나씩 코드화 해보자. 1) 먼저 기본적인 입력과 BFS 들을 만든다. 메인 코드는 아래와 같다. from collections import deque dxs = [-1, 0, 1, 0] dys = [0, 1, 0, -1] # n, m을 입력받고, board에 판을 저장한다. n, m = list(map(int, input().split())) board = [l..
L1, L2 Regularization (Lasso, Ridge) 머신러닝을 위한 파이썬 워밍업에서 Linear Regression 파트를 공부하며 복습한 내용을 적어본다. Overfitting 의 문제 Regularization 이라는 문제에 앞서 항상 먼저 나오는게 overfitting 이슈다. 기술 관련 이슈는 대부분 원인 -> 해결방법 순으로 설명이 되다보니 당연한 일이겠지만. 이전에 Gradient Descent 를 통해 W 를 기계적으로 (반복문과 갱신을 통해) 찾아내었다. 일단 머신러닝이라고 하는 것이 되긴 한거다. 사람이 찾지 않고, 어떤 식과 기계의 힘을 빌려서 찾았으니깐 말이다. 그럼 이제 문제는 '잘' 찾는 것인데. 본격적인 고도화 및 성능 이슈의 시작되는 듯 하다. Overfitting 은 이러한 고도화 이슈 중, 가장 일반적인 현상인데, 한 마디..
Normal equation 과 Gradient Descent 머신러닝을 위한 파이썬 워밍업에서 Linear Regression 파트를 공부하며 복습한 내용을 적어본다. 선형회귀 모델은 y = Wx + b 다. 우리는 데이터(x) 를 가지고 어떤 결과(y)를 예측하는 어떤 모델(y=Wx+b) 를 만들려고 한다. 즉 결과적으로 "모델", 을 만드는 것인데, 이 모델은 구체적으로 각 변수에 곱해지는 계수항들의 묶음 W와 상수항인 b를 의미하고, 이 두 변수를 구하는 것이 기계학습의 목표이다. 이를 어떻게 구할까? 에 앞서, 이에 대해 강의에서는 2가지를 설명해주는데, Normal Equation과 Gradient Descent다. Normal Equation y = Wx + b 에서 b 는 x 에 [1] 로 구성된 열을 추가해주면, y = Wx + b 를 y = xW&..
[BOJ] 1964. 소수 경로 문제 소수 경로 (https://www.acmicpc.net/problem/1963) 풀이 1. 초기접근 문제조건 해석 한 step 단위로, 특정 수를 찾아야 하는 문제다. BFS 문제다. 현재 step에서 다음에 갈 step은 각 자릿수를 바꿔보며 소수인 경우다. 알고리즘 먼저 어떤 수 i 가 소수인지 체크하는 배열을 미리 만든다. 에라토스테네스의 체를 사용한다. 현재 수의 각 자리를 0~9로 바꿔보며, 바꾼 수가 소수인 경우 큐에 넣어준다. 그 외 조건들, 바꾼 수가 1000 보다 큰지, 바꾼 자릿수가 -1은 아닌지 등을 체크한다. BFS를 이런 식으로 진행하다, 찾으려 했던 수를 찾으면 즉시 현재 step 을 반환한다. 코드 from collections import deque def bfs(a, ..
[BOJ] 2636. 치즈 문제 치즈 (https://www.acmicpc.net/problem/2636) 풀이 1. 초기접근 문제조건 해석 한 step 단위로, 판의 상태가 달라진다. DFS, BFS 문제다. 가장자리의 치즈만 트래킹해서 처리해야한다. DFS 로 풀 수 있겠다. 알고리즘 기본적인 아이디어는 이렇다. 먼저 치즈가 있는부분(1)을 찾는다. 해당 좌표에서 상하좌우의 연결된 1들을 쭉 탐색(DFS) 한다. 탐색하는 동안, 해당 좌표가 가장자리이면, 탐색을 마칠 때, 치즈(1)가 아닌 공기(0)로 상태를 바꿔준다. 해당 좌표가 가장자리인지 아닌지 알려면, 좌표기준 상하좌우를 다 둘러보아 공기(0)이 있는지 확인한다. 이 때, 공기를 좀 구분해줄 필요가 있는데, 가장자리임을 알 수 있는 공기는 바깥공기다. 따라서, 치즈 내..
[BOJ] 13913. 숨바꼭질 4 문제 숨바꼭질 4 (https://www.acmicpc.net/problem/13913) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이전 12851. 숨바꼭질 3 문제에서 방법에 약간 변형을 준 것이다. 이제는 경로를 출력해야하는데, DFS야 쉽게 탐색 경로를 출력할 수 있다지만, BFS 에서는 어떻게 해야할까? 현재 위치 cur 에 오기 직전 위치를 담는 리스트(path_list)를 만들자. 예를 들어, 현재 위치가 3이고, 다음으로 이동할 위치가 2, 4, 6이면, path_list[2], path_list[4], path_list[6] = 3 이 된다. 물론 여기에도, 최소 시간으로 왔는지 체크해야 한다. 그리고 최종 ..

티스토리툴바