일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- google coding competition
- nlp
- 프로그래밍
- 파이썬
- AI
- 코딩테스트
- 코딩 테스트
- BFS
- CSS
- 네트워크
- 리눅스
- kick start
- 백준
- 프로그래머스
- 코딩
- 순열
- 그래프
- 킥스타트
- dp
- OS
- DFS
- 동적 프로그래밍
- 브루트포스
- 딥러닝
- 운영체제
- 구글 킥스타트
- linux
- 동적프로그래밍
- PYTHON
- 알고리즘
- Today
- Total
목록코딩 테스트 (127)
오뚝이개발자
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 나의 풀이 DP를 사용하는 문제이다. 메모리 제한이 아주 극심해서 여기에 신경쓰면서 코드를 구현해야 한다. 2차원 리스트로 DP를 구현하면 메모리 초과가 발생하므로 각각의 변수에 저장하도록 한다. 코드 # https://www.acmicpc.net/problem/2096 import sys input = sys.stdin.readline N = int(input()) dp = [list(map(int, i..
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 나의 풀이 먼지 확산, 먼지 이동 이 두 가지 함수를 짜면 된다. 확산 함수를 짤 때 유의할 점은 먼지가 이미 있던 곳으로도 확산이 일어난다는 점이다. 먼지 이동 함수를 짤 때 유의할 점은 공기청정기를 기준으로 해서 위 아래 순환 방향이 다르다는 점과 공기 청정기로 들어간 먼지는 소멸한다는 점이다. 이동 함수를 짤 때 range 설정이 조금 까다롭긴 하나 차근차근 따져보면 풀 수 있다. 제..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 나의 풀이 방법은 두 가지가 있다. s -> v1 -> v2 -> n s -> v2 -> v1 -> n 각 경로가 최소가 되는 것을 찾으면 최종경로 또한 최소가 된다. 따라서 s, v1, v2를 시작점으로 해서 다익스트라 알고리즘을 3번 돌린 뒤에 위 두 경로 중 최단거리를 print하면 된다. 코드 # https://www.acmicpc.net/..
문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 나의 풀이 우선순위큐를 사용해서 풀면 된다. 큐에 삽입할 때는 시간이 빠른 순서로 정렬될 수 있도록 (시간, 위치)의 순서쌍을 넣어준다. 주의할 점은 삽입하는 순서인데, x 위치에서 가능한 총 경우의 수는 x-1, x+1, 2x의 세 가지이다. 이 때 순간이동을 하는 경우 소요되는 시간이 0초로 가장 짧으므로, 2x의 위치를 먼저 삽입한 뒤에 방문검사를 해서..
문제 https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b933#problem Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 보통 이런 문제는 그리디 방식으로 풀면 되고, 시간복잡도를 고려하면 중간의 range가 아닌 각 구간의 양 끝단에만..
문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a8e6 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 이 문제에서의 핵심은 주어진 조건 Z의 상한이 10^8인데 1~10^8까지의 소수를 모두 구할 필요가 없다는 것이다. 또한 탐색을..
문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 BFS를 사용하면 된다. 핵심은 상자가 많은 칸의 주변을 먼저 채워준다는 것이다. 이를 위해 우선순위 큐를 사용하였다. 생각해보면..
문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c509#problem Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 본 무제는 DP를 사용하는 문제이다. test set 2의 사이즈를 보면 유추할 수 있겠지만 대략 O(R*C) 시간..