본문 바로가기

Algorithm/BOJ

 (23)
[BOJ] 2579 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 쓸데없는 조건문을 엄청 만들어서 하고 있었는데 그런 코드는 좋은 코드가 아니라는 걸 다시 한 번 배우고 간다. DP 배열의 조건을 확실히 이해하고 선언해 놓아야한다. #include #define MAX 300 using namespace std; int n, A[MAX+1],DP[MAX+1]; void input(){ cin >> n; for(int i =1 ; i > A[i]; } void solve(){ DP[1] =A[1]; DP[2] =A[1]+A[2]; for(i..
[BOJ] 1107 리모컨 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 충격과 공포의 문제이다. 엄청 더럽게 if문 많이 해서 풀었는데 전혀 그런식으로 푸는 문제가 아니었다. 브루트 포스로 처음부터 끝까지 하나하나 확인하면서 가는 문제이다. 반례↓ 글 읽기 - [반례모음] 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 1555 8 0 1 3 4 5 6 7 9 670 10 9 1 2 3 4 5 6 7 8 9 11 0 9 1 2 3 4 5 6 7 8 9 1 100000 9 0 1 2 3 4 5 6 7..
[BOJ] 2615 오목 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 반례↓ 글 읽기 - 누가 기침소리를 내었는가? 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 틀린 이유 6개 이상일 경우 → 이전 값까지 모두 확인해야 한다. 이전 값이 없을 때만 온전히 5개인지 검사할 수 있다. visit를 쓸 경우 관계 없는 경우의 새로운 케이스에 대해 검사하지 못한다. #include int a[19+2][19+2]; int main() { int i, j; for(i=1; i
[BOJ] 7573 고기잡이 7573번: 고기잡이 한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고 www.acmicpc.net 단순한 방법으로 하면 4중 중첩이 된다. 당연히 시간초과가 난다. 물고기를 기준으로 for문을 돌려야 한다. ▶그물의 크기를 정하고 (sx, sy) 위치를 탐색할 때, 모든 지점을 탐색하면 TLE 발생 위와 같이 (4, 3)에서 그물을 치는 것은 비효율 적입니다. ▶ 어디를 (sx, sy)로 설정하는 것이 좋을까요? 물고기가 존재하는 위치 & 물고기간의 교차점 ※ (2, 3)과 (4, 5)과 주어질 때 두 좌표의 교차점은 (4, 3)과 (2, 5) 입니다. #include ..
[BOJ] 17255 N으로 만들기 스스로 풀어낸 기쁜 문제이다. 방문 배열을 이차원으로 만들어서 layer마다 확인하도록 했다. BFS로도 풀어낼 수 있을 것 같다. 17255번: N으로 만들기 음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000) www.acmicpc.net #include #include #define MAX 8 using namespace std; string N; int cnt = 0, N_length; string visit = "00000000"; bool layer_visit[MAX+1][10]; void input(){ cin >> N; N_length = N.length(); } void solve(int len, string cur, string v ){ if( len == N_lengt..
[BOJ] 3933 라그랑주의 네 제곱수 정리 3933번: 라그랑주의 네 제곱수 정리 입력은 최대 255줄이다. 각 줄에는 215보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다. www.acmicpc.net 이 문제 전에 풀었던 문제와 거의 같은 문제인데 까맣게 잊고 있었다. 힘들게 이해하고 기억에서 지워버리다니... 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 심지어 성공한 문제;; brute force 백준 3933 라그랑주의 네 제곱수 정리 https://www..
[BOJ] 1058 친구 플로이드-와샬 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net
[BOJ] 1535 안녕 #include #define MAXL 20 #define MAXJ 100 using namespace std; int DP[MAXL+1][MAXJ+1], L[MAXL+1], J[MAXJ+1]; int N; void input() { cin >> N ; for (int i = 1; i > L[i]; for (int i = 1; i > J[i]; } void solve() { for (int i = 1; i = L[i]) DP[i][j] = max(DP[i - 1][j - L[i]] + J[i], DP[i - 1][j]); else DP[i][j] = DP[i - 1][j]; } } int res = 0; for (int i = 1; i < 100; i++) res = max(DP[N][i], res); ..
[BOJ] 1261 알고스팟 DFS에서 백트랙킹하는 부분을 잘 생각해야 되는데 매번 고려하지 않아서 생각이상의 시간이 걸린다. 4방향을 모두 확인하면서 간다면 한 방향을 확인하고 그 방향으로는 더 이상 가면 안된다. 따라서 4방향을 모두 확인한 후에 false로 바꿔줘야 한다. row, col으로 하는게 안헷갈린다. x,y로 했다가 완전히 뒤죽 박죽이 되어있었다. 시간 초과가 뜨는 풀이이긴 하지만 DFS백트랙킹 잘 알아둬야 겠다. #include #define MAX 100 using namespace std; int N, M, next_col, next_row, res = INT32_MAX; string MAP[MAX]; bool visit[MAX][MAX]; int d_row[4] = {-1, 0, 1, 0}; int d_col..
[BOJ] 1182 부분수열의 합 부분 수열 합이 S가 되었다고 해도 끝까지 확인을 해보면 또 다시 S가 나올 수 있다. 처음에 S가 0일 경우가 있을 수도 있다. 따라서 합을 레이어가 시작할 때 구한다. #include #define MAXN 20 using namespace std; int N, S, cnt =0 ; long long A[MAXN]; void input(){ cin >> N >> S; int i = 0; while(i > A[i++]; } void solve(long long sum , int index){ sum += A[index]; if(index >= N) return; if(sum == S ) cnt++; solve( sum -A[index], index+1); solve(sum, index..
[BOJ] 6603 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 각 depth마다 index값을 잘 살펴봐야한다. 종료 조건으로 인덱스 값이 넘어가면 끝내야한다. 처음 시작할 때의 index가 0이므로 7개의 배열이라면 인덱스가 8일때부터 끝인것이다.
[BOJ] 11057 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 수식은 모두 맞았지만 +=과 %의 연산 순서 차로 값이 달라진다. 애매하면 그냥 괄호로 다 쓰는게 확실하겠다. 연산자 우선 순위 다시 공부해라.
[BOJ] 2011 암호코드 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 한번 확인해보세요 1. 처음에 0~ 의입력을 정상적으로 받는지 ex) 0 -> 0 011 -> 0 0101 -> 0 등등 2. 중간에 0이 있을때 그앞 두자리를 고려하는지 ex) 1203 -> 1 인데 세번쩨 0을 고려하지않고 12를 먼저 고르고 그다음 0을 보고 불가능으로 0을 출력하진 않았는지 3. 26이하와 27이상을 잘 구분하였는지 ex) 2626 -> 4 2727 -> 1 원래 내가 하려던 방법으로 계속 진행해보려 했으나 2번 반례에서 실패.. 1203 DP[0] = A..
[BOJ] 1987 알파벳 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net string형으로 해보려했는데 잘 안풀린 문제다. c++에서 string형 다루는 방법을 잘 모르는 것을 많이 느꼈다. 비트마스킹 방법을 처음으로 직접 적용해본 문제이다. 백준 1987번 알파벳 문제 링크입니다: https://www.acmicpc.net/problem/1987 DFS(Depth First Search) 알고리즘과 백트래킹 기법을 요구하는 문제였기 때문에 visited 배열을 사용하지 않아도 되는 문제였습니다. 대신, 문제 조건에.. ja..
[BOJ] 2580 스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net DFS를 이용해서 스도쿠를 참신하게 풀어낸다. 나는 4방향으로 모두 이동하는 것을 생각했는데 그렇게 풀지 않고 81개의 칸을 차례로 돌면서 0인 값이 나온다면 1부터 9까지 수를 가능한 경우를 모두 넣어준다. 백준 2580번 스도쿠 문제 링크입니다: https://www.acmicpc.net/problem/2580 흥미로운 백트래킹 문제였습니다. 처음에 풀 때는 3*3 칸 내에서도 1~9가 하나씩 존재해야한다는 규칙을 잊어먹어서 틀렸습니다. 3*3 칸 내 인덱스..
[BOJ] 3108 로고 BFS 탐색을 통해 한 붓 그리기 를 수행하는 문제이다 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 1. 사이의 간격을 고려해야 풀 수 있다. [ 백준 3108 ] 로고 (C++) 백준의 로고(3108) 문제이다. [ 문제 바로가기 ] [ 문제풀이 ] 1) 처음에 접근하기가 굉장히 어려웠던 문제이다. 먼저 입력을 받는 것 부터 차근차근 알아보도록 하자. 입력으로는 사각형의 양 끝 yabmoons.tistory.com 2. DFS로 해야한다 생각했는데 BFS로도 풀 수 있는 문제였다. [BFS] 3108번 로고 3108..
[BOJ] 1525 퍼즐 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net #include #include #include #define TARGET "123456780" using namespace std; string Input; map visit; queue q; int d[4] = { -3, -1, 1, 3 }; void input(){ int i =0 ; string N; while( i++ > N; Input += N; } } bool possible(int cur, int d){ if( (cur % 3) == 0 && d == -1) return false; if( (cur % 3..
[BOJ] 2261 가장 가까운 두 점 이 문제 학부 때 알고리즘 시간에 들었던 문제이다. 들었지만 전혀 이해 안가는 문제였는데 이제서야 이게 분할정복이라는 것을 어렴풋이나마 이해했다. 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net BOJ 2261:: 가장 가까운 두 점 – 분할 정복 (Closest Pair Problem) – The Casterian http://acmicpc.net/problem/2261 모든 쌍 다 고려하기 점 두 개를 고르는 방법은 $\frac{n(n-1)}{2}$가지니까, 각각에 대해 모..
[BOJ] 9466 텀 프로젝트 cycle의 개수를 세야하는 문제였다. 이전에도 알고리즘 조교하면서 구현을 제대로 못했었는데 이번에도 어렵게 코드를 이해했다. 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이전에 확인한 cycle 관련코드도 지금 다시 보니 어질어질하다. frieden1946.tistory.com/334 #include #include //memset using namespace std; const int MAX = 100000 + 1; int N, cnt; int want[MAX]; bool visited[MAX]; bool ..
[BOJ] 2331 반복수열 DFS로 풀어야하는 문제였는데 처음에는 이게 어떻게 DFS가 되는지 고민해야 했다. 그래도 고민해서 BFS로 하면 되는구나 하고 알아내긴 했다. 수가 매우커진다고 생각했기 때문에 vector를 쓰려고 했는데 vector는 또 탐색을 어떻게 진행해야하는지가 문제였다. find함수를 사용하려했는데 내가 원하는 범위안에서만 값을 찾는 방법을 알아내지 못해서 for문으로 그냥 반복해서 값을 확인해주는 코드를 작성하였다. 다른사람이 작성한 코드를 보니 최대 값도 3만이 넘지 않는다고 측정하여서 범위를 한정시킬 수 있었다. 그걸 배열로 작성하여 주니 좀 더 간단하게 해결되었다. 내가 작성한 코드는 if문이 많아서 별로 좋은 코드는 아닌 것 같다. #include #include #include using names..
[BOJ] 2110 공유기 설치 가장 인접한 공유기의 최대거리를 이분탐색을 이용해서 구한다는 것까지는 알겠는데 이걸 공유기 C개만큼이 가능한지 확인하는 방법을 생각하기가 어려웠다. 해결책을 보니 첫번째 집에 무조건 공유기가 설치된다고 가정하고 계산을 한다. 이건 이해가 아직도 잘 안간다. ▶(수정) 거리가 d보다 무조건 같거나 커야하므로 첫번째 집이 아니라 그 다음집부터 시작을 한다면 공유기가 있는 집들간의 거리는 당연히 줄어들 것이다. 그러니까 처음집부터 해야 거리가 좀 더 큰 영역을 확인을 할 가능성을 높일 수 있다. 마지막 줄의 답이 x이상일 수 있는가?에 대한 내용을 구현하는 것이 어려웠습니다. ​ 정리를 하자면 이렇습니다. 먼저 우린 문제에서 주어진 가장 인접한 공유기 간의 최대거리를 구해야합니다. ​ 즉, 공유기를 어디 어디..
[BOJ] 1707 이분 그래프 이분 그래프를 먼저 알고 이해하고 있어야 풀 수 있는 문제였다. bfs로만 풀어봤는데 우선 이분그래프를 다시 설명해보자면 서로 연결된 그래프가 있으면 그걸 두 집합으로 나누려고 한다. 이걸 색깔로 구분하는 것이다. 자신이랑 연결된 노드들은 다른 색으로 칠한다. 그게 불가능하다면 이분 그래프가 되지 못한다. 자신과 연결된 노드가 같은 집합에 속하는 것이 되기때문이다. 테스트케이스 11 3 1 2 3 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 3 2 2 1 3 2 4 4 2 1 3 2 4 3 4 1 5 2 1 5 1 2 5 2 1 2 2 5 4 3 1 2 4 3 2 3 4 4 2 3 1 4 3 4 1 2 3 3 1 2 2 3 3 1 2 1 1 2 예제 출력1 YES YES NO YES YES ..
[BOJ] 2422 별 찍기 - 5 이걸 이렇게 오래 붙잡고 있을 줄이야..... c언어에서 정말 구멍이 많음을 느낀다. for문으로 하는 단순한 방법 말고 이전에 교재에서 공부했던 재귀 방식으로 코드를 짜려고 하는데 계속해서 오류가 나서 도대체 뭔가 했다. 우선 string형이 c언어에는 없어서 직관적이지가 않았다. 자바로만 워낙에 쉽게쉽게 해버렸으니 str관련 함수를 많이 알아냈다. 그리고 무엇보다 중요한 건 복사를 해줘도 기존에 값은 그대로 저장되고 그 앞에 짧은 값만 복사가 돼서 값의 길이가 계속 그대로였다. str형은 마지막에 무조건 \0을 붙여줘야 문장이 끝나는 걸 알아야 한다. str관련 함수는 이번 기회에 잘 알아갔으면 좋겠다. 그리고 c++에서는 굳이 이렇게 하지 않아도 String형이 존재한다는 것을 코드를 다 짠다음에 ..

티스토리툴바