0과 1의 쉼터

문제https://www.acmicpc.net/problem/32978풀이입력받은 N개의 재료에 대해 언급되지 않은 재료를 찾는 문제다.우선 N개의 재료를 입력받아 집합에 넣어주자.다음으로 N - 1개의 재료를 입력받아 어떤 재료가 빠졌는지 확인하면 된다.입력받은 재료들을 집합에서 제거해주자.정확히 N개를 입력받고, N - 1개를 제거했으므로 집합의 첫 번째 요소를 출력하면 된다.소스코드보기

Python에서는 * 연산자를 사용하여 리스트나 문자열을 쉽게 복사하거나 확장할 수 있습니다.  이 연산은 매우 간편하지만, 작동 원리를 제대로 이해하지 못하면 의도치 않은 결과를 초래할 수 있습니다.특히, 리스트와 같은 가변 객체(mutable object) 를 다룰 때는 주의가 필요합니다.  이번 글에서는 Python의 * 연산이 어떻게 작동하는지, 그리고 이를 사용할 때 발생할 수 있는 문제와 해결 방법을 알아보겠습니다. 1. * 연산의 기본 원리Python의 * 연산자는 반복(repetition) 을 통해 객체를 복사하거나 확장하는 역할을 합니다.대표적으로 문자열, 숫자, 리스트에서 활용됩니다. (1) 문자열과 숫자의 경우문자열과 숫자는 불변 객체(immutable object) 이므로, * 연산..

문제https://www.acmicpc.net/problem/1520풀이최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수우선 입력을 받자.모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y..

문제https://www.acmicpc.net/problem/6593풀이L, R, C로 이루어진 직육면체에서 상하좌우, 위, 아래로만 이동하며 출발지 S에서 도착지 E로 도착하는데 걸리는 최단 시간을 구하는 문제다.BFS를 3차원으로 확장하면 되는 기본 문제다.우선 시작 전 문자나 상태를 정의해주자.상위 그래프 문제로 갈수록 이처럼 문제에서 주어지는 문자들을 자신의 언어로 변환해주는게 실수를 방지하는데 도움이 된다.L, R, C가 모두 0이 아닐 때 까지 입력을 받으며 탐색을 진행하면 된다.그래프 정보를 입력받으며 벽을 표시해주고, 시작점과 종료점의 위치를 파악해주자.(sl, sr, sc, el, er, ec)각 층마다 한 줄 공백 입력이 주어진다는 점에 유의하자.기본 BFS를 3차원으로 확장해 구현해주..

문제https://www.acmicpc.net/problem/2583풀이K개의 직사각형을 제외한 나머지 영역의 개수와 넓이를 구하는 문제다.우선 문제의 예제를 살펴보자.K개의 직사각형에 대해 표시하면 다음과 같다. 왼쪽아래 좌표와 오른쪽위 좌표가 주어지는데 그림을 회전시켜보자.일반적인 배열의 논리적 표현과 같다.그러면 사각형의 넓이는 어떻게 구할까?전체적으로 행과 열을 축소시키면 된다.즉, 이 문제에서 다룰 범위는 M, N에 대해 (0, 0) ~ (N - 1, M - 1)가 된다.K개의 좌표를 입력받아 블럭표시를 해주자.이제 블럭( BLCOK )이 아니고, 방문한적 없는( EMPTY )영역들에 대해 BFS를 진행하면된다.bfs(i, j)는(i, j)에서 bfs를 하고, 하나로 연결된 영역의 넓이를 반환한..

문제https://www.acmicpc.net/problem/17071풀이수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.수빈이는 다음과 같이 움직일 수 있다.X - 1X + 12X동생은 다음과 같이 움직일 수 있다.N + KK는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.bfs로 N부터 탐색을 시작하자.큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.수빈이는 X - 1..

문제https://www.acmicpc.net/problem/28288풀이가로, 세로가 5 * N으로 이루어진 일정을 참고해, 각 열에 존재하는 'Y'의 비율 가장 많은 요일을 출력하는 문제다.만약, 각 일정이 가지는 Y의 수가 동일한 경우 ','를 구분자로 같이 출력해주면 된다.우선, 문자열 결합을 쉽게 하기 위해 StringJoiner를 사용했다.이후 입력받은 char 배열에 대해 각 열에 존재하는 Y의 개수를 cnt 배열에 기록해주자.동시에 최대 개수를 따로 기록해주자.이제 cnt 배열에서 기록한 최대 개수와 동일한 개수의 Y가 존재하는 일정을 구분자와 결합해 출력하면 된다.소스코드보기

Python 개발을 하다보면 다양한 외장 라이브러리를 설치하게 됩니다.VSCode, PyCharm, 또는 콘솔에서 pip를 통해 외장 라이브러리를 설치했을 것입니다. 오늘은 Python의 표준 패키지 관리 도구인 pip를 사용해 인터페이스에 관계없이 외장 라이브러리를 손쉽게 제거할 수 있는 방법에 대해 알아보겠습니다.명시적 삭제삭제하려는 패키지를 직접 명시해 삭제하는 명령어입니다.pip uninstall 아래 명령어는 numpy를 삭제하는 명령어입니다.pip uninstall numpy다음과 같이 여러 라이브러리를 동시에 삭제할 수 있습니다.pip uninstall numpy pandas  설치된 패키지 확인삭제 전 설치된 패키지의 목록을 확인할 수 있습니다.pip list  설치된 패키지 목록화만약 설..

오늘은 피크민들에게 정수를 먹이고, 꽃잎을 2배로 얻을 수 있는 방법에 대해 소개하겠습니다. 피크민은 처음에 "잎사귀"로 시작합니다.저의 B-2입니다. 보시는 것처럼 머리 위에 "잎사귀"가 있습니다.피크민에게 "정수"를 주거나, 대열에 넣어 함께 산책하면 머리의 잎사귀는 "꽃봉오리"가 됩니다. 이렇게 머리위에 꽃봉오리를 핀 상태에서 정수를 주어 꽃잎을 피우면, 해당 꽃잎을 두배로 얻을 수 있습니다.  아침밥을 보고 눈 돌아간 노예입니다. 이후 피크민을 눌러 꽃잎을 채취 후 실제로 꽃잎 두개를 얻었는지 확인 해보겠습니다. 보시는 것처럼 하양 헬레보루스가 238개에서 정수 하나로 240개가 된 것을 확인할 수 있습니다. 이 방법은 피크민 머리 위에 "잎사귀"가 있을 때 일반 정수를 주거나 산책을 통해 꽃봉오..

문제https://www.acmicpc.net/problem/2482풀이바텀업보다 탑다운 방식으로 접근하면 쉬워지는 문제다. 원형을 이루는 N개의 색상환 표에 대해 인접하지 않은 색을 K개 선택하는 경우의 수를 구해야 한다.경우의 수가 너무 커지지 않게 1e9 + 3으로 나눈 나머지를 출력해야 한다. dp[N][K] : N개의 색상에 대해 인접하지 않는 K개의 색을 선택하는 경우의 수문제를 단순화해보자. 다음이 성립한다.dp[N][1] = Nif K > N / 2, dp[N][K] = 0문제에서 주어진 그림을 예시로 설명하겠다.우선 빨강색(N번째)을 선택해보자.N번째 색을 선택할 때, 인접한 N - 1번(다홍색)은 선택할 수 없다. N - 2번(주황)을 선택해야하고, 이 때 K - 1개의 색을 선택하면 ..

PS 문제집을 따라 푸는 분들을 위해 제작한 노션 페이지 입니다.기존 또는 앞으로의 PS에 대해 문제집이 존재하는 경우 아래의 노션 페이지에서 관리할 예정입니다.감사합니다. https://held-sparrow-180.notion.site/164c96bf505e807b957cf4062faabdc1?pvs=74