일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 동적 프로그래밍
- 알고리즘
- 순열
- DFS
- dp
- 네트워크
- 구글 킥스타트
- BFS
- PYTHON
- CSS
- 파이썬
- AI
- 코딩 테스트
- 동적프로그래밍
- kick start
- 코딩테스트
- 운영체제
- linux
- google coding competition
- 프로그래머스
- nlp
- 딥러닝
- 코딩
- 그래프
- OS
- 백준
- 프로그래밍
- 킥스타트
- 브루트포스
- 리눅스
- Today
- Total
목록코딩 테스트 (127)
오뚝이개발자
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 DP를 사용해 쉽게 풀 수 있는 문제이다. input으로 주어진 각 수는 아래의 연산 중 한 가지를 할 수 있다. 2로 나누어 떨어지면 2로 나눈다. 3으로 나누어 떨어지면 3으로 나눈다. 1을 뺀다. 이를 반복해서 결과적으로 1이란 수를 만들어야 하는데, 이를 DP의 점화식과 연관지어 생각해보면 쉽다. 만약 내가 10이란 수를 input으로 받는다고 가정해보자. 10->5->4->2->1 10->9->3->1 10->9->8->7->...->1 위의 경우 말고도 10을 1로 만들기 위해선 굉장..
문제 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 나의 풀이 양끝에서부터 하나씩 이동시켜가면서 서로 문자를 비교해보면 된다. 왼쪽에서 오른쪽으로 가는 포인터를 l, 오른쪽에서 왼쪽으로 가는 포인터를 r이라고 하자.(two pointer 방식) l = 0, r = len(a)-1로 초기화 해주고 a[l]과 a[r]을 서로 비교해준다. a[l] == a[r] -> l += 1, r -= 1 a[l] != a[r] -> print("no")하고 break 여기서..
문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 나의 풀이 정규표현식을 사용하면 되는 문제이다. 약간 신경써야할 부분은 re의 match()함수가 아니라 fullmatch() 함수를 사용해야 한다는 점이다. match()의 경우 일치하는 부분문자열이 있는 경우 True를 return하지만 문제에서 요구하는 것은 문자열의 처음부터 끝까지 해당 정규표현식의 규칙을 가진 경우를 detection해야 한다. 따라서 fullmatch()..
문제 https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 리트코드 풀이를 하다가 굉장히 재미있는 문제가 있어 가져와봤다. 문제는 간단하다. 리스트와 타겟이 주어지면 그 리스트의 3개의 원소의 합이 타겟과 같아지는 그룹을 return하는 문제다. 여기서 포인트는 단순히 3중 for문으로 구현하면 시간초과가 난다는 것이다. 다른 방법을 고안해야 하는데 그 풀이가 굉장히 흥미롭다. tw..
문제 https://leetcode.com/problems/integer-to-roman/ Integer to Roman - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 2가지 방법으로 풀이했다. 첫 번째 방법은 좀 naive한 풀이이고, 두 번째 방법은 변환의 규칙을 파악한 풀이이다. SOL 1) 문제에서 주어진 조건이 num의 범위가 [1,3999]이므로 이 범위 안에서만 변환을 생각하면 된다. 예컨대, 256을 변환하려면 200+50+6으로 분..
문제 https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 나의 풀이 사실 처음엔 itertools 모듈의 중복조합을 사용해 구했다. 물론 답은 맞았지만 조금 더 nice해 보이는 코드가 있어 첨부한다. 이 문제는 브루트 포스 문제로 그냥 가능한 경우를 모두 카운트 해주면 된다. 문제에서 주어진 조건 중 1000이하의 자연수만 입력으로 주어진다고 했기 때문에 1000 이하의 모든 유레카 수를 구해두면 된다. eureka라는 flag 배열을 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 나의 풀이 뭔가 그래프 문제라서 복잡한 알고리즘을 써야할 줄 알았는데 생각보다 간단하게 해결했다. 자식-부모의 pair로 이루어진 dictionary를 활용해 반복적으로 돈을 분배하면 된다. 이 때 반복문의 종료 조건은 center까지 도달해 분배가 끝나거나 혹은 나눌 돈의 10%가 1원 미만(문제에서 주어진 종료조건)이다. 문제의 조건에서 10%를 ..
문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 나의 풀이 위상 정렬을 사용해 푸는 대표적인 문제이다. 위상 정렬의 개념을 모르겠으면 이 글을 참조하기 바란다. 코드 # https://www.acmicpc.net/problem/2252 n, m = list(map(int, input().split())) # adjacent list adj_list = [[] for _ in range(n+1)] ..