개발 로그

https://www.acmicpc.net/problem/11724 💡문제 분석 요약 방향없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하라 💡알고리즘 설계 1. 그래프를 연결리스트로 저장한다. 2. 그래프에 저장된 노드를 하나씩 방문한다. 2-1. 하나의 노드에 연결된 노드들을 연결 리스트로 저장하여, 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 차례로 방문한다. 2-2. dfs 함수가 더이상 호출되지 않고 끝나면 연결 요소를 모두 찾은 것이므로, 함수 호출이 끝나 연결되지 않은 다음 노드를 방문하게 되면 카운트를 하나 더하고 새 연결 요소 방문을 시작한다. 💡코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N, M..

https://www.acmicpc.net/problem/11478💡문제 분석 요약문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 💡알고리즘 설계for문을 이용해 첫번째 문자로 시작하는 문자열, 두번째 문자로 시작하는 문자열 등을 순서대로 구하여 set에 추가한다. 중복처리를 위해 set을 이용하고, set의 크기에서 1을 뺀 값을 리턴한다. 💡코드S= input() len_S=len..

https://www.acmicpc.net/problem/10816💡문제 분석 요약상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.💡알고리즘 설계1. 이분 탐색 방법 중복된 값이 있을 때 그 값이 제일 앞에 있는 위치와 제일 뒤에 있는 위치를 구하는 함수를 만들고, 위치의 차를 출력한다. upperBound 구하기: 이분 탐색을 하다가 탐색값이 타겟과 일치하거나 작은 경우 lo를 mid+1로 설정하고, lo가 hi보다 커지면 lo를 리턴한다. lowerBound 구하기: 이분 탐색을 하다가 탐색값이 타겟과 일치하거나 큰 경우 hi를 mid-1로 설정하고, lo가 hi보다 커지면 lo를 리턴한다. ..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1)한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해www.acmicpc.net백트래킹을 연습해보고 싶어서 고른 문제이다. 쉬운듯 어려운듯.. 💡문제 분석 요약자연수 N과 M이 있을 때, 1에서 N까지 길이가 M인 수열을 출력한다. 한 수열에 중복되는 수가 있으면 안된다. 💡알고리즘 설계1. search 함수에서, 1에서 N까지 숫자를 하나씩 list에 추가하고 함수를 다시 호출한다. 2. list의 길이가 M+1과 같다면 수열을 프린트하고 리턴한다. 3. list의 제일 마지..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💡문제 분석 요약 수빈이는 1초에 X-1, X+1, 2*X로 이동할 수 있다. 동생의 위치로 이동하기까지 걸리는 가장 작은 시간을 구하라 💡알고리즘 설계 DFS 문제로 큐를 사용한다. 현재 수빈이의 위치를 큐에 넣고, 그 위치에서 X-1, X+1, 2*X로 이동시킨 후 visted[]에 1을 하나씩 더해 이동에 걸린 시간을 저장한다. 빈 큐에 현재 수빈이의 위치를 추가 ..