오뚝이개발자

문제 https://codingcompetitions.withgoogle.com/kickstart/round/00000000008caa74/0000000000acee89 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 나의 풀이 1. 약수를 구하는 함수 findFactors()를 만든다. 2. 팰린드롬인지를 판별하는 isPalindrome() 함수를 만든다..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 나의 풀이 BFS를 사용하여 풀었다. 걸린 시간 외에도 경우의 수를 카운트해야 하므로 방문 체크를 일반적인 방식으로 하면 안된다. 일반적인 경우처럼 방문한 곳은 다시 가지 않도록 하면 K까지의 경우의 수는 언제나 1이 되기 때문이다. 따라서 visit 체크를 2가지 경우로 나누어주어야 한다.(아래 코드 참고) 코드 # https://www.acmicpc...

문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 나의 풀이 bfs를 사용하여 풀면 된다. 1. bfs를 (0,0)에서부터 시작한다. 2. 도중에 공기칸을 만나면 큐에 넣어주고, 치즈칸을 만나면 1을 더해준다. 3. 한 번의 bfs를 돌고나서 값이 3 이상인 칸은 2면 이상이 공기와 접하는 것이므로 이 칸의 치즈를 0으로 만든다. 4. 1~3을 모든 치즈가 녹을때까지 반복 코드 #https://www.acmicpc.net/pro..

문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 나의 풀이 dp를 사용하면 된다. dp 2차원 리스트에 각 위치에는 (0,0)부터의 부분합을 저장한다. 주황색 부분의 부분합을 구하려면 전체 합에서 A, B, C 부분을 빼주면 된다. 식으로 나타내면, (x2,y2)까지의 부분합 - (A+B) - (A+C) + A 가 된다. A부분이 두번 빼지니까 마지막에 한 번 더 더해주면 된다. 코드 # http..

문제 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의 위치를 먼저 삽입한 뒤에 방문검사를 해서..