일지 & 개발

문제 요약 알고리즘 분류: 트리, 탐색 난이도: Silver2 문제내용: 루트가 1이라고 가정할때 2번 노드부터 N개까지의 부모노드를 출력해라. 사이트: https://www.acmicpc.net/problem/11725 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 이번 문제는 트리의 활용과 트리의 탐색에 대한 내용을 알고있으면 풀수있다고 생각한다. 트리에 대한 자세한 설명은 여기에서 확인 해보면 된다. 문제 접근 방법 일단 예제 1번을 그림 으로 대충 표현한다면 아래와 같다. 왼..

문제 요약 알고리즘 분류: 힙, 우선순위 큐, 자료구조 난이도: Silver2 문제내용: 선물N개와 아이들 M개가 있다. 아이들은 순서대로 선물 N개 선택할수 있고 이전에 선택된 선물을 또 선택가능하다. 아이들이 원하는 선물개수가 없는 경우 실망한다. 아이들이 실망 하지 않고 선물을 다 가져 갈수 있는지 확인해라.. 사이트: https://www.acmicpc.net/problem/23757 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 문제풀이 이번 각 10^5개 데이터라서 O(NM)으로 풀면시간이 초과가 된다. 그래서 O(MlogN)이 나오도록 처리를 해야 한다. 그러기..

문제 요약 알고리즘 분류: 수학, 조합 난이도: Silver3 문제내용: 조합 결과값을 출력해라 사이트 주소: https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제풀이 이번 문제는 조합 공식만 알면 되는데 파이썬같은 동적 변수타입은 문제 없지만 정적 타입 선언 해야 되는 언어는 long타입 선언해도 결과값이 오버 되기때문에 그점을 유의 하면서 풀면 된다. Code Python 파이썬은 어떤 방식으로 풀어도 된다. 그래서 factorial과 comb 사용 법만 알면된다. from math import factorial n, m = map(int, input()...

문제 요약 알고리즘 분류: 힙, 우선순위 큐, 자료구조 난이도: Gold2 문제내용: 숫자가 추가될때마다 정렬해서 가운데 숫자를 출력하면된다. 사이트: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 이번 문제는 힙으로 풀어야 한다. 하지만 힙을 구하는 목적은 최대값, 최소값인데 중간 크기를 구하는 힙은 없어서 어느정도 생각해서 풀어야 될 문제이다. 힙 관련된 자세한 내용은 아래의 사이트에서 확인 헤보면된다. https..

문제 요약 알고리즘 분류: 이분탐색 난이도: Gold2 문제내용: 수열 A가 주면 가장 긴 증가하는 수열의 길이를 구해라 사이트: https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제풀이 이번 문제는 LIS문제인데 1,000,000크기 데이터로는 DP로 풀기에는 시간 초과가 난다. 그래서 이분 탐색으로 풀어야 된다. 그 부분은 아래의 사이트에서 확인 해보면 된다. 아래 사이트에 이분 탐색으로 구현한 코드있으면 거기 코드 보고 약간 추가만 해주면..

문제 요약 알고리즘 분류: 이분탐색 난이도: Gold2 문제내용: 크기 N×N 배열이고 시작 인덱스는 0이 아니고 1부터 시작한다. 배열 A[i][j]의 값은 i × j이다. 2차원 배열 A를 일차원 배열 B로 만들어서 오름차순으로 정렬하면 배열 B에서 K번째 인덱스 값을 구해라 사이트: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제풀이 이번 문제는 간단해 보일거 같은데.. 배열 A에서 완전탐색으로 값을 넣..

문제 요약 알고리즘 분류: 큐, 데크 난이도: Silver4 문제내용: 배열 담을수 있는 공간 N 원소는 첫뻔째 원소만 뽑을 수 있다. 앞에 원소를 뒤로 옮길수 있다. 뒤에 원소를 앞으로 옮기수있다. M개의 빼야될 목록을 주면 최소 몇번 이동해야는 구해라. 문제풀이 이번 문제 큐와 데크에 관련된 문제이다. 일반적으로 배열이나 리스트로 구현하기에는 힘들어서 모듈을 들고 와서 처리를 해야한다. 큐와 데크에 대한 자세한 내용은 아래의 사이트에서 확인하면된다. https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0) 큐(자료구조) - 나무위키 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다. 서로 다른 쓰레드 사이 또는 프로..

문제 요약 알고리즘 분류: 문자열 난이도: Bronze5 문제내용: 앞뒤 공백없음 입력받은대로 그대로 출력해라 문제풀이 이 문제는 여러줄 입력해서 처리하는 방법을 알면된다. 언어의 예외처리나 문법적인 지식으로 풀어야 될 문제이다. Code Python EOFError대한 예외처리만 하면된다. while(True): try: print(input()) except EOFError: exit() Java 조건문 안에 변수 선언하는 방법을 알자 String이 객체라서 아무런 값이 없을때 null로 조건 걸면된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main ..