성장하는 코딩블로그

백준(C++) 시간초과 해결법 백준 알고리즘 문제를 풀다 보면 제출 시 시간초과가 뜨는 경우가 있다. 이 경우 코드 몇 개만 추가하거나 수정하거나 해서 시간초과를 해결할 수 있다. 아니면 문제 해결에 사용한 알고리즘의 시간복잡도를 고려해 볼 수도 있다. 오늘 시간초과 원인과 해결법에 대해서 알아보자. 1. ios::sync_with_stdio(false) 추가 C++에서 입력은 크게 printf와 cout 출력은 scanf와 cin이 있다. 여기서 cout와 cin은 printf, scanf에 비해 속도가 느리다. 그 이유는 cout와 cin는 실행 시 값의 자료형을 검사하기 때문이다. 속도가 좀 더 느리나 안정적이다. ios::sync_with_stdio(false); ios::sync_with_std..

C++ STL pair 클래스 총정리(vector, sort) C++ STL 중 라이브러리에 pair클래스가 있다. 오늘은 이 pair클래스에 대하여 알아보겠다. 추가로 알고리즘 문제를 풀 때 어떻게 응용되는지도 보자. pair를 사용하면 자료 두 개를 한 가지 자료에 저장할 수 있다. pair는 2차원 좌표 저장등 많은 곳에서 유용하게 쓰이므로 꼭 익혀두자. 일단 라이브러리에 있으니 추가해 준다. 이제 사용해 보자 생성 pair p; type1, type2 두 개의 데이터를 저장하는 pair p를 만든다. 예를 들어 좌표를 저장하려면 y좌표, x좌표 두 개를 저장할 int형 공간이 필요하므로 pair p;와 같이 선언해 주면 된다. int형뿐만 아니라 string, char, float 등을 자유롭게 ..

C++ STL sort() 총정리 오늘은 C++ STL의 헤더가 속한 sort() 함수에 대해 정리해 보겠습니다. 2차원배열에서의 정렬, 오름차순, 내림차순등에 대하여 설명하겠습니다. sort() 함수는 정렬을 해주는 함수로 간편하고 빠르기에 매우 많이 사용되며 단순 정렬문제부터 그리디 알고리즘등 광범위하게 활용되기 때문에 필히 익혀야 합니다. 일단 라이브러리를 추가합니다. 이제 사용을 해봅시다. 사용 sort( 시작 주소, 마지막 주소+1, 정렬기준(생략가능) ) 위처럼 사용하면 됩니다. 정렬기준은 생략 가능하며 기본값은 오름차순입니다. 정렬기준은 조금 있다가 아래에서 다루겠습니다. 예를 들어 int a[10]을 오름차순으로 정렬할 경우 sort(a,a+10) sort(&a[0], &a[10]) 이 두..

백준 플레티넘 5를 달성하였다! 사실 플레 5는 찍은 지 꽤 됐는데 이제 자랑한다. 골드 5까지는 빨리 찍었는데 플레 5는 1년이 더 걸렸다. 골드 2? 까지는 가파르고 빠르게 올렸었는데 그쯤부터 레이팅 오르는 속도가 많이 느려졌었다. 실버문제를 풀어도 점수를 짜게 줘서 골드를 풀자니 그 당시 한 문제 푸는데 시간이 오래 걸리고..... 대충 클래스5를 따고 상위 100문제 평균을 골드 4 정도 맞추면 플레를 찍는 거 같다. 나는 상위 100문제를 골드 5 이상으로 채웠다. 실버가 안 보여서 간지가 나긴 한다. 그런데 이제 레이팅을 올리려면 골드 4 이상의 문제를 풀어야 하기 때문에 점수 올리기가 매우 힘들다. 골드 상위 문제들은 푸는데 시간이 오래 걸리고 플레이상의 문제들은 슬슬 벽이 느껴지기 시작했다..

필자는 2023년 2분기 네트워크관리사 2급에 합격하였다. 네트워크관리사는 한국정보통신자격협회에서 주관하는 국가공인민간자격증으로 네트워크 구축, 서버 구축, 인터넷 관련 내용을 평가한다. 필기, 실기 둘 다 60점이 커트라인이며 일 년에 4번의 시험을 치른다. 1급과 2급이 있는데 1급은 국가공인이 아닌 민간자격으로 대부분 2급을 응시하게 된다. 일단 응시료가 비싸다. 필기 43000원, 실기 78000원. 그래서 한 번에 합격하기를 간절히 바랐다. 일단 나는 '이기적 네트워크관리사 1ㆍ2급 필기+실기'책과 유튜브 무료 강의를 이용하여 공부하였다. 책에 있는 내용들을 암기하고 기출을 풀어보는 식으로 공부했는데 이렇게 안 하고 그냥 기출만 봐도 충분히 합격할 수 있을 것 같다. 기출에서 약간 변형해서 문제..

문제 링크 : https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 ..

문제 링크 : 9655번: 돌 게임 (acmicpc.net) 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 해설 구하는 방법은 크게 두가지가 있습니다. 1. 직접..

문제 링크 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인..

문제 링크 : https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 해설 N!이면 1×2×3×4.....N-1×N 인데 이 결괏값에서 뒤에 0이 몇 개나 나오는지 구해야 한다. 예를 들어 5!이면 1×2×3×4×5=120으로 답은 1이고 10! 은 3628800으로 답은 2이다. 일단 가장 쉽게 생각해 볼 수 있는 것은 10을 곱할 ..

문제 링크 : 1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사..