문제 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생이 인접한..
Koala - 9기/코딩테스트 준비 스터디
문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 코드 풀이 입력되는 숫자를 모두 받아서 정렬하는 방법으로 코드를 짰는데 메모리초과만 나서 heapq를 쓰는 방안을 찾게 되었다. ㅇheapq의 크기가 5보다 크면 최솟값을 빼내고 입력받은 값을 집어넣고, 아니면 그냥 넣고 크키가 5일때와 그 이상일때로 나누어 뒤에서 5번째인 수를 출력한다.
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 분석 정사각형 보드 위에서 뱀이 움직이는데, 자신의 몸에 닿거나 벽에 닿으면 끝나는 게임이다. 뱀은 사과를 먹을 때만 몸이 길어지고, 그 외에는 항상 동일하다. 사과를 먹으면 꼬리는 제자리에 남아있고, 머리만 한 칸 이동한다. 사과를 먹지 않으면 머리도 한 칸, 꼬리도 한 칸 이동한다. 주의할 점은, 꼬리는 머리가 이동했던 경로를 따라서 이동해야 한다는 점이다. 또한 뱀은 방향을 전환할 수 있다. ..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 ..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 분석 난이도 골드4 분류 스택 들어가기 전에 대략적인 시간복잡도 계산을 할 수 있다면 어려울 것이 없는 문제. 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자..
https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def solution(progresses, speeds): answer = [] for i in range(1, 101): cnt = 0 for n, j in enumerate(speeds): progresses[n] = progresses[n] + j while progresses: if progresses[0] >= 100: progresses.pop(0) speeds.pop(0) cn..
https://www.acmicpc.net/problem/20956 20956번: 아이스크림 도둑 지호 지호는 매일 아이스크림 가게에 방문한다. 아이스크림을 먹던 지호는 놀라 자빠질 수밖에 없었다. 실수로 민트초코 맛을 먹었기 때문이다. 대다수의 사람은 치약 맛이 난다는 이유로 민트초코 www.acmicpc.net 0. 잡설 deque에 배열을 선언할 수 있다는 사실을 간과하고 Priority queue로 풀려다가 많은 '틀렸습니다' 를 받았습니다. 풀었던 방법을 오래 기억하고 싶어 기록합니다! 지호가 민초를 먹고 배열을 어떻게 돌리던간에, 가장 양이 많은 아이스크림을 먹는다는 점은 바뀌지 않습니다. 그래서 Priority Queue의 top과 같은 원소를 배열에서 앞뒤로 찾으려고 했는데요, 45%쯤에서..
문제 https://www.acmicpc.net/problem/19591 Algorithm 1. 문자열을 파싱해 수와 연산자를 분리한다. 수는 vector에 push하고 연산할 수의 위치를 나타내는 변수left , right도 선언한다. 연산자는 맨 앞 혹은 맨 뒤의 것이 수행되므로, deque에 push한다. 2. 문제의 조건에 따라 연산을 진행한다. 앞의 연산자가 수행될 경우 vector[left]와 vector[left+1]를 연산하고, 뒤의 연산자가 수행될 경우 vector[right-1]와 vector[right] 연산한다. 연산 결과는 각각 vector[left+1]과 vector[right-1]에 담긴다. - 문자열은 어떻게 파싱하는가? 1. 문자열을 순회하며 첫 번째 연산자를 제외하고, 연..
어떤 것을 pop 할지를 잘못 생각해서 삽질한 문제 스택에서 없애야 할 것 건물이 더 이상 확장할 수 없는 경우, pop 한다. 입력으로 들어온 Y가 스택의 상단 T보다 작다면, (Y < stack().top()) 높이 T를 가지는 건물의 범위는 거기서 끝나기 때문에, 더 이상 스택에 있을 필요가 없어진다. 스택에 넣지 말아야 할 상황 건물의 영역이 이어지는 경우, 스택에 push 하지 않는다. (Y == stack.top()) 입력으로 들어온 Y가 스택의 상단 T와 같다면 스택에 넣지 않는다. 고층 건물에 대한 정보가 삭제된 후, 바뀐 스택의 상단 T가 N과 높이가 같다면, 높이 N의 건물이 계속되는 형태기 때문에, 따로 카운팅을 할 필요가 없어진다. 스택에 넣어야 하는 상황 스택이 비어있을 때와, 입..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고..
문제 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다. 하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다. 꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다. 꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다..
수학적 관찰이 필요한 문제 문제는 진짜 잘 만들었지만 증명하는 데 꽤 오래 걸렸다 코테에서 이렇게 나오면 시간 내에는 못 풀 거 같다. 완전 탐색 매 요청마다 리그전의 재미를 계산한다. Q = 200,000, N = 100,1000, l = 1, r = 100,000 인 경우 200,000 * N!로 시간 초과가 발생한다 완전 탐색 최적화 각 후보 디비전을 계산할 때, 공통적으로 계산되는 부분이 있을 것이다 이를 알기 위해 1번 팀부터 N 번 팀까지 리그전을 진행할 때 생기는 재미에 대한 식을 나열해 본 결과 공통되는 식이 있단 것을 알 수 있다. 아래 표는 예제 1을 풀어쓴 결과다. 표를 보면 1 ~ 3 팀까지 리그전을 할 경우 계산 결과에, 1 ~ 2팀끼리 리그전을 한 계산들이 포함된 것을 알 수 있..
