분류 전체보기 (72) 썸네일형 리스트형 [백준] 10993번: 별 찍기 - 18 https://www.acmicpc.net/problem/10993 10993번: 별 찍기 - 18 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 재밌어보여서 풀기 시작했다가 복잡해서 당황했다..;; 출력 삼각형을 잘 관찰해보면 가장 큰 삼각형 안에 이전 수준의 삼각형이 있고, 또 그 안에 이전 수준의 삼각형이 있고... 를 반복하는 것을 알 수 있다. 삼각형의 크기는 이전 수준의 삼각형의 대략 2배정도이므로 지수승으로 커진다. 이 점을 이용해서 top-down(재귀) 방식이나 bottom-up(for문) 방식으로 풀면 되는데 나는 for문으로 풀었다. 한줄짜리 string을 저장하는 덱을 선언한 뒤, 가장 작은 삼각형부터 덱에 넣는다. 그리고 그보다 한단계 큰 삼각형을.. [백준] 3190번: 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 문제가 길고 난해하다. 구현을 위해서는 조건을 세세하게 잘 읽어봐야 한다. 1. 뱀 머리를 늘린 후 꼬리 줄이기 2. 보드 행열의 인덱스는 1~.. [백준] 5397번: 키로거 https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 테 www.acmicpc.net list로 푸는게 속도가 더 빠를 것이라고 생각했는데 deque으로 푸는게 더 빨랐다. deque이 list보다 메모리를 덜 잡아먹어서 그.. [백준] 1021번: 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net #include #include using namespace std; deque dq; int N, M; int arr[50]; int cnt = 0; void moveLeft() { int front = dq.front(); dq.pop_front(); dq.push_back(front); } void moveR.. [알고리즘] Linked List(연결 리스트) https://kks227.blog.me/220781402507 리스트(List), 배열(Array), 연결 리스트(Linked List) 오랜만입니다. 논문 읽다가 멘붕이 와서 빠르게 글 씁니다.원래는 이번 차례에 DFS를 강의하려고 했으나... blog.naver.com (이분 블로그를 정리하기 위해 쓰는 글입니다.) list란 선형적으로 값을 가지고 있는 자료구조이다. linked list란 배열과 같이 어떤 자료구조를 구현하는 프로그래밍 기법이다. linked list나 배열을 이용해서 list를 구현할 수 있으며, 두 방법 모두 각각의 장단점을 가지고 있다. 배열로 구현할 때 장점: 랜덤 액세스가 가능하다(O(1)의 시간복잡도) 단점: 삽입, 삭제 연산이 오래걸린다(삽입, 삭제 연산하는 위치 뒤.. [백준] 16500번: 문자열 판별 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다. www.acmicpc.net 한참동안이나 붙들고 있었던 문제..ㅠㅠ 처음에는 정말 간단하게 아래와 같이 입력이 주어졌을 때 softwarecontest 2 software contest 문자열 S에서 단어를 하나씩 지워가면서 문자열을 모두 지울 수 있는지를 검사하면 된다고 생각했었는데 틀린 접근법이었다. 반례는 soft, s.. [백준] 12865번: 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 첨에 내가 푼 접근법이 완전 틀려서 ㅠㅠ 결국 인터넷에 검색해서 다른분들 해설을 보고서야 해결했다. DP문제 중 매우 유명한 배낭 문제로, 각각의 무게와 가치가 주어진 N개의 물건이 있을 때, 무게가 K가 넘지 않도록 물건들을 배낭에 넣어서 최대 가치를 구하는 문제이다. 접근법은 .. [백준] 11051번: 이항 계수 2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수를 구하는 문제. 간단하게 생각해서 1~N까지의 팩토리얼을 구해서 배열에 저장하면 되지 않을까 생각했지만, 1000!은 long long의 표현 범위조차 아득히 넘어버린다. 따라서 nCr = n-1Cr-1 + n-1Cr 이라는 조합 공식을 이용해야 한다. include using namespace std; int dp[1001][1001]; int main(void) { int N; int K; cin >> N >> K; for (int i = 0; i 이전 1 ··· 5 6 7 8 9 다음
