본문 바로가기

알고리즘133

[백준 1764- 듣보잡][파이썬]-25일차 https://www.acmicpc.net/problem/1764 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 예제 입력 1 복사 3 4 ohhe.. 2022. 6. 20.
[백준 1244- 스위치 켜고 끄기][파이썬]-24일차 https://www.acmicpc.net/problem/1244 문제 1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. 에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다. 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. 과 같은 상태에서 남학생이 3을 받았다면, 이 학생은 와 같이 3번, 6번 스위치의 상태를 바꾼다. 여학생은 자기가 받.. 2022. 6. 18.
[백준 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.
[백준 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.

티스토리툴바