분류 전체보기 (62) 썸네일형 리스트형 [백준/C++] 알고리즘 1932번 - 정수 삼각형 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 1932번 - 정수 삼각형 울 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [문제 접근] 제한시간은 2초이고, 완전탐색이 가능한지 확인을 했습니다. 처음에는 대략적으로 완전탐색이 어렵다고 판단이 들었습니다. 그래서 완전탐색을 목표로하는 BFS와 DFS의 접근방식을 고려하지 않았습니다. 엄밀히 계산해보면 n= 500일 때 모든 경로의 수는 2^499임을 알 수 있고 완전탐색으로 제한시간 2초이내로 실행하기 어렵다는 것을 알 수 있습니다... [백준/C++] 알고리즘 1003번 - 피보나치 함수 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 1003번 - 피보나치 함수 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [문제 접근] n = 2, n =3 , n= 4 .... 일 때 f(0)과 f(1)이 호출된 개수를 확인하면서 패턴이 있는지 계속 생각했습니다. D[i] = D[i-2] + D[i-1] (i >= 2) 점화식을 발견하고 for문을 이용하여 bottom-up방식으로 점화식 값들을 채웠습니다. [풀이 전략] 1. d[0],d[1] 초기값을 설정합니다. 2. 점화식, for문을 이용하여 .. [백준/C++] 알고리즘 3190번 - 뱀 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 3190번 - 뱀을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net [문제 접근] 읽어보면 구현문제임을 알 수 있습니다. 사과가 존재하지 않았을 때 꼬리의 좌표에 접근하여 빈칸으로 만들고 다음 꼬리의 좌표를 파악하는 게 핵심입니다. 이 부분을 꼬리의 좌표를 따로 변수로 만들고, 각 좌표의 direction을 저장하는 히스토리 배열을 만들어서 꼬리가 삭제될때마다 꼬리의 좌표를.. [백준/C++] 알고리즘 2617번 - 구슬 찾기 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 2617번 - 구슬 찾기 를 풀어보도록 하겠습니다. [문제 접근] 문제에서 답에 포함되는 상황은 특정 구슬이 (n+1)/ 2개보다 더 무겁거나 같은 구슬의 개수를 가지거나, 더 가볍거나 같은 구슬의 개수를 가지는 상황입니다. 그래서 저는 특정구슬보다 무거운 구슬들을 담는 공간과 특정구슬보다 가벼운 구슬 공간을 담기 위해 인접리스트 두 개를 이용했습니다. 특정 구슬의 인접리스트 원소 그리고 인접리스트 원소가 연결된 모든 원소들이 몇개인지 파악하기 위해 BFS를 생각했습니다. [풀이 전략] 1. 인접리스트를 이용하여 구슬 간의 관계를 저장합니다. 2. 모든 구슬을 for문을 이용하여 방문합니다. - for문의 한 턴이 시작될 때마다 방문 구슬을 저장하.. [백준/C++] 알고리즘 20922번 - 겹치는 건 싫어 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 20922번 - 겹치는 건 싫어를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net [문제 접근] N이 최대 20만이고, 시간 제한이 1초이기 때문에 O(N^2)은 불가능합니다. 이러한 상황과, 문제가 연속과 관련된 문제이기 때문에 투 포인터를 생각했습니다. st와 en을 두어서 중복개수 조건에 따라 st와 en이 변칙적으로 함께 움직이는 방법을 생각했는데 최장.. [백준/C++] 알고리즘 2531번 - 회전 초밥 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 2531번 - 회전 초밥을 풀어보도록 하겠습니다. [문제 접근] 시간 제한은 1초이고 N은 최대 3만이기 때문에 완전탐색은 불가능합니다. 연속이라는 부분에서 투 포인터를 생각했지만, 중복여부랑 쿠폰초밥 포함여부를 고려하면서 st와 en을 옮기는게 잘 되지 않았습니다. 문제에서 K개라는 고정된 구간이 주어져있으므로 슬라이딩 윈도우 개념을 생각했습니다. 투 포인터와 마찬가지로 슬라이딩 윈도우는 시간복잡도를 O(N)으로 줄일 수 있습니다. [풀이 전략] 1. for문을 한번 돌때마다 앞의 원소가 삭제되고, 뒤의 원소가 추가되기 때문에 deque를 이용한다. 2. 처음에 k-1개만큼 초기값을 대입해준다. 3. for문을 돌면서 뒤의 원소를 추가한다. 4... [백준/C++] 알고리즘 1405번 - 로봇 청소기 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 1405번 - 로봇 청소기를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net [문제 접근] 이 문제는 특별한 자료구조나 알고리즘 개념이 포함된 것이 아니고, 문제에 나와있는 데로 구현하면 됩니다. [풀이 전략] 생략 [코드] #include #include using namespace std; int dx[] = {-.. [백준/C++] 알고리즘 13335번 - 트럭 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 13335번 - 트럭을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net [문제 접근] 가장 오래걸리는 시간을 확인해보았을 때 n * w+로 100,001라는 것을 확인할 수 있습니다. 제한시간은 1초로 넉넉해서 완전탐색으로 접근했습니다. 그리고 가장 먼저 다리에 통과한 트럭이, 가장 먼저 빠져나오기 때문에 큐를 이용하였.. [백준/C++] 알고리즘 2805번 - 나무 자르기 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 2805번 - 나무 자르기를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [문제 접근] 시간 제한 1초, N은 100만이기 때문에 완전탐색이 불가능합니다. 적어도 M미터의 나무를 집에 가져가기 위해 절단기 설정할 수 있는 높이의 최댓값을 생각해보면 H를 점점 높여나가다가 어느 특정 지점을 넘어가는 순간 M미터 작아지는데 그 .. [백준/C++] 알고리즘 18869번 - 멀티버스 II 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 18869번 - 멀티버스 II를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net [문제 접근] 우주가 균등하다는 조건을 그대로 이용하려고 했는데, 잘 안되었습니다. 결국 좌표압축이라는 개념을 알아야하더라구요. 간단히 좌표압축이란 좌표의 값과 무관하게 좌표들 사이의 대소관계만 필요할 때 사용하는 테크닉입니다. (메모리 공간을 절약할 수 있음) 우주가 균등하다는 .. 이전 1 ··· 3 4 5 6 7 다음
