본문 바로가기

Algorithm/Implementation

 (751)
(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
(C++) - 백준(BOJ) 14719번 : 빗물 답 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 왼쪽에서 오른쪽으로 보면서 현재 높이가 이전 높이보다 낮다면 여태까지 가장 큰 높이의 블록높이 - 현재 블록의 높이 즉, 가로에서 i번째 위치에서 고이는 빗물의 높이 값을 d[i][0]에 저장합니다. 만약 높다면 가장 높은 높이의 값을 갱신해줍니다. 2. 오른쪽에서 왼쪽으로 보면서 같은 방식을 적용합니다. 3. 다시 처음부터 끝까지 보면서 고인 빗물의 최소값을..
(C++) - 백준(BOJ) 1722번 : 순열의 순서 www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지 www.acmicpc.net 구현문제였습니다. 풀이방법 예제에서 n = 4 소문제 번호가 1인 경우를 예시로 설명하겠습니다. 나올 수 있는 모든 순열의 경우 수는 4!이므로 24개입니다. 24개 중 천의 자리 1로 시작하는 순열들을 1 ~3! 번째 순열 사이에 있습니다. 천의 자리 2는 3! + 1 ~ 3! + 3! + 1! 천의 자리 3은 3! + 3! +1 ~ 3! + 3! + 3! +1 천의 자리 4는 3! + 3..
(C++) - 백준(BOJ) 17135번 : 캐슬 디펜스 www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 적이 상태를 board배열에 입력받습니다. 2. mC3으로 궁수의 배치를 구합니다. 3. 게임을 진행합니다. 3-1. 매 궁수마다 각 적이 얼마나 떨어졌는지 거리를 구해줍니다. 그 후 가장 가깝고 왼쪽에 있는 적을 죽일 것임을 check해줍니다. *가장 왼쪽에 있는 궁수가 가까운 적을 먼저 죽이고 0으로 만들어 버린다면 틀립니다. 이유는 두 궁수로부터 가장 왼쪽에 있는 적의 거리가 같은 ..

티스토리툴바