본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

c++

Algorithm/BOJ 2022. 3. 15. [BOJ] 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!(20153) [백준(BOJ)] 20153_영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해! C++ 문제 : BOJ_20153번 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해! 문제 설명 우선 n 개의 자연수가 주어집니다. 이 n 개의 수를 모두 이진수로 바꾸고 각 자리의 1의 개수를 조회합니다. 각 자리수의 1의 개수가 홀수이면 최종 결괏값에 (2^자리수)를 더해주고, 짝수이면 더하지 않습니다. 이때 최종 결괏값이 최대가 될 수 있도록 n 개의 자연수 중 최대 하나의 자연수를 제외할 수 있습니다. 마지막으로 결괏값을 띄어쓰기 없이 두 번 출력하면 정답입니다. Solution 완전 탐색, 수학 주어질 수 있는 수의 최고값이 2222222이므로, 그에 맞게 2222222의 숫..

Algorithm/AOJ 2022. 3. 14. [AOJ] BOARDCOVER [ALGOSPOT Online Judge(AOJ)] BOARDCOVER C++ 문제 : AOJ BOARDCOVER 문제 설명 테스트 케이스마다 H*W 크기의 게임판이 주어집니다. 게임판의 각 자라니는 검은 칸이나 흰 칸으로 되어있는데, L자 모양의 블록으로 흰 칸이 안 남도록 채워야 합니다. L자 모양의 블록을 자유롭게 회전할 수 있지만, 블록끼리 겹치거나 검은 칸을 덮으면 안 됩니다. 이때 L자 모양의 블록으로 모든 흰 칸을 채울 수 있는 경우의 수를 구하는 문제입니다. Solution 완전 탐색 게임판의 가장 위쪽, 왼쪽의 판부터 시작해서 오른쪽, 아래쪽으로 내려가며 완전 탐색으로 해결해야 합니다. 게임판의 한 칸을 기준 삼아 순회하면서 L자 모양의 블록이 그 칸을 기준으로 회전할 수 있는 네 가지 ..

Algorithm/AOJ 2022. 3. 14. [AOJ] PICNIC [ALGOSPOT Online Judge(AOJ)] PICNIC C++ 문제 : AOJ PICNIC 문제 설명 n 명의 학생이 주어지고, m 개의 가능한 짝의 수가 주어집니다. m 개로 주어진 조건에 맞게 짝을 지을 수 있는 모든 경우의 수를 구하는 문제입니다. 가능하다고 주어지지 않은 학생들 끼린 짝이 될 수 없고, 모든 학생들은 각자의 짝이 있어야 합니다. Solution 완전 탐색 학생의 수가 최대 10명으로 완전 탐색으로 모든 경우의 수를 확인하여 풀 수 있습니다. 최악의 경우 최대 학생 수 10명이 자신을 제외한 9명과 모두 짝이 될 수 있는 경우인데, 이 경우는 9*7*5*3*1이므로 시간제한 안에 해결할 수 있습니다. 해당 학생이 짝을 찾았는지의 유무인 isFind 배열을 만들어 이 배열로 ..

Algorithm/BOJ 2022. 3. 14. [BOJ] 소문난 칠공주(1941) [백준(BOJ)] 1941_소문난 칠공주 C++ 문제 : BOJ_1941번 소문난 칠공주 문제 설명 5 * 5의 map이 주어지고, 각 자리는 'Y' 혹은 'S'로 표현되어 있습니다. 위, 아래, 좌, 우에 서로 인접한 7개의 자리에서 'S' 가 최소 4개 이상 있는 7 자리의 수를 찾는 문제입니다. Solution 완전 탐색, bfs 각 자리에 대한 정보를 벡터에 저장해 줍니다. 저장할 정보는 각 자리의 위치, 'S'인지의 여부입니다. 저장된 상태에서 7개의 자리를 check 해주고 이 7개의 자리에서 'S'가 4개 이상인 경우 bfs를 돌려줍니다. bfs에서 다음을 확인하며 순회해 줍니다. 주어진 크기 안에 있는 map의 자리인지 좌, 우, 상, 하로 인접돼있는지 앞선 완전 탐색에서 check 되어 ..

Algorithm/이론 2022. 3. 14. [알고리즘] lower_bound, upper_bound lower_bound, upper_bound lower_bound, upper_bound를 int 타입과 pair에서도 사용해봅시다. algorithm 헤더 lower_bound, upper_bound를 사용하기 위해선 algorithm 라이브러리가 필요합니다. #include 선언 lower_bound(시작 이터레이터, 끝 이터레이터, 지정 값) upper_bound(시작 이터레이터, 끝 이터레이터, 지정 값) 리턴 값 vector에서 lower_bound, upper_bound를 사용할 때의 리 값을 알아봅시다. lower_bound lower_bound는 vector의 시작 이터레이터와 끝 이터레이터 사이에서 지정한 값 이상을 가지는 최초의 이터레이터를 반환합니다. upper_bound upper_..

Algorithm/BOJ 2022. 3. 14. [BOJ] 사이클 게임(20040) [백준(BOJ)] 20040_사이클 게임 C++ 문제 : BOJ_20040번 사이클 게임 문제 설명 n 개의 노드가 주어지고, m 개의 양방향 선이 주어졌을 때, 최초로 사이클이 완성되는 m 번 째를 출력하는 문제입니다. 모든 m을 순회해도 사이클이 생기지 않았다면, 0을 출력해야 합니다. Solution 유니온 파인드 n이 최대 500,000이므로 O(n) 만에 답을 출력해야 합니다. 유니온 파인드를 사용해야 합니다. 이어지는 두 점을 merge 하면서 진행합니다. merge 하기 전에 주어진 두 점이 같은 조상이라면, 같은 조상을 갖고 있는 노드끼리 이어지므로 사이클이 됩니다. 이때의 m을 출력해 줘야 합니다. Description vector를 이용해 n과 m에 값에 맞는 배열을 동적할당했습니다. ..

Algorithm/BOJ 2022. 3. 13. [BOJ] 하노이 탑 이동 순서(11729) [백준(BOJ)] 11729_하노이 탑 이동 순서 C++ 문제 : BOJ_11729번 하노이 탑 이동 순서 문제 설명 재귀 재귀 문제로 유명한 하노이 탑 문제입니다. n을 입력받으면 세 개의 장대 중 첫 번째 장대에 n 개의 탑이 쌓이는 것으로 시작합니다. n 개의 탑은 가장 위에 있는 원판이 가장 가볍고 아래로 갈수록 무거운 원판이며, 가벼운 원판 위에 무거운 원판이 올라갈 수 없습니다. 각 장대 중 가장 위에 있는 원판을 하나 옮기는 것을 1회로 할 때, 최초에 첫 번째 장대에 있었던 원판을 모두 세 번째 원판으로 옮기는 최소 이동 회수를 구하는 것이 문제입니다. Solution 현재 장대의 위치를 st, 이동해야 하는 장대의 위치를 ed, 나머지 장대를 mid라고 합시다. 처음에 n을 3이라고 입력..

Algorithm/BOJ 2022. 3. 13. [BOJ] 가장 긴 바이토닉 부분 수열(11054) [백준(BOJ)] 가장 긴 바이토닉 부분 수열(11054) C++ 문제 : BOJ_11054번 가장 긴 바이토닉 부분 수열 문제 설명 DP 기존의 증가하는 수열, 감소하는 수열이 합쳐진 문제입니다. 수열이 증가하다가 감소가 되는 경우, 수열이 계속 증가하는 경우, 수열이 계속 감소하는 경우가 모두 바이 토닉 부분 수열입니다. 수열이 감소하다가 증가하는 경우는 해당되지 않습니다. DP를 활용해 해결할 수 있었습니다. Solution 앞서 언급한 세 가지 경우로 나누어서 DP 배열에 갱신해 주어야 합니다. 수열이 계속 증가하는 경우 -> dp[0][현재 인덱스] 수열이 증가하다가 감소가 되는 경우 -> dp[1][현재 인덱스] 수열이 계속 감소하는 경우 -> dp[2][현재 인덱스] 로 만들어 값을 계속 비..

이전 1 2 3 4 ··· 7 다음

티스토리툴바