본문 바로가기

Algorithm/Implementation

 (746)
(C++) - 백준(BOJ) 17413번 : 단어 뒤집기 2 www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net stack이용한 구현문제였습니다. 풀이방법 3가지 경우에 단어가 stack에서 빠져나옵니다. 1. 현재 보는 문자가 ''인 경우 3. '공백' 또는 마지막 문자인 경우 1.의 경우 stack에 들어있는 문자들이 tag인 경우는 없으므로 (''가 번갈아 나오기 때문) 모두 뽑아 ans에 붙여줍니다. 2. ''포함 모두 뽑아내고 다시 뒤집어주어 원래 단어가 나오게 한 다음 ans변수..
(C++) - 백준(BOJ) 17406 : 배열 돌리기 4 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 순열 + 구현 문제였습니다. 풀이방법 1. 매 연산마다 범위를 계산해 s와 함께 넣어줍니다. x1 : r - s, y1 : c-s, x2 : r + s, y2 : c + s 로 계산한 후 그 점들과 s를 op라는 변수에 vector형태로 넣어줍니다. 2. dfs형태로 모든 형태의 연산 순열을 뽑아냅니다. 한 연산의 순열을 뽑아냈다면 뽑아낸 순열을 comb라는 vector 변수에 저..
(C++) - 백준(BOJ) 21609번 : 상어 중학교 www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net bfs와 정렬을 구현하는 문제였습닌다. 풀이방법 1. 블록 그룹 넓이, 무지개 블록 개수, 기준 블록의 행,열을 struct로 하는 자료구조인 groups vector변수를 선언해줍니다. 그 외 기본적인 입력을 받을 board 등을 선언해줍니다. 2. 조건에 만족하는 블록 그룹의 기준 블록을 찾아줍니다. 무지개 블록은 공유될 수 있기 때문에 check이후 check해제해야합니다. 기준 블록을 찾았으면 gro..
(C++) - 백준(BOJ) 21608번 : 상어 초등학교 www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현 문제였습니다. 풀이방법 1. x번 학생이 좋아하는 사람이 i,j자리에 앉아있으면 그 자리의 인접칸들중 비어있는 칸들마다 1씩 더해줍니다. 이런식으로 가중치를 부여하면 그 최대값과 같은 자리들을 possibleSeats vector변수에 넣어줍니다. 2. possibleSeats를 first, second 순으로 기준을 두어 오름차순으로 정렬합니다. 이들 좌표의 인접 칸에 대해 빈 칸들을 세주고 ..
(C++) - 프로그래머스(2021 Dev-Matching: 웹 백엔드 개발자(상반기)) : 행렬 테두리 회전하기 programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 구현문제였습니다. 풀이방법 돌릴 때 배열의 규칙을 찾아서 회전시키면 됩니다. 1. 먼저 x1,y1의 값은 x라는 변수에 저장합니다. 2. y1+1 ~ y2열까지 확인하면서 tmp를 선언해 arr[x1][i]값을 먼저 저장후 이전 x를 arr[x1][i]에 넣고 x를 tmp로 갱신해줍니다. 3. 같은 방식으로 우측 세로선, 하단 가로선, 좌측 세로선으로 확인하..
(C++) - 프로그래머스(2021 Dev-Matching: 웹 백엔드 개발자(상반기)) : 압축 programmers.co.kr/learn/courses/30/lessons/77484?language=cpp# 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 구현문제였습니다. 풀이방법 1. 0인 개수를 notMatch에 lottos와 win_nums가 같은 수의 개수를 match에 저장합니다. 2. 가장 잘되는 경우는 모든 0이 win_nums의 수인 경우입니다. 따라서 7 - (match + notMatch) 가 답입니다. 가장 안되는 경우는 모든 0이 wi..
(C++) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[3차]) : 압축 programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 구현 문제였습니다. 풀이방법 1. 사전에 등록되어있다면 현재 문자열을 string 변수 w 계속 붙여줍니다. 사전에 등록되어 있지 않다면 등록이 되었었던 가장 긴 문자열을 answer에 push해주고 piv를 현재 index로 갱신해줍니다. 그 후 w+msg[j]문자열은 등록이 안되어있으므로 map에 등록해줍니다. 그리고 break합니다. 2. piv부터 msg의 끝까지 잉여 문자열을 substr해..
(C++) - 백준(BOJ) 16935번 : 배열 돌리기 3 답 www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 무지성 구현으로 푼 문제였습니다. *3, 4 연산시 n*m이 m*n이 된다는 점 주의해야합니다. Code #include using namespace std; int n, m, r, arr[101][101]; void calculateOne(){ for(int i = 1; i

티스토리툴바