상상쓰

https://programmers.co.kr/learn/courses/30/lessons/87391 코딩테스트 연습 - 공 이동 시뮬레이션 n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리 programmers.co.kr 처음에는 BFS로 접근하려고 했으나 범위를 보고 다르게 생각하였다. 이분 탐색인가 했으나 방법이 떠오르지 않았고 답이 사각형 모양으로 나와 범위를 기억하는 것으로 접근하였다. 범위를 top, left, right, bottom 으로 변수를 받아 기억하였고 구하면 해당 좌표를 가진 사각형의 넓이를 구하면 된다. ..

https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 11주차 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 1) 테두리 좌표 기억하기 2) BFS 알고리즘 사용 으로 접근하였다. 테두리 좌표는 직사각형의 테두리와 내부를 board[][] = 1로 만든 다음, 내부를 board[][] = 0으로 바꿔준다. 어떤 직사각형에서 테두리가 다른 직사각형의 내부라면 board[][] = 0 으로 처..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net union-find 알고리즘을 사용하여 분리 집합을 표현하였다. 예를 들어, {1, 2, 3}, {4, 5} 인 집합에서 '0 3 5' 의 입력을 받으면 root[1] = 5, root[2] = 5, root[3] = 5, root[4] = 5, root[5] = 5로 하여 root[i] = 5가 나오는 i는 같은 집합의 원소라고 할 수 있다. 5가 아닌 ..

https://programmers.co.kr/learn/courses/30/lessons/87390 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr [1, 2, 3, 4, ...] [2, 2, 3, 4, ...] [3, 3, 3, 4, ...] [4, 4, 4, 4, ...] . . . 로 진행하는 배열로 규칙을 찾아서 구해주면 된다. 위치를 i 라고 한다면 i 를 n 으로 나누면 i 에 해당하는 행과 열을 구할 수 있다. 위의 규칙으로 봤을 때 해..

https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 각 층의 방의 개수가 같으므로 W 는 무시해도 된다. divmod 를 이용하여 몫과 나머지로 방 번호를 구할 수 있다. 나머지가 0이 될 때만 주의해주면 된다. import sys T = int(sys.stdin.readline()) for i in range(T): H, W, N = map(int, sys.stdin.readline().split()) q, r = divmod(N, ..

https://programmers.co.kr/learn/courses/30/lessons/87377 코딩테스트 연습 - 10주차 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 문제에 참고 사항에 친절하게 해를 구하는 공식이 나타나 있다. 이를 활용하여 해가 정수인 ..

https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 나는 몇 번의 과정을 거쳐서 64cm의 막대기가 Xcm가 됐는지를 구하는 줄 알았는데 막대기의 개수를 구하면 되는 문제였다. 이진수로 나타내어 1의 개수를 구하면 된다. import sys X = int(sys.stdin.readline()) answer = bin(X).count('1') print(answer)

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N = 5 로 예를 들면, N * N 배열은 아래와 같다. [1, 2, 3, 4, 5] [2, 4, 6, 8, 10] [3, 6, 9, 12, 15] [4, 8, 12, 16, 20] [5, 10, 15, 20, 25] 이분 탐색으로 나올 수 있는 수 중 최솟값인 1과 최댓값인 5*5(=25)를 시작으로 한 중간값(=mid)이 조건에 맞는지를 확인한다. 배열 안에 중..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 불금! import sys T = int(sys.stdin.readline()) dp = [[1, 0], [0, 1]] for i in range(39): dp.append([dp[-2][0] + dp[-1][0], dp[-2][1] + dp[-1][1]]) for i in range(T): N = int(sys.stdin.readline()) print(dp[N][0], end = ' ') print(dp[N][1])

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net A에 포함된 문자열을 한 개 이상 붙일 수 있으므로 dp[index] 가 1이면 이미 재귀함수로 A의 문자열로 S를 만들 수 있는지 확인하고 있으므로 무시해도 된다. DFS 알고리즘으로 S = 'softwarecontest' A = ['software', 'contest'] 라면 1) index = 0 (dp[0] = 1) : softwarecontest(= S[0:]) 와 ..