갑갑이의 개발세상

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제도 단순하고, 난이도에 비해서 쉽게 푼 것 같다. 풀이 N자리 숫자가 주어졌을 때 가장 큰 수를 만들려면 앞자리 숫자를 가장 크게 만들어야 할 것이다. 그러면 앞에 숫자부터 비교해서 1. 다음자리 숫자가 나보다 큰 경우 && 아직 제거해야할 자릿수가 남은 경우 나를 지우고 다음숫자를 이어붙여준다. (1) 예를 들어 476127과 같은 경우 4 < 7이므로 4를 제거해야 함 (2) 76127 에서는 1 < 2 이므로 1을 제거 (3) 7627 에서는 2= c) break;..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 개인적으로 분할정복에 약해서 좀 어려웠던 문제이다. 아이디어를 얻어서 문제를 풀었다기보다는, 그림을 그려가며 규칙을 발견해서 이에 맞춘 느낌? 이 문제를 N별로 찬찬히 들여다보면 다음과 같은 규칙을 발견할 수 있음 빨>주>노>초 순으로 1>2>3>4 1. N=1일 때 또한 왼쪽 위 칸을 기준으로 인덱스는 2. N=2일 때 왼쪽 위 영역에서 0,0좌표의 숫자를 기준으로 한다. 3. N=3일..

트라이(Trie)란? 트라이는 문자열을 효율적으로 검색하기 위해 고안된 Search Tree의 일종입니다. 어떠한 알고리즘을 이용하여 정수나 실수 등과 같은 기본 자료형의 변수를 비교할 때에는 각 자료마다 동일한 시간이 걸릴 것이지만, 문자열의 경우 각각의 문자열마다 길이가 다르기 때문에 동일한 알고리즘으로 비교하더라도 같은 시간이 걸린다고 말할 수 없습니다. 최악의 경우 문자열의 길이만큼의 시간이 더 걸리게 될 것입니다. BST를 이용한 검색 (1) 정수 자료형의 경우 한 번의 검색마다 트리의 깊이가 1씩 깊어집니다. 트리의 깊이가 1씩 깊어질 때마다 비교해야 할 자료형은 절반씩 줄어들기 때문에 총 검색의 시간복잡도는 O(logN) 일 것입니다. (2) 문자열의 경우 한 번 검색마다 트리의 깊이가 1씩..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이를 활용하여 풀 수 있다. 트라이에 삽입할 때 비교해주면 쉽게 풀 수 있음 트라이에 삽입할 때 1. 삽입 중간에 end node를 만날 경우 예를 들어 911 91111 순으로 삽입한다고 하면 91111을 삽입할 때 91111에서 이전에 삽입한 911의 end node를 만날 것이다. 이 경우 일관성 없음: false를 return해준다. for (int i = 0; ..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 풀이는 간단하다. 과목들간의 관계를 방향 그래프로 생각, 정보는 인접 리스트에 담아준다. 과목 그래프의 방향은 그림의 반대방향으로 담아줘야지 나의 선수과목에 뭐가 있는지 쉽게 검색이 가능하다. 선수과목이 없는 경우: 1학기에 바로 수강이 가능 선수과목이 있는 경우 인접 리스트를 통해서 해당 과목의 선수과목들이 뭐가 있는지 판단하고, 선수과목 중 가장 큰 것의 학기에 +1 *시간복잡도 선수과목 정보를 입력받을 때 조건이 1≤A

1. 코드를 짠다! 예를 들어 tmp[i][0]가 tmp[i][1]이하인 경우에 두 값을 0으로 바꿔주는 메서드라고 하자 2. 출력을 찍어본다! 엥? 10일 때 0으로 안바뀐다!! 어디가 잘못된걸까? 3. 원하는 곳에 breakpoint를 찍는다 조건문이 이상한 것 같으니 여기에 찍어보자 breakpoint 잡는 법은 저 파란 부분에 더블클릭 하면 된다. 4. 보고싶은 변수는 어떤게 있는지 정한다 Window-Show View-Expressions 를 열어서 해당 탭을 열어준다. 그리고 원하는 변수를 적는다. 그 다음에 이 벌레 버튼을 눌러서 실행한다. 그러면 이렇게 breakpoint에 걸리면서 Expressions에 해당 변수값들이 나온다. 5. 진행 방법 상단에 있는 세 개의 화살표로 코드를 진행할..

https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 문제 자체는 그냥 BFS로 풀면 되는 문제이다. 다만 까다로운 조건이 두 가지 있음 1. 한 점이 아니라, 좌표 네 개짜리 네모로 BFS를 해야한다. > 처음에는 네 좌표를 int[4][2] 배열에 저장해서 비교할까 생각했었는데, 생각해보니 왼쪽 위와 오른쪽 아래, 대각선 좌표끼리만 비교를 하면 나머지 두 좌표는 비교할 필요가 없다. 그리고 가로 길이와 세로 길이가 주어지..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 그냥 스택을 응용하는 기본 문제일 뿐이지만, 아스키코드를 활용해서 코드를 간단하게 짤 수 있어서 적어봤다. import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..

https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 상세한 문제 설명은 링크 참조 손가락의 처음 위치는 */# 147(왼쪽)은 무조건 왼손 369(오른쪽)은 무조건 오른손 2580(가운데)는 가까운 손으로 친다. 0만 없었으면 다른 자료구조가 필요 없이 그냥 int변수만으로 끝낼 수 있을 것 같은데, *..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256MB 39897 11238 7356 25.687% 문제 백준 사이트를 참고해주세요 입력 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 ..