본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[기출 상] 단어 게임 [문제] 영희와 철수는 단어게임을 하고 있다. 영희가 첫글자를 말하면, 철수는 그 글자로 시작하는 단어를 얘기해야 한다. 단, 단어는 미리 주어진 단어목록에서 선택해야 하며, 동일한 첫글자를 가진 단어가 여러개 있다면, 각 단어는 최소 횟수로 말한 것이여야 한다. 횟수가 똑같다면 알파벳 순으로 결정한다. [코드] // 실제 시험에서는 Solution 클래스의 solution 함수를 사용합니다. 이를 감안하여 풀이해주세요. #include #include using namespace std; void solution(int k, int n, vector word, vector first_word){ //각 단어는 최소 횟수로. 같은 횟수면 알파벳 순으로. sort(word.begin(), word.end(..
[기출 상] 백준 14891 톱니바퀴 [문제] https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net [풀이] 양방향으로 데이터 입출력이 가능한 deque에 방향을 저장해 회전하도록 한다. [코드] #include #include #include using namespace std; deque wheel[4]; void turn_wheel(int num, int dir) { //id톱니 dir방향으로 움직이기 if (dir == -1) //반시계방향 { wheel[num].push_b..
[기출 상] 주울 수 있는 최대의 돈2(정수삼각형) [문제] 주울 수 있는 최대의 돈 문제와 같은 조건이되, 삼각형으로 돈이 위치한 경우이다. 아래층으로 내려갈 때는 바로 아래 또는 오른쪽 대각선 아래로만 이동 가능하다. 예를 들어, 1 5 2 2 3 4 5 4 9 2 4 7 1 7 3 으로 돈이 놓여있다면 최대값은 25이다. [풀이] 동적프로그래밍을 이용하여 풀면된다. 고려해야 할 경우는 3가지인데, 아래로만 이동하는 경우, 오른쪽 대각선으로만 이동하는 경우, 그 중간 부분이 있다. 아래로만 이동하는 경우 money[i][j] = money[i][j] + money[i-1][j]. 오른쪽 대각선으로만 이동하는 경우 money[i][j] = money[i][j] + money[i-1][j-1]. 가운데 부분의 경우 money[i][j] = money[i]..
[기출 상] 백준 19538 루머 [문제] https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net [풀이] bfs를 이용하는 문제이다. 이전에 풀었던 토마토 문제와 비슷해서 bfs를 이용해야겠구나!라는 생각은 들었는데,,, 이 문제의 관점은 주변인들의 절반 이상이 루머를 믿을 때(감염되었을 때) 본인도 루머를 믿는다는 것이다. 먼저 bfs를 이용하므로 최초유포자인 사람들의 index를 큐에 넣고 그들의 시간을 0분으로 저장해준다. 큐에서 나온 유..
[기출 상] 프로그래머스 불량 사용자 [문제] https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr [풀이] 먼저 dfs를 이용하여 풀 수 있다. 이미 방문했거나 길이가 다른 경우를 패스하고, user_id[i]의 문자를 하나씩 비교해줘 user_id와 banned_id가 *부분을 제외하고 전부 일치하면 visited[]배열에 true를 저장, 방문 표시를 해준다. 이후 비교해야 할 banned_id index인 bsize를 하나 증가시켜 dfs를 호..
[기출 중] Palindrome 만드는 횟수 구하기 [문제] Palindrome(회문)은 앞으로 읽으나 뒤로 읽으나 똑같은 배열을 의미한다. 예를 들어, 123321과 같은 배열은 회문이다. 회문이 아닌 배열은 인접한 요소들끼리 합쳐서 회문을 만들려고 한다. 예를 들어, 12351은 회문이 아니지만, 2+3의 한번의 수정을 통해 1551인 회문을 만들 수 있다. 이렇게, 회문이 아닌 배열이 주어졌을 때 회문을 만들 수 있는 가장 적은 수정 횟수를 구하도록 해라. [풀이] 맨 앞과 맨 뒤부터 시작해 비교해 나가면서 대칭이면 통과하고, 대칭이 아니면 더 작은 숫자인 쪽을 합쳐서(횟수 증가) 대칭인지를 다시 비교해 본다. [코드] #include #include using namespace std; int answer = 0; int solution(int* ..
[기출 중] 도서관 좌석 예약 [문제] 2개의 좌석에 대해서, 학생들의 희망 시작 시간과 희망 종료 시간이 저장된 배열이 주어질 때, 최대로 예약할 수 있는 학생의 수를 구하는 문제이다. 좌석의 우선순위는 동일하며, 한 좌석에 한 명만 앉을 수 있고, 희망 시작 시간과 종료시간이 같아도 문제없이 교대 가능하다. [풀이] 그리디 알고리즘으로 풀 수 있다. 먼저 최대한 많은 학생을 배정하기 위해서는 희망 종료 시간이 짧은 순서대로 배정해주어야 하므로 정렬을 해준다. 다음 사람의 희망 시작 시간이 현재 좌석에 앉아있는 사람의 희망 종료 시간과 같거나 더 커야 교대가 가능하다. 먼저 1번 좌석이 이용 가능한지 확인해주고, 그 다음 2번 좌석이 이용 가능한지 확인한다. 이 때, 코드 상 항상 1번 좌석을 먼저 확인해주는데, 사실상 두 좌석의 ..
[기출 중] 백준 7576 토마토 [문제] https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [풀이] BFS를 이용해서 푸는 문제이다. 익은 토마토(box[i][j]==1)는 큐에 row, col 좌표를 넣어준다. 큐가 빌 때 까지, 큐를 pop하고 반복문을 돌려 pop한 row, col 행의 상, 하, 좌, 우를 검토한다. 범위 내에 존재하고, 익지 않은 토마토가 들어있으면 box 값을 원래 값+1로 갱신해준다. 이는 모든 토마토가 익을 때까지 걸리는 최소 일수..

티스토리툴바