코딩 테스트31 위상정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미 예시) 선수과목을 고려한 학습 순서 설정 그래프 + 순서(단 방향이여야 한다.) 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (O) 자료구조 → 고급 알고리즘 → 알고리즘 (X) 아이디어 : "제일 먼저 올 수 있는 정점은?" = 0인걸 먼저 찾기 위상정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다 정점들의 Indegree, Indeg[1...N] 계산하기 들어오는 간선이 0개인(Indeg[i] == 0) 정점들을 찾아서 자료구조 D에 넣기 D가 빌때까지(Queue) D에서 원소 x를 꺼내서 "정렬"시키기 Graph 에서 정점 X "제거".. 2023. 3. 2. [프로그래머스] N-Queen 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 정말 5번이상 풀었지만 계속 풀이법을 근접할 뿐 풀지를 못했다.... 담에는 풀 수 있겠지...?? cols = [] result = 0 def Check(row, col): global cols for i in range(row): if cols[i] == col: return False if row - col == i - cols[i]: return False if row+col == i + cols[i]: return False return True def backtracking(row,n):.. 2023. 2. 20. [프로그래머스] [3차] 파일명 정렬 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 잘 풀었는데 s1과 s2 의 초기값을 잘못설정했다. s1은 만약 시작점이 "12abc" 일경우 한개는 HEAD이기 때문에 초기값을 0으로 설정하면 안된다. 또 s2는 for문에서 끝까지 가서 TAIL이 없을 경우를 대비해 초기값을 len(file) 이 옳다. def slice1(file): s1 = 1 s2 = len(file) for i in range(1,len(file)): if file[i].isdigit(): s1 = i break for i in range(s1,len(file)): if.. 2023. 2. 17. [프로그래머스] 롤케이크 자르기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 작성한 이유는 Counter를 잘쓰자는 의미이다.(난 왜이리 이 좋은 Counter을 안쓰는지 모르겠네) from collections import Counter def solution(topping): data1 = Counter(topping) data2 = set() result = 0 for t in topping: data1[t] -= 1 data2.add(t) if data1[t] == 0: data1.pop(t) if len(data1) == len(data2): result += 1 .. 2023. 2. 17. 까먹는 코테 문법2 1. 컴퓨터는 2진수 체계이기 때문에 실수 덧셈을 정확히 하지 못한다. 보통 5째 자리에서 반올림 하면된다. a = 0.3 + 0.6 print(rount(a,4)) 2. 거듭 연산자 a ** b # a의 b승 3. 자료형 변환 char ch = 'a'+1; # 자바 ch = chr(ord('a')+1) # 파이썬 4. 입력 # N개의 정수를 한 줄로 입력 받아 List에 저장할 경우 data = list(map(int, input().split())) # N개의 정수를 여러 줄에 걸쳐 입력 받아 List에 저장할 경우 N = int(input()) data = [int(input()) for _ in range(N)] # N개의 문자열을 여러 줄에 걸쳐 입력 받아 List에 저장할 경우 리스트 변환 s.. 2023. 2. 16. [백준] 개미 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 아......나는 뭔가 이런거는 잘 못푸는거 같다.... 그래도 tmp 대신 아래 풀이와 같이 푸는방법을 알게 되어서 다행이다. import sys input = sys.stdin.readline n1,n2 = map(int,input().split()) A = list(input().rstrip()) B = list(input().rstrip()) time = int(input()) A = A[::-1] sumAnt = A + B for _ in range(time): # 반복문을 통해 두 개미 그룹을 확인 for i in.. 2023. 2. 13. k진수에서 소수 개수 구하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 내가 왜 틀렸는지 솔직히 모르겠다.... (알려줄 사람....) 내가 푼 풀이는 에라토스테네스 체를 이용한 풀이이여서 이것이 더 빠른걸로 알고 있지만... 흐음,,,,내생객에는 소수범위를 어디까지 구해야 하는지 몰라서 그러는거 같다. 내가 푼 풀이 def sol1(number): for i in range(2,len(number)): if number[i] != 0: for j in range(2*i,len(number),i): number[j] = 0 def solution(n, k): str1 .. 2023. 2. 8. [프로그래머스] 캐시 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 한줄 정리 : 조건부 스택 이문제를 풀기 위해서는 먼저 LRU알고리즘을 알아야 한다. LRU알고리즘이란 페이지 교체 알고리즘이라고 하는데 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. 이 알고리즘이 사용되는 시기는 페이지 부재가 발생해 새로운 페이지를 적재 해야하나 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용된다. 페이지 교체 알고리즘의 종류로 페이지 부재가 발생했을 경우 가장 오랫동안 사용되.. 2023. 2. 6. [프로그래머스] N개의 최소공배수 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 최소공배수(lcm)을 만드는 문제이다. 최소 공배수를 만들기 위해서는 먼저 최대공약수(gcd)를 알고 있어야 한다. 그리고 최대공약수는 아래와 같이 라이브러리를 이용하여 할 수도 혹은 직접 만들 수 있다. import math def gcd(a, b): # 최대공약수 while b > 0: a, b = b, a % b return a a,b =12,20 math.gcd(a, b) gcd(a,b) 이제 위의 최대공약수를 이용한 최소공배수를 만들어 보자 import math def lcm(a, b): .. 2023. 2. 6. [백준] 수들의 합 2 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 이 문제는 투포인터 같이가기의 전형적인 문제이다. 먼저 문제는 A[i] + A[i+1] + … + A[j-1] + A[j] 처럼 합을 구하는 형식이기 떄문에 같이 가야한다. 아래의 풀이 방식은 시작은 left만 더한 상태로 sum 의상태를 보고 미리 가르키고 있는 right를 더한 후 right를 +1 인덱스 추가 시켜주는 방식이다. 이 방식은 sum 이 m 보다 큰데 가르키고 있던 right가 n을 초과하면 더이상 없다.. 2023. 2. 3. [프로그래머스] 징검다리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제에서 기준은 n개의 돌을 징검다리에서 제거했을 때 최소 거리이다. 먼저 범위를 생각해보면 최소값은 징검다리에 돌이 겹쳐있는 경우는 없기 때문에 1이다. 최대 값은 시작지점과 도착지점사이의 거리인 distance이다. 이 값을 기준으로 중간값(mid)가 n개의 돌을 제거했을 때 돌 사이의 거리중 최소값이라고 가정해보자. 이 가정하에 돌을 제거했을 때 이 값(mid)보다 작은 거리는 없어야 한다. 즉 돌 사이의 거리를 구했을 때 이 mid 값보다 작으면 제거하고 크면 두는 방식의 전략을 사용해야한다. 돌.. 2023. 2. 2. 이분 탐색 & 매개변수 탐색 & 투 포인터 탐색 이분 탐색 vs 매개변수 탐색 vs 투 포인터 이분 탐색 : 정렬된 배열에서 중앙값(mid)이 가리키는 값이 내가 찾는 값인지가 중요 (대표 문제) 매개변수 탐색 : 배열에서 목표(target)가 원하는 조건에 만족할 때까지 최대한 찾는 것이 중요 (대표 문제) 투 포인터 : 배열에서 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리 (대표 문제) 이분 탐색 매개변수 탐색 투 포인터 시간 복잡도 O(logN) O(logN) O(N) 가정 데이터 정렬 x x 방식 mid를 활용 하여 매 연산마다 탐색의 범위를 절반으로 좁혀 나감 target과 일치하는 값을 찾아도 더욱 최적의 해가 있을때까지 찾아나감 양끝 혹은 모두 왼쪽에서 한칸씩 이동하며 알맞은 값 을 찾아나감 이분 탐색 이분 탐색이란 데이.. 2023. 2. 2. [백준] 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 먼저 이문제가 이분 탐색인 이유에 대해 생각해보자 우리의 조건은 거리가 얼마나 최대한 멀게끔 하는것이다. 알아봐야 할 부분은 중요한 것은 집들이 수직선상에 위치하고 있다는 것을 생각해야 한다는 점이다. 풀이 1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬. 2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 ) 3. 앞.. 2023. 2. 2. [백준]평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 유명한 냅색 알고리즘 이다. 냅색(Knapsack: 배낭) 알고리즘이란 담을 수 있는 물건이 나눌수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g등) : 분할 가능 배낭문제 담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제이다. 냅색 알고리즘은 문제를 보면 생각나는 방법은 두가지정도이다. 1. 모든 경우의 수를 넣어본다. -.. 2023. 2. 2. [프로그래머스] 표 병합 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 잘 알려진 유니온 파인드 문제 -> 두개의 집합을 공통 부모를 찾는 문제 1. 50 X 50 이중 리스트 2. 상위 셀은 (r, c)가 작은 순서대로 정함 cell1(r1,c1), cell(r2,c2)에 대해서 -> r1 r1 == r2, c1 < c2 cell2가 부모 2023. 2. 1. 이전 1 2 3 다음
