본문 바로가기

코딩테스트공부8

[백준] 1518번 또 슬금 들어와서 문제 하나 끄적이고 가기 코딩테스트가 코앞인데 졸업 작품도 준비중이라 정신이 없다.🥺 그치만 또 바쁜게 좋은 ESTJ는 그냥 이 상황을 즐기기로... 오늘은 간단하게 1518번 풀이! 문제출처: https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 처음에는 반복문마다 deepcopy를 이용해 8행 8열씩 배열을 만들고, deepcopy된 배열 내에서 완전탐색으로 상하좌우와 다른 알파벳인지 확인하는 방식으로 해결하려고 했다. .. 2022. 11. 10.
[백준] 18258번 문제출처: https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 오랜만에 티스토리 글쓰기! 지난주에 티스토리가 안돼서 이대로 내 티스토리가 임종인줄 알았다.(ㅋㅋㅋㅋㅠㅠㅠ) 연산당 시간 복잡도가 O(1)임을 유의하여 deque를 이용해서 푸는 문제였다. 각각의 명령어 함수를 이용해서 풀어도 되고, 내 코드처럼 조건문을 이용해서 풀어도 될 것같다. (명령어를 함수화 하는 대신 반복문 안에서 조건문을 쓰니 조금 지저분해 보이는 .. 2022. 10. 22.
[백준] 2108번 문제출처: https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 주어진 홀수개의 숫자들에 대한 산술평균, 중앙값, 최빈값, 범위를 구하는 것이었다. 다 괜찮은데 최빈값 구하는데서 발목이 잡혔다. 찾아보니 collection 에서 Counter라는 모듈을 사용하면 된다고 한다. most_common을 쓰면 최빈값을 출력할 수 있고, 최빈값은 (해당값, 빈도수) 로 나타난다. 만약 빈도수가 같으면 두 번째로 작은 값을 출력한다. ​ 2022. 6. 15.
[백준] 11659번 문제출처: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 주어빈 배열의 i번째에서 j번째까지의 합을 구하는 문제이다. 더이상 따로 설명할 것없이 겉으로 보기에는 간단해보였는데 다 쓰고나니 시간초과에 걸렸다. 시간복잡도를 고려해야했다. 배열의 누적합을 구하는 경우, 배열을 모두 훑게되면 시간 복잡도가 O(N^2)으로 늘어난다. 따라서 prefix sum을 위한 배열을 하나 더 만들어주고, 거기에 누적 합을 따로 저장해둔다.. 2022. 6. 15.
[백준] 2331번 문제출처: https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 숫자 A,P가 주어지고, 처음은 A의 자릿수마다 P제곱 해준 값을 모두 더한 값으로 다음 수열값을 시작한다. 이후 그 뒤에 자릿수마다 P제곱의 합으로 다음 수열값을 만든다. 이걸 계속 하다보면 언젠간 같은 부분이 반복되는 지점이 생긴다. 그 반복되는 지점을 싹다 지우고, 남는 원소들의 개수를 구하는게 이 문제의 요지이다. 원소가 어떤게 남아있는지, 혹은 남은 원소의 모든 합을 구해도 좋을 것같은데 그렇게 하면 처리하는 시간이 더 오래걸려서 그냥 문제를 제한시간 2초에 개수를 구하라. 정도로 끝난것.. 2022. 6. 15.
[백준] 2577번 문제출처: https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 주어진 세 개의 수를 곱하여 나온 숫자에서 0~9까지의 개수를 각각 순서대로 출력하는 문제이다. 숫자의 길이랑 10의 몇 제곱이고를 따지는 것은 불편할 것같아 그 값을 문자열로 바꾸고, 문자열 첫번째 자리부터 '0'이면 0의 개수 count 값에 +1, ..., '9'면 9의 개수 count 값에 +1 하는 식으로 반복했다. 쉬운 단계의 문자열 문제는 이제 어느정도 할 수있을 것같지만, 혹시라도 내가 놓친 것들이나 아직 잘 다루지 못하는 라.. 2022. 6. 15.

티스토리툴바