일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- dynamic programming
- 동적 계획법
- 잠실
- 백트래킹
- BOJ
- PS
- 시뮬레이션
- 백준
- dfs
- 브루트포스
- 소수
- 삼성 기출
- 그리디
- 해커랭크
- 맛집
- 에라토스테네스의 체
- 완전탐색
- koitp
- DP
- sw expert academy
- Algorithm
- 구현
- BFS
- C++
- hackerrank
- 다이나믹 프로그래밍
- 알고리즘
- 스택
- 삼성 SDS 대학생 알고리즘 특강
- SWEA
- Today
- Total
목록BOJ (65)
펭로그
문제링크 : https://noj.am/1107 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include using namespace std; bool unabledNum[10]; // 사용 불가능한 숫자라면 -1을 반환 // 사용 가능할 경우 자릿수를 반환 int isUnableNum(int input){ int curDigit; int numOfDigits = 0; do { curDigit = input % 10; if(unabledNum[cur..
문제링크 : https://noj.am/1986 간단하면서도 지저분한 시뮬레이션 문제로 보인다.최대한 깔끔하게 하기 위해서 define을 사용하여 직관성을 높였으며 queen과 knight의 이동시 조건을 고려하여 별도의 함수로 구성하였다. 문제를 풀이할 때 주의할 점은 Queen 말이 이동할 때 장애물에 가로막혀있으면 이동 못한다는 점이다.풀이시에 안전하지 않는 영역은 'X'로 만들어 두었고 장애물 체크는 board[x][y] == 0 (빈공간) 상태일때만 체크했었는데 올바른 답이 나오지 않는 실수를 풀이 과정에서 겪었다.5번째 줄에서 적어놓은 것처럼 Q, K, P가 아닐 경우라고 명시해주니 쉽게 풀 수 있었다. 12345678910111213141516171819202122232425262728293..
문제링크 : https://noj.am/11047 최소의 동전 갯수로 주어진 금액을 때려맞추는 그리디한 문제이다.주어진 동전도 이미 정렬되어있기 때문에 솔루션도 매우 간단하다.큰 동전부터 차례대로 나누어서 값을 누적시키고 나머지 값들은 더 작은 단위의 동전으로 나눠서 또 누적시키면 쉽게 구할 수 있다.혹시라도 중간에 모든 동전을 소진했을 경우 바로 탈출하기 위해 24번째 줄과 같이 total == 0일 경우 탈출하는 조건을 두었다. 123456789101112131415161718192021222324252627282930// BOJ_11047 동전 0#include using namespace std; int coins[11]; int main() { ios::sync_with_stdio(false);..
문제링크 : https://noj.am/2217 각 로프에는 동일한 하중이 걸려야 한다는 점이 이 문제의 핵심이다.이때, 각각의 로프에 걸리는 하중은 병렬로 연결되어 있는 어떤 로프의 최대 중량을 초과할 수는 없다.그렇기 때문에 현재 병렬로 연결되어있는 로프 중에서 가장 적은 수치의 최대 중량이 각 로프들에 걸릴 수 있는 최대 하중이 되는 것이다.따라서, 임의로 뽑은 로프들 중에서 가장 값이 작은 것을 뽑은 로프의 갯수 만큼 곱하면 답을 구할 수 있다. 각 로프의 최대 하중을 담은 배열을 내림차순으로 정렬하여 최대 하중 값이 큰 것부터 차례대로 계산을 해주고 그 중에서 최대치만을 답으로 출력하면 된다. 예를 들자면, [110, 70, 20, 5, 35, 40]의 배열이 있다면 이를 내림차순 정렬하여 [1..
문제링크 : https://noj.am/1475 문자열을 입력 받아서 갯수를 카운팅 하고 그 중에서 가장 많이 카운팅 된 숫자가 몇개인 지를 구하는 문제이다.단, 문제의 조건에서 6과 9는 뒤집어서 사용할 수도 있다고 했기 때문에 0.5씩 카운팅하여 쉽게 해결하였다.이러한 과정을 위해서 float형을 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243// BOJ_1475 방 번호#include #include using namespace std; int max(int a, int b){ return a > b ? a : b;} int round(float input){ float temp = (int)in..
문제링크 : https://noj.am/1018 브루트포스 문제로 4중 for문이라는 더러운 코드로 문제를 풀게 되었다..... 체스판의 격자를 다음과 같은 2가지의 임의의 규칙을 정할 수 있다.1-1. 홀수번째 줄의 홀수 칸이 'W'1-2. 홀수번째 줄의 짝수 칸이 'B'1-3. 짝수번째 줄의 짝수 칸이 'W'1-4. 짝수번째 줄의 짝수 칸이 'B'or2-1. 홀수번째 줄의 홀수 칸이 'B'2-2. 홀수번째 줄의 짝수 칸이 'W'2-3. 짝수번째 줄의 짝수 칸이'B'2-4. 짝수번째 줄의 짝수 칸이'W' 위와 같은 조건에 해당이 되지 않는 칸이라면 전부 카운트를 시켜서 값을 누적시키면 다시 칠해야하는 칸이 몇칸인지 구할 수 있다.하지만 2가지의 case를 모두 비교할 필요 없이 1의 case를 골라서 ..
문제링크 : https://noj.am/5566 주사위의 지시사항 대로 구현하면 쉽게 풀리는 단순 시뮬레이션 문제이다.1. 현재 위치에서 주사위를 던져 해당 눈금만큼 진행한다.2. 보드의 범위를 초과 했는지 체크한다.3. 초과하지 않았으면 진행된 자리에 있는 지시사항을 수행한다.4. 보드의 범위를 초과 했는지 체크한다. 1234567891011121314151617181920212223242526272829303132333435363738394041// BOJ_5566 주사위 게임#include using namespace std; int direction[1001];int dice[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout..
문제링크 : https://noj.am/1120 단순하게 두 문자열을 같은 길이 만큼만 비교하여 일치하지 않는 만큼의 문자가 몇개인지를 체크하여 최소값을 구하는 브루트포스 알고리즘적 방법으로 접근하였다. 1. A의 앞에 아무 알파벳이나 추가한다. 2. A의 뒤에 아무 알파벳이나 추가한다.이 두 조건을 최소값이 나오게 하려면 추가할 아무 알파벳을 B와 같게 만들면 되기 때문에 신경 안써도 되는 조건이다. 12345678910111213141516171819202122232425262728293031323334// BOJ_1120 문자열#include #include using namespace std; int min(int a, int b) { return a > b ? b : a;} int main() ..
문제링크 : https://noj.am/1057 문제의 조건에서 지민과 한수가 둘이 만나기 전까지는 무조건 이긴다고 하였다.따라서 문제에서 나온 조건대로 하면 '만약 서로 대결하지 않을 때는 -1을 출력한다.'은 절대로 나올 수 없기 때문에 무시해도 된다. 두 사람이 만날 수 있는 조건은 A와 B가 각각 2n-1과 2n 이어야 하는 조건이다.계산을 편하게 하기 위해서 그냥 A, B를 작은 순서대로 정렬하고 A가 홀수이고 A-B의 차가 1이면 정답으로 출력하도록 했다. 두 사람이 각 라운드에서 만나지 못한다면 div( ) 함수를 통하여 입력값을 절반으로 나누어주면서 정답을 찾아가면 된다.절반씩 계속 나누기 때문에 최악의 경우에도 O(logN)의 시간복잡도를 보일 것이다. 1234567891011121314..
문제링크 : https://noj.am/14500 1. 모든 경우의 수를 시뮬레이션하여 풀기테트로미노가 나올 수 있는 모든 상황을 시뮬레이션해서 문제를 푸는 방법이다.문제에서 조건을 살펴보면N*M은 최대 500*500 = 250,000테트로미노가 나올 수 있는 모양의 가지 수 = 19가지 250,000 * 19 = 4,750,000번 이므로 1억번을 초과하지 않는다.무식하게 한 좌표를 기준으로 19번의 테트로미노의 상태 모두를 탐색하는 방법으로 푸는게 시간복잡도 면에서는 가장 효율적이다. 다만, 이 방법으로 풀 경우 모든 경우, 숫자를 한개라도 틀리게 적었을 경우 실수하기가 매우 쉽다. 123456789101112131415161718192021222324252627282930313233343536373..