chae._.chae

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net import sys input = sys.stdin.readline N, C = map(int, input().split()) position = [int(input()) for _ in range(N)] position.sort() # 가장 인접한 공유기 사이의 최대 거리 구하기 # 집 사이의 최소/최대 거리 start, end = 1, pos..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 숫자와 +, -로 구성된 식을 입력받아 적절한 위치에 괄호를 삽입해 최솟값을 만드는 문제이다. 🔎풀이 방법 1. 먼저 - 를 기준으로 식을 나눠준다. 입력된 식이 55-50+40+30-20+10+30라면, -를 기준으로 ['55', '50+40+30', '20+10+30'] 으로 식을 split()해준다. 2. +로 연결된 숫자를 계산해준다. [55, 120, 60]으로 + 기호를 계산해준다..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP를 사용해서 푸는 문제이다. N을 1로 만들기 위해 필요한 최소 횟수는 N-1을 1로 만들기 위한 최소횟수 + 1 OR 2나 3으로 나누어지면, 나눠지고 남은 몫에 +1하는 횟수이다. # 1463 1로 만들기 import sys input = sys.stdin.readline N = int(input()) dp = [0] * (N+1) # dp리스트를 모두 0으로, N+1개만큼 초기화 시켜준다. for i in range(2, N+1): dp[i] = dp[i - 1] + 1 if i % 3 == 0: # ..

https://www.acmicpc.net/problem/1874 🔎 어려웠던 점 1. "스택에 push하는 순서는 반드시 오름차순을 지키도록 한다." 라는 말이 이해가 어려웠다. 즉, 문제 예시처럼 수열에 4를 첫번째로 나오게 하기 위해서는, 1~3까지의 수를 push하고 4을 push하고, 4을 pop해줘야 한다. 2. 수열을 만들 수 없는 경우를 stack 그림을 통해서는 대략(?) 이해가 갔지만, 코드로 직접 표현하는 부분이 어려웠다. 스택을 만들 수 있는 경우 예시 1 ~ 4를 push 하고, 4와 3을 순차적으로 pop시켜 수열에 넣는다. 수열에 6을 넣기 위해서는 스택에 5와 6을 push하고 6을 pop시킨다. 동일한 과정으로 수열에 8을 넣기 위해서는 7과 8을 push하고 8, 7을 p..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 📌 풀이 방법 완전탐색(Brute Force) + bfs 의 방법으로 풀어야하는 문제이다. 브루트 포스로 벽3개의 위치로 가능한 경우의 수를 모두 구해주고, 그때마다 bfs함수를 돌려주며 안전영역(0) 갯수의 최댓값을 구한다. virus() 함수 : 바이러스를 퍼트리는 함수로, 값이 2인 지점을 만나면 큐에 넣고, 상하좌우를 살피며 0인 지역이 있으면 바이러스가 퍼진 2의 상태로 모두 바꿔준다. (result..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 📌 다시 봐야 할 부분 1. 리스트 컴프리헨션! c = [i + 5 for i in range(10)] # 0부터 9까지 숫자를 생성하면서 값에 5를 더하여 리스트 생성 M, N = map(int, input().split()) # 5, 7 area = [M * [0] for i in range(N)] print(area) [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 📌 다시 봐야 할 부분 1. 다른 문제와 조금 달랐던 점은, (bfs방식) 큐에 값을 넣고 하나씩 꺼내고 확인과정에서 연결된 지점의 갯수도 구하고, 연결된 지점이 몇개의 칸으로 이루어져 있는지도 함께 구해줘야 했다. 주로 지금까지 풀때는 bfs함수를 구성할때 리턴값이 없었는데, 이 문제에서는 graph의 값이 1일때마다 값을 0으로 바꿔주고(방문처리) + 큐에 추가하고 + 갯수 세주기(count변수..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 📌 다시 봐야 할 부분 1. dx, dy를 모두 돌면서 확인해줄 때, 범위 벗어난 처리를 먼저! if nx = w or ny = h: # 범위를 벗어난 경우 continue 이 부분을 먼저 적어주어야한다. 범위를 벗어난 경우의 처리를 아래로 빼주고 육지가 아닌 경우나 땅인 경우를 먼저 처리하려고 하면, out of index오류가 발생한다. 주로 다른 ..

맨 처음에 문제 이해가 안됐음... 입력하는 숫자들이 점수 라고 착각해서 잘못 풀고 있었다.. ㅂㅏ보... 점수가 아니라 순위를 입력한다!! 아래 그림처럼 순위를 적어주고, 합격자가 누구인지 옆에 표시하며 분류해줬다. 순위를 서류를 기준으로 먼저 오름차순 정렬을 해준다. 서류 1등은 무조건 합격이므로, 서류 1등의 면접 순위를 rank변수에 저장해준다. 아래로 내려가며 면접 순위를 비교해준다. (서류를 기준으로 오름차순 정렬을 했기에 서류 순위는 비교대상보다 무조건 낮기에 면접 순위만 비교해주면 된다.) (1 4) (2 3) 을 비교하면, 면접 순위가 뒷사람이 더 높으므로 합격이다. 밑에 사람과 순차적으로 비교하며, 면접 순위가 더 높다면, 그 사람은 합격이므로 rank를 그사람의 순위로 업데이트 시켜준..