🌱1 Day, 1 Commit Wonseok's Record

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해설 : 수빈이는 A라는 위치에 있고 동생은 B라는 위치에 있다 (A, B)는 모두 자연수 수빈이는 현재위치 X에서 X+1, X-1, 2*X의 이동을 할 수 있다고 한다. 모든 연산엔 시간이 1씩 소모된다고 했을 때 동생을 찾는데 소모되는 최소 비용을 찾는 문제이다. 풀이 : 현재위치 X에 X+1, X-1, X*2 연산을 진행하며 X를 만날 때까지 실행되게 하였다. 지금..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 : N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제이다. 풀이 : 자릿수를 계산하기 위헤 뒤에서부터 10씩 나누어가며 0의 개수를 카운트해주고 0이 아닌 숫자가 나올경우 카운트를 출력하였다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys input = sys.stdin.readline if __name__ == "__main__": ans = 1 for i in range(1,int(input()..

https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 해설 : 숫자들로 이루어진 문자열 S가 주어질 때 K(Q) 라는 구조는 Q가 K번 반복된다는 의미이다. 이를 통해 원래 숫자들로 이루어진 문자열의 길이를 찾는 문제이다. 풀이 : Queue를 이용하여 (를 만났을 때, )를 만나기 전까지 숫자들을 합치고 이를 ( 앞의 숫자만큼 곱하여 원래 문자열로 더해주었다. 소스코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 해설 : K개의 랜선 길이가 주어지고, 이 K개의 랜선을 동일한 길이로 잘라 N개의 랜선을 만들려 한다. 이 때 자를 수 있는 랜선의 최대 길이를 찾는 문제이다. 풀이 : 이분탐색으로 쉽게 해결할 수 있는 문제이다. start는 0, end는 랜선의 길이들 중 최댓값으로 설정하고 각 탐색마다 자른 랜선의 개수가 K개보다 작으면 길이를 줄이고, 크거나 같다면 길이를 늘려..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 해설 : N개의 포켓몬 이름이 주어지고 알고 싶은 값이 포켓몬 이름(문자열) 또는 숫자로 주어진다. 문자열로 주어진 포켓몬 이름은 몇 번째 포켓몬인지 출력하고 (숫자로) 숫자로 주어진 번호는 그 번호의 포켓몬 이름을 출력하면 된다. (문자열로) 풀이 : 포켓몬의 이름과 순서에 대응하는 Dictionary를 만들어 값을 치환해주었다. 소스코드 : 1 2 3 4 5 6 7..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 해설 : 괄호가 있던 수식에서 괄호를 모두 뺐다. 100 + 20 - 30 + 50 과 같은 수식에서 괄호를 적절히 넣어 값을 최소로 만드는 방법을 찾는 문제이다. 풀이 : 간단한 아이디어로 해결할 수 있는 문제이다. - 부호를 만난다면 다음 - 부호가 나오기 전까지 모든 + 부호들을 괄호로 묶어주면 된다. 100 + 20 - 30 + 50 의 경우 100 + 20 - (30 + 50)이 최..

연결리스트(Linked List) 연결리스트란 ? 연결리스트(Linked List)는 링크드리스트라고도 부릅니다. (사실 저는 링크드리스트라고 더 자주 말합니다.) 어쨌던, 링크드리스트는 데이터와 포인터를 갖고 있는 노드들이 포인터로 연결되어있는 자료구조입니다. 그림으로 보면 쉽게 이해할 수 있으니 이미지를 첨부하겠습니다. head라는 글자가 가르키고 있는 노드가 있고, 이 노드에서 화살표가 나와 다음 노드를 가르킵니다. tail의 노드는 null을 가르키고 있습니다. 구조가 이해되시나요? 링크드리스트는 노드로 이루어져 있으며 이 노드들은 Data부와 Pointer부로 구별되어 있습니다. Data부에는 노드의 데이터가, Pointer부에는 다음 노드를 가르키는 포인터만이 적재될 수 있습니다. 또한 hea..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 해설 : 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 : DP문제이다. X가 3으로 나누어 떨어지거나, 2로 나누어 떨어질 때, X에서 3 또는 2를 뺀 인덱스의 DP값에 1을 더해서 갱신해주면 된다. 이 횟수가 항상 최솟값이다. 소스코드 : 1 2 3 4 ..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 해설 : 수리공 항승은 물이 새는 파이프를 테이프로 막으려고 한다. 테이프의 길이 L과 막아야 할 구멍의 개수 N이 주어지고 막아야할 구멍의 위치가 주어질 때, 테이프를 최대한 적게 사용하여 모든 구멍을 막는 경우를 찾는 문제이다. 풀이 : 그리디하게 해결할 수 있다. 구멍이 있는 위치를 만났다면, 이 때 최대한 많은 구멍을 막게끔 구현하면 되는 것이다. 핵심은 막은 첫 번째 구멍..