꼼개의 개발자취

문제 : https://www.acmicpc.net/problem/2493 [ 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net ](https://www.acmicpc.net/problem/2493) 문제설명 단순 반복문을 사용한 구현문제로는 제약조건 때문에 시간초과가 날 수 있다. 1개의 for문을 사용하되 문제를 풀 수 있는 방법 하면 stack이 생각나야한다. 알고리즘 1. for문을 이용하여 앞에서 부터 스캔하며 stack에 값을 push한다. 2. 조건문안에 stack이 비었으면 자신보다 큰 탑이 없..

구현코드 문제 : https://www.acmicpc.net/problem/1966 [ 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net ](https://www.acmicpc.net/problem/1966) 문제설명 1. 제목 그대로 큐를 사용하면 된다. 자료구조을 이용하는 문제임을 쉽게 알 수 있다. 알고리즘 1. queue 와 중요도가 높은 문서를 알 수 있는 어떠한 가이드가 필요하다. 2. 가이드를 vector를 이용했다. vector를 정렬하여 높은 숫자가 빠지면 vector의 index도 증가하도록 하였..

문제 : https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제설명 1. 푸는 방법이 굉장히 많다. 어떤 방법으로 푸느냐에 따라 난이도가 달라지는 것 같다. 알고리즘 1. 먼저 가장 높은 위치를 구한 뒤 왼쪽과 오른쪽으로 나눠 생각한다. 2. 왼쪽부터 가장 높은 위치 인덱스 까지 반복문을 진행한다. 조건은 최대값인 tempValue 보다 현재위치의 높이가 크거나 같을 때 최대인덱스인 tempIdx부터 현재 위치까지 반복문을 진행..

문제 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제설명 괄호가 나오는 문제이다. 괄호가 나오는 문제는 왠만하면 스택을 사용하고, 여기서는 temp 변수가 핵심이다. 알고리즘 1. 열린 괄호가 나오면 stack에 push하고 괄호 모양에 따라 temp에 특정 값을 곱해준다. 분배 법칙이라 생각하면 이해하기 쉽다. 2. 닫힌 괄호가 나오면 바로전에 닫힌 괄호에 맞는 열린괄호가 있으면 result에 값을 더해주고 조건이 틀리면 break..

문제 : www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 문제설명 단순 구현 시뮬레이션 문제이다. 배열 회전하는 방법과 BFS를 사용하면 쉽게 풀 수 있다. 알고리즘 1. 배열을 스캔하며 나눠진 구역마다 회전해준다. 회전 방법은 코드에 주석처리 해놨다. 2. 회전 후 인접한 4방향을 탐색하고 조건을 실행한다. 3. 모든 명령을 마친 후 BFS을 통해 가장 큰 덩어리의 개수를 구한다. 주의사항 1. 구역을 나누고 회전하는 부분이 까다로웠는데..

문제 : www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제설명 단순 구현 시뮬레이션 문제이다. 알고리즘 1. 문제 설명에 나와있는 5x5의 흩날리는 비율을 각 토네이도 방향마다 적용시켜준다. 2. 4방향 모두 만들어준다. 3. 토네이도를 이동하며 방향에 맞는 배열을 적용시켜 계산한다. 주의사항 1. 구현 문제는 조건을 주의해야한다. 조건을 미리 종이나 메모장에 적어논 다음 코딩하는 것이 실수를 줄이는 방법같다. 2. 4방향..

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제설명 자료구조를 잘 활용하여 풀어야하는 시뮬레이션인다. N의 크기가 100이기 때문에 값이 0인 자리에서 출발하여 모든 경우의 수를 살펴봐도 O(N^2)이다. 아마 평균적으로는 장애물들이 있기 때문에 훨씬 더 빠를 것이다. 알고리즘 1. 0이 있는곳 즉 아무 장애물이 없는 구역을 queue에 넣는다. 2. 하나씩 poll 하며 4방향으로 조건에 맞게 탐색을 진행한다. 3. 웜홀 같은 경..

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN&categoryId=AV18KWf6ItECFAZN&categoryType=CODE4 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. 반복문을 이용하여 substr을 구하고 우선순위 큐에 넣는다. 2. 큐에서 주어진 index를 빼며 답을 구한다. 주의사항 1. 우선순위 큐에 substr을 담았기 때문에 중복제거는 반복문 1개로 가능하다. 2. 우선순위 큐를 이용하여 정렬할 때 문제에 주어진 조건을 잘 읽어봐야 한다. -> ..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 1. 이중 포문을 돌면서 8방향 지뢰의 개수를 찾는다. 2. 지뢰개수가 0인 좌표를 큐에 넣고 조건을 만족 하는 범위까지 퍼진다. 3. 안 퍼진 곳(0)과 퍼진곳의 시작 좌표(-1)을 count해준다. 주의사항 1. 구현 하는 방식은 다양하다. 알고리즘을 생각할 때 문제를 잘 읽어보고 문제대로 구..

문제 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG&categoryId=AWqU0zh6rssDFARG&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Treeset, list 등을 이용하여 푸는 방식은 많지만 우선 순위 큐가 가장 적합하다 생각했다. 알고리즘 1. 입력을 받으면서 우선 순위 큐에 넣는다. 이름은 객체로 받았다. -> ComparTo 함수를 만들어도 된다. 2. 객체 비교를 하는데 먼저 길이를 비교하였고, 길이가 같으면 반복문을 통해 사전 순으..