🌷맹이나라🌻

1. 문제 www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 접근 방법 경로를 어떻게 담냐가 관건이었다. 처음에 ㅋㅋㅋㅋ 아무 생각없이 그냥 2차 행렬 만들어서 다 집어넣었다가 메모리 초과 바로 나버리고 그 전 인덱스만 담았다. 그렇게 해서 최종 인덱스에 도달했을 때, 하나씩 pop 해서 프린트했다. 3. 코드 python from collections import deque def bfs(n): global visite..

1. 문제 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 접근 방법 deque로 해서 x*2를 먼저 해결했다. 3. 코드 python from collections import deque def bfs(n): q = deque() q.append(n) visited[n] = 0 while q: x = q.popleft() if x == K: print(visited[K]) return for nx in (x*2, x+1, x..

1. 문제 www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 2. 접근 방법 순서를 어떻게 잡아야할까 하다가 서치를 조금 했다. C++은 next permutation이라는게 있다고 한다. (codedrive.tistory.com/386) [BOJ]10972. 다음 순열 문제: 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오. 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 codedrive.tistory.com 알고리즘 로직은 이대로 ..

1. 문제 www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 2. 접근 방법 매우 그리디하게 접근 했습니다. 3. 코드 python E, S, M = map(int, input().split()) year = 1 while True: if (year-E)%15 == 0 and (year-S)%28 == 0 and (year-M)%19 == 0: print(year) break year += 1 4. 마치며 이거 나머지로 접근하면 될 거 같은데, 1부터 접근해도 되나..

1. 문제 www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 2. 접근 방법 스타트와 링크는 N//2였지만! 링크와 스타트는 팀 당 최소 1명 이상이면 된다 ! 그래서 여태껏 시간초과를 내다가 드디어 풀었다 ! 후우~! 일단 팀 당 최소 1명 이상이면 되니까 1명, 2명, ..., N//2명 까지만 뽑는 경우의 수를 세면 된다. N//2이상의 경우 중 N-1명을 뽑는 경우의 수를 예로 들자면, (N-1명을 뽑는거)랑..

1. 문제 www.acmicpc.net/problem/20127 20127번: Y-수열 N개의 정수로 이루어진 수열 a1, ... , aN이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다. 증가수열은 모든 i(1 ≤ i < N)에 대해서 ai ≤ ai+1을 만족하는 수열이고, 감소수열 www.acmicpc.net 2. 접근 방법 드디어 풀었다 ㅠ 못 푼 문제에 들어있는게 싫어서 ^^,, 몇 번이나 시도했는지 모르겠다 후우 ~!,, 나는 계속 증가 or 감소 둘 중 하나로만 풀려고 했는데, 결국 1. 증가 수열이라고 생각했을 때 2. 감소 수열이라고 생각했을 때 이렇게 두 개로 나눠서 풀었다. 1. 증가 수열이라고 생각 했을 때 1-1. 앞에서부터 쭈욱 확인하다가 감소하는 지점이 존..

1. 문제 www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 2. 접근 방법 와우오아오아우와웅 완전 딱 처음에 봤을 때는 순열을 구하면 되겠다라는 생각을 했는데 문자열 길이가 3000까지 되는 걸 보고 순열은 글러먹었다 라는 생각을 했다. 그 다음에는 그냥 word 안에 존재하는 문자일 경우에만 문자열에서 슬라이싱 해서 봐주면 되지 않을까 ? 라는 생각을 했다. 이렇게 되면 대충 가지치기 할 수 있으니까 ?? 근데 생각해보니까 3..

1. 문제 programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 2. 접근 방법 1. 현재 n이 max인가 아닌가 확인 -- max를 확인하기 위해서 새로운 리스트 하나를 만듦 --- pop을 max리스트만 해주는 이유는 n을 확인하기 위해서! 1-1. max라면 max리스트에서 pop하고 isPrint를 뜻하는 visited[n] = True를 해준다. 그리고 answer += 1을 해준다. 1-1-1. 만약 max인데 locat..

1. 문제 programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 2. 접근 방법 스택을 이용하면 된다. 1. 기능 개발하는데 걸리는 시간 구해서 리스트에 담기 2-0. 기능 개발하는데 걸리는 시간 리스트 순회하며 현재 값이 전 값과 같거나 작다면 cnt += 1 2-1. 현재 값이 전 값보다 크다면 현재 cnt를 answer에 append하고 cnt 를 1로 초기화 이렇게 생각했다. 3. 코드 python def solu..

1. 문제 www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 2. 접근 방법 조합으로 2개만 뽑아가지고 총 키에서 그 2개의 합을 뺀 값이 100이 나오면 바로 프린트하고 exit()해서 빨리 끝냈습니당. 3. 코드 python def comb(cnt, start): global pair if cnt == 2: if sum(heights) - sum(pair) == 100: for i in heights: if i != pair[0] and i != pair[1]: p..