본문 바로가기

자료구조&알고리즘63

꼭 필요한 자료구조 기초 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 오버플로우(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 언더플로우(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로우가 발생한다. 스택 선입후출(First In Last Out)구조 또는 후입선출(Last In First Out)구조 e.g. 쌓아올린 박스를 연상 큐 선입선출(First In First Out) 구조 e.g. 놀이공원 줄을.. 2021. 5. 2.
[이.코.테] Chapter 04 구현 - 게임 개발 (Java) 게임 개발 문제 (교재 118p) 난이도 ●○○ | 풀이 시간 40분 | 시간 제한 1초 | 메모리 제한 128MB 문제 맵은 N x M 크기의 직사각형이며, 맵의 각 칸은 (A, B)로 나타낼 수 있다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어있는 공간에는 갈 수 없다. 매뉴얼은 아래와 같다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향을 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어있는 칸의 경우에는, 바라보는 방향을.. 2021. 4. 10.
[이.코.테] Chapter 04 구현 - 왕실의 나이트 (Java) 왕실의 나이트 문제 (교재 115p) 난이도 ●○○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB 문제 나이트는 L자 형태로만 이동할 수 있으며, 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 대는 a부터 h로 표현한다. 입출력 조건) 입력 조건 - 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표.. 2021. 4. 10.
[이.코.테] Chapter 04 구현 - 시각 (Java) 시각 문제 (교재 113p) 난이도 ●○○ | 풀이 시간 15분 | 시간 제한 2초 | 메모리 제한 128MB 문제 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우의 수를 구하는 프로그램을 작성하시오. 입출력 조건) 입력 조건 - 첫째 줄에 정수 N이 입력진다. (1 ≤ N ≤ 100) 출력 조건 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. 입출력 예시) 입력 예시 출력 예시 5 11475 문제 풀이 방법 모든 시각의 경우를 하나씩 세서 풀 수 있다. 왜냐하면 하루는 86,400초로 86,400가지밖에 존재하지 않기 대문이다. 경우의 수가 100,000개도 되지 .. 2021. 4. 10.
[이.코.테] Chapter 04 구현 - 상하좌우 (Java) 상하좌우 문제 (교재 110p) 난이도 ●○○ | 풀이 시간 15분 | 시간 제한 1초 | 메모리 제한 128MB 문제 아래와 같은 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오. L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로 한 칸 이동 D : 아래로 한 칸 이동 가장 왼쪽 위 좌표는 (1,1) 이며, 시작 좌표는 항상 (1,1)이다. 입출력 조건) 입력 조건 - 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100) - 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 ≤ 이동 횟수 ≤ 100) 출력 조건 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.. 2021. 4. 10.
구현 보호되어 있는 글 입니다. 2021. 4. 10.
[백준] 동적 프로그래밍 - 12865번 평범한 배낭(Java) 문제링크 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 처음에 1차원 배열로 계산하여.. 실패하였다.. 다른 블로그들을 보며 아래 소스코드 작성 방법을 참조하여 문제를 풀었다. 소스코드 작성 방법 a를 이중 배열로 선언 크기는 [n+1][k+1]로 i는 물건의 종류, j는 무게 a[i][j]에 i-1번째 물품을 넣었을 때의 가치를 넣음 (현재(j) 무게 - 물품의 무게) > 0 이라면 max(i번째 물건을 .. 2020. 12. 6.
[백준] 동적 프로그래밍 - 11051번 이항 계수 2 (Java) 문제링크 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 처음에는 예를 들어, $_{5}C_{2}$를 구한다 했을 때 $_{4}C_{0}$을 가장 먼저 구한 다음 차례 차례 조합 공식에 맞추어 $_{5}C_{1}$을 구하고 마지막 최종값을 구하도록 짰는데 틀렸다... 결국... 다른 분들의 블로그 도움을 받았다 T^T 이 문제는 파스칼의 삼각형을 이용하는 문제였다. (된장...ㅎㅎㅎ 언제 배웠는지도 기억이 안나는 데.. 이 이론을 기억할리가 있나 ㅎㅎㅎㅎ) 파스칼의 삼각형 이론 참조 링크 파스칼의 삼각형의 이론을 요약하여 예를 들면, 아래와 같.. 2020. 12. 1.
[백준] 동적 프로그래밍 - 11057번 오르막 수 (Java) 문제링크 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 아래 문제를 고군분투하며 풀고나니 이 문제는 쉽게 풀 수 있었다. 출처 : 2020/11/29 - [알고리즘/동적 프로그래밍] - [백준] 동적 프로그래밍 - 10844번 쉬운 계단 수 (Java) 끝자리가 0일 경우 : 앞자리에 0만 올 수 있다. (00) 끝자리가 1일 경우 : 앞자리에 0, 1 두가지가 올 수 있다. (01, 11) 끝자리가 2일 경우 : 앞자리에 0, 1, 2.. 2020. 11. 29.
[백준] 동적 프로그래밍 - 10844번 쉬운 계단 수 (Java) 문제링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이 방법 n=4일 때까지, 전부 나열해보고 규칙을 찾아보려 했지만 전혀 보이지 않았다. 앞자리가 0, 9일 때 다음 자릿수에 올 수 있는 건 한가지뿐이어서 각 n자리수마다 0과 9의 갯수를 세서 규칙을 찾아보려했지만, 발견하지 못했다. 그래서 다른 블로그들의 글을 보고.. 해결하였다. 끝자리가 0일 경우 : 앞자리에 숫자 1만 가능하다. (한가지) 끝자리가 1~8일 경우 : 끝자리를 i라고 한다면 앞자리에 숫자 i-1, 숫자 i+1 이 가능하다. (두가지) e.g. 끝자리가 1이라면 앞자리에 0, 2가 가능하다. 끝자리가 9일 경우 : 앞.. 2020. 11. 29.
[백준] 동적 프로그래밍 - 11052번 카드 구매하기 (Java) 문제링크 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 아래 문제를 응용하여 풀이방법을 생각해보았다. 출처 : 2020/11/10 - [알고리즘/이것이 코딩테스트다] - Chapter 08 동적 프로그래밍 - 효율적인 화폐 구성 (java) $p_{0,i}$ : 카드 i개가 포함된 카드팩의 단위 $p_{1,i}$ : 카드 i개가 포함된 카드팩의 가격 $a_{j}$ : 카드 j개를 갖기 위해 지불할 수 있는 최대 금액 $a_{j-p_{0,i}}$ : 카드팩에 단위를 $p_{0,i}.. 2020. 11. 28.
[백준] 동적 프로그래밍 - 1699번 제곱수의 합 (Java) 문제링크 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이 방법 이 문제를 며칠을 고민했는지 모른다 ㅠㅠ 결국, 다른 분들의 블로그 풀이를 보고 겨우.... 이해했다... 이해 잘 된 거겠지... 규칙을 찾기 위해 아래와 같이 나열하고, 그에 따른 점화식을 세워보자. $a_{n} = min(a_{n- {1}^{2}} + 1, a_{n-{2}^{2}} + 1 , ... , a_{n-{i}^{2}} + 1)$ ${i}^{2}$ 은 n보다 작은.. 2020. 11. 21.
반응형

티스토리툴바