결국 빛나리라

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net > 큐 각 큐의 원소와 원소에 해당하는 순서를 함께 튜플로 묶어 큐에 추가함으로써 찾고자 하는 원소가 어디에 위치하는지 알 수 있도록 하는 것이 중요한 키포인트였다. 그리고 큐의 첫번째에 나와있는 튜플이 큐의 최댓값과 같다면 해당 튜플을 큐에서 빼주고 순서를 하나씩 증가시키면서 반복문을 진행하다가 찾고자 하는 원소가 나오면 반복문을 중단한다. 해당 원소가 몇번째에 큐에서 나오게됐는지를 알려주는 순서를..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net > 동적계획법 문제의 원리만 깨우치면 코드 작성은 그렇게 복잡하지 않은 문제였다. 4개의 타일로 만들 수 있는 모든 가짓수를 세려본다고 할 때 우리는 다음 그림과 같이 바로 이전 3개 타일의 경우의 수에 1을 붙이는 경우와 그 이전 2개 타일의 경우의 수에 00을 붙이는 경우를 생각해볼 수 있다. 단 숫자를 추가할 땐 뒤쪽에만 숫자를 붙여야 중복되는 수가 나오지 않는다는 것을 기억하자. 결과적으로 4개..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net > 큐 활용 다음 그림은 문제에 나와있는 예시를 대상으로 생각한 아이디어를 그려본 것이다. 1번에서 k-1번, 즉 시작 번호에서 두 번 이동해야하는데 이동하면서 거쳐가는 숫자들은 모두 뒤로 빼준다(

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net > dfs 활용 연결되어있는 격자들에 방문처리하고 개수를 카운트한다는 점에서 dfs 알고리즘을 사용하였다. 먼저 격자 정보들을 2차원 배열형태로 입력한다. 아래 코드로 값을 입력받으면 숫자들이 모두 문자형태로 들어간다는 것을 기억하자. 그리고 격자에 방문했는지 여부를 보여주는 visited 배열과 격자의 상하좌우로 움직이기 위한 dx, dy 배열도 선언해준다. 행, 열 정보를 파라미터로 넣은 dfs..

1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net > 다이나믹 프로그래밍 7부터 시작하여 아래 그래프로 내려가며 최대가 되는 수를 찾는 문제이다. 위부터 아래로 내려오며 더한 값들이 최대가 되도록 하는 방법을 사용했다. 더한 값들이 최대가 되기 위해선 수에 더할 윗 값들 중 더 큰 수를 더할 수 있을 것이다. 한 행에서 맨 앞에 위치한 수나 맨 마지막에 위치한 수의 경우 위의 줄에서 더할 수 있는 수가 하나밖에 없으므로 다음 그림과 같이 그릴 수 있다. 해당 그림대로 수를 더해보면 다음과 같다. 맨 아래 줄에서 최대값인 30이 7에서..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net > 큐 활용 큐의 기본 개념을 묻는 문제이다. 마지막 원소가 남을 때 까지(큐의 길이가 1보다 클 때까지) popleft와 append를 반복한다.

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net > 이분 탐색 활용 탐색하는데 사용되는 시간효율성을 위해 이분탐색방법을 활용하였다. 기본 이분 탐색 개념에 중복되는 수의 개수를 카운트하는 아이디어만 생각할 수 있다면 풀 수 있는 문제였다. 먼저 입력값들을 받아오고 가지고 있는 카드들의 개수 정보를 담은 딕셔너리를 선언한다. 기본 이분 탐색 알고리즘에 중간값이 타겟과 같은 수 일 때 반환하는 값부분만 수정해주었다..

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net > 정렬 알고리즘 이전 포스팅에 정리한 내용을 참고하면 파이썬의 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)의 시간복잡도를 보장한다. 해당 문제에서는 N의 최대개수가 100만이므로 NlogN은 약 600만이다. 파이썬에선 1초에 2000만번의 연산을 수행할 수 있다고 생각하면 정렬 알고리즘을 사용하여 충분히 해결가능하다.

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net > 스택 활용 리스트를 사용하여 스택 자료구조를 간단하게 구현할 수 있다.

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net > dfs 활용 단방향 그래프가 아닌 양방향 그래프임에 주의해야한다. ▷ 처음에는 단방향 그래프로 다음과 같이 구현했다. 그러나 위 코드는 다음과 같은 예제는 풀지 못한다. 위와 같은 그래프가 있다고 할때 단방향 그래프는 1번 노드에서 출발했을 때 3번과 2번노드와 연결되어 있다고 인식하기 때문에 다음과 같이 1과 연결된 노드의 수로 2를 출력한다. ▷ 그러나 문제에 따르면 1번 노드는 2,3번 노드 ..