본문 바로가기

전체 글182

[백준 18870- 좌표 압축][파이썬]-23일차 https://www.acmicpc.net/problem/18870 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 제한 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 109 예제 입력 1 복사 5 2 4 -10 4 -9 예제 출력 1 복사.. 2022. 6. 17.
[백준 2630- 색종이 만들기][파이썬]-22일차 https://www.acmicpc.net/problem/2630 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로.. 2022. 6. 16.
[백준 9184 -신나는 함수 실행][파이썬]-22일차 https://www.acmicpc.net/problem/9184 KEY POINT: dp, 메모리제이션 사용 1. dp 재귀함수로 풀었더니 메모리 초과가 뜬다 -> dp와 메모리제이션을 생각함 2. 메모리제이션 조건은 이미 제시되어있으니까, dp를 활용해야함 20 넘어가면 20 처리해주니까 (이런 조건이 dp를 나타내는 키 포인트가 아닐까..?) 20을 범위로 해서 3차원 리스트 만들기 나머지는 조건대로 구현 해주고 만약 dp에 값이 있다면 return 해주는 조건을 달아서 50 50 50 이 넘어가는 조건도 처리 2022. 6. 16.
[백준 1010 -다리 놓기][파이썬]-22일차 https://www.acmicpc.net/problem/1010 -- 메모리 초과 팩토리얼 코드 -- DP 정답 코드 KEY POINT: dp 로직 적용하기 1.dp 2022. 6. 16.
[프로그래머스- 타겟 넘버][파이썬]-21일차 https://programmers.co.kr/learn/courses/30/lessons/43165 KEY POINT: dfs 로직이해하기 1. 어려운 난의도 라고 생각이 들었다 2. 양수로 더하든 -1로 더한 현재 값 처리를 둘 중에 하나로 하고 dfs 재귀 로직을 실행시키기 3. s==len(numbers) . 탐색이 끝나면 target에 맞으면 1 아니면 0 반환 2022. 6. 15.
[프로그래머스- 메뉴 리뉴얼][파이썬]-21일차 https://programmers.co.kr/learn/courses/30/lessons/72411 KEY POINT: Counter(most_common()), combinations 1. Counter Counter개념으로 각각의 원소가 몇개씩 있느지를 카운트하는 것이 핵심이었다고 생각한다. 다만 combinations에 접근할 때 join과 sorted 로 미리 잔처리를 해주는 것도 시간 절약에 중요했다 2. combinations a,b나 b,a 나 똑같으니까 combinations 사용 3. 전체 로직 가장 중요했던 포인트는 course 숫자에 맞게 따로따로 구별해주는 것이었다. => 길이가 2인 것들 따로, 3인 것들 따로, 4인 것들 따로 해줘야 비교가 편했다(여기서 푸는데 시간이 오래 걸.. 2022. 6. 15.
[CS 기초지식 알고리즘] -20일차 1. 탐색 - 선형 탐색 인덱스의 처음부터 끝까지 탐색 - 이진 탐색 배열이 sorted, 중간 인덱스부터 시작해서 작거나 큰 쪽으로 이동하며 탐색 2. 알고리즘 표기법 O, Ω 로 표기 O :실행 시간의 상한(최악의 수까지 고려했을 때의 알고리즘 속도) Ω: 실행 시간의 하한(최대로 운이 좋았을 때의 알고리즘 속도) 3. 선형 검색 typedef 이름 으로 새로운 자료구조를 형성해서 사용할 수 있다! 선형 탐색은 시간복잡도가 높은 알고리즘 4. 버블 정렬 두 개의 인접한 자료 값을 비교하면서 위치를 교환해나가는 방식 -> 너무 많은 시간이 걸릴 수 있음 자료가 sorted 되어있다면 O, else면 정렬하는 시간도 포함되어 마찬가지로 시간이 오래 걸린다 5. 선택 정렬 가장 작은 수를 찾아 첫 번째 위.. 2022. 6. 14.
[백준 14501 -퇴사][파이썬]-20일차 https://www.acmicpc.net/problem/14501 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는.. 2022. 6. 14.
[백준 9461 -파도반 수열][파이썬]-20일차 https://www.acmicpc.net/problem/9461 KEY POINT: 조건 파악 1. 조건 파악 조건에 예외가 되는 것들은 직접 지정하고, 삼각형의 변의 길이로 하는 조건을 찾았다 문제에서 n의 limit이 100이었기에 range를 조건 부합하는 수의 시작부터, 100까지 두고 append를 진행해서 골라 뽑기를 했다! 조건 찾으려면 0번부터 쭉 써보자! 2022. 6. 14.
[백준 1904 -01타일][파이썬]-20일차 https://www.acmicpc.net/problem/1904 --실패 코드(메모리 초과/ dp 로직 사용 X) --성공 코드(DP 로직 사용) KEY POINT: DP 로직, 수열조건 찾기 1. 수열 조건 n=1 1 1 n=2 00,11 2 n=3 001,100,111 3 n=4 0000,0011,1100,1001,1111 5 n=5 00001,00100,10000,00111,10011,11001,11100,11111 8 (n-1) + (n-2) 를 더한 가짓수 2. dp 로직 n의범위가 1,000,000, 메모리 초과 방지 2022. 6. 14.
[백준 9663- N-Queen][파이썬] 백 트래킹, dp -19일차 https://www.acmicpc.net/problem/9663 2가지로 풀이했다. back tracking, dp 1. 백 트래킹 key point: is_promising, x==n에 answer+=1 is_promising -> 같은 열에 있거나 대각선에 있으면 false를 return 해서 탐색을 하지 x if x==n: answer+=1 -> n번쨰 칸에 닿았을 때 -> 탐색이 완료 되었을 때, n에 안 닿았을 때는 퀸의 자리를 옮겨가면서 is_promising 로직 실행 후, 재귀적으로 한칸씩 키워서 0 -> 1 ->2 로 탐색 진행 --탐색 과정 n=4 x=0 else로 가게 되고 i=0 row[x]=0 (0,0을 의미) -> solution이 커져도 영향을 줌 if is_promosing.. 2022. 6. 13.
[프로그래머스- 조이스틱][파이썬]-19일차 https://programmers.co.kr/learn/courses/30/lessons/42860 참조 블로그: https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1-Greedy key point: A가 연속됨 -> A를 마지막에 처리해줌 2022. 6. 13.

티스토리툴바