본문 바로가기

Algorithm

 (83)
[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..
다익스트라(Dijkstra) 알고리즘 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com 1. 출발 노드를 설정합니다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택합니다. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다. 5. 위 과정에서 3번 ~ 4번을 반복합니다. 최소 비용을 단순히 선형 탐색으로 찾도록 만들었습니다. 이렇게 작성하는 경우 다익스트라의 시간 복잡도가 O(N^2)으로 형성됩니다. 따라서 최대한 빠르게 작동시켜야 하는 경우 힙 구조를 활용하여 시간 복잡도 O(N * lo..
[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 ..
'틀렸습니다'를 받지 않기 위한 팁 https://www.secmem.org/blog/2021/02/19/wa/ '틀렸습니다'를 받지 않기 위한 팁 개요 이전 글들에서 시간 복잡도를 고려한 코드 설계 전략과 PS에서의 런타임 에러와 디버깅에 대해 각각 다루어 보았습니다. ‘시간 초과’와 ‘런타임 에러’는 모두 오답 판정 중 특수한 경 www.secmem.org
순열 알고리즘 (Permutation Algorithm) 사전순으로 출력되지 않는다는 점을 주의해야겠다. 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2 위와 같이 출력된다. 사전순으로 출력된다면 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 이어야 한다. #include #include #include using namespace std; /* 순열 알고리즘 */ void Permutation(vector& Array, int Start, int End) { if (Start == End) { for (const auto it : Array) { cout
endl과 \n, flsuh 풀이법은 맞는데 계속 시간 초과가 나서 뭔가 했는데 endl이 문제였다. endl은 flush를 겸하기 때문에 매우 매우 매우 매우 매우 느립니다. '\n'을 대신 사용하세요. 항상 flush를 해서 느린 c++ endl 1 버퍼의 내용을 모두 지운다. 2 버퍼의 내용을 모두 처리한다. (여기서 처리한다는 그냥 버리는게 아니다) stream에서 어딘가로 written을 한다. 그리고 내부적으로는 버퍼로 구현된. 이라는 게 눈에 들어옵니다. endl을 만난 경우에, '\n'을 추가하고, flush를 하는데요. 버퍼링 정책이 버퍼가 꽉 찼을 때 출력하는 정책이라 해도, endl을 넣으면 강제로 flush가 됩니다. 이게 얼마나 큰 차이냐. 라고 다시 되물으신다면, 위에서 strace 한 결과를 보여드렸으니,..
[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
지도에서 DFS, BFS DFS 지도에서 DFS는 한 가지 방법으로 갈 때까지 가보는 방식이라고 생각한다. - 백트랙킹 방식이라 생각하고 visit 표시를 해줘야 한다. 중복 방지를 위해서 체크하는 방법은 자주 활용되므로 잘 익혀둘 수 있도록 한다. 그리고 만약 n 의 크기가 10,000이상의 값이라면 어떻게 해결해야할지 고민해보기 바란다. 이 방법들은 모두 시간이 너무 많이 걸리기 때문에  값이 커질 경우 제한된 시간 이내에 해를 구할 수 없다. BFS BFS는 한 칸에 대한 데이터가 중요하고 그것을 저장하는 것이다. 최단거리 문제
[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); ..
완전탐색 - 2단계 문제집: 완전 탐색 (normal) (soo7652) www.acmicpc.net 1051 숫자 정사각형 37.506% 1057 토너먼트 55.774% 1198 삼각형으로 자르기 51.807% 1487 물건 팔기 29.775% 1639 행운의 티켓 50.498% 1895 필터 81.250% 2548 대표 자연수 49.509% 2615 오목 21.368% 2992 크면서 작은 수 47.778% 3024 마라톤 틱택토 32.280% 3182 한동이는 공부가 하기 싫어! 71.429% 4375 1 36.962% 9873 Cow Baseball 64.894% 9996 한국이 그리울 땐 서버에 접속하지 27.958% 10211 Maximum Subarray 42.152% 10974 모든 순열 60.007% 115..
완전탐색 - 1단계 문제집: 완전 탐색 (easy) (soo7652) www.acmicpc.net 4690 완전 세제곱 40.853% 9094 수학적 호기심 69.964% 20410 추첨상 사수 대작전! (Easy) 68.148% 1813 마지막 한마디 36.826% 2231 분해합 47.515% 2309 일곱 난쟁이 43.555% 2386 도비의 영어 공부 60.497% 2798 블랙잭 44.414% 2858 기숙사 바닥 55.560% 2966 찍기 50.483% 3040 백설 공주와 일곱 난쟁이 70.973% 10448 유레카 이론 59.016% 13410 거꾸로 구구단 59.473% 14697 방 배정하기 43.745% 19532 수학은 비대면강의입니다 47.391% 1145 적어도 대부분의 배수 58.621% 216..
Deque 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.
[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일때부터 끝인것이다.
복습1 문제 - 정답 참조 문제 - 스킵함 문제 - 풀었지만 미완성 입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953,11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 별찍기 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 28문제 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 2751, 11650, 11651, 10814..
DP 하면서 틀리는 것 / DFS하면서 틀리는 것 DP 하면서 틀리는 것 - 변수형 사이즈 - DP배열 초기화 - DP배열 시작 인덱스 DFS하면서 틀리는 것 - 아무것도 포함하지 않는 경우는 제외한다. - 종료 조건 - depth 종료 조건
[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..

티스토리툴바