컴굥일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12985 문제 내용 N명의 참가자는 번호를 1~N번으로 부여받아 토너먼트 식으로 경기를 하게 된다. 매 라운드마다 (1,2), (3,4), ...., (N-1,N)이 토너먼트 경기를 하게 된다. 우리는 A번 참가자와 B번 참가자가 몇 라운드에 만나게 될지를 출력하면 된다. (그전까지 두 참가자는 항상 이긴다) 문제 풀이 위 그림은 각 라운드별로 어떤 참가자들이 겨루게 될지를 그려둔 것이다. (같은 조에 있으면 싸우게 된다.) 참가자는 항상 2의 지수승으로 주어져 부전승이 발생하지 않고, 2^20명까지 참가하니 라운드의 수는 최대 20까지 가능하게 된다. 우리는 입력받은 a와 b가 각 라운드별로 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42842 문제 내용 위의 사진과 같이 안쪽에 노란색 칸들이 있고, 이를 1줄로 감싼 갈색 칸들이 있다. 갈색 칸의 개수와 노란색 칸의 개수가 주어질 때, 전체 카펫의 가로, 세로 길이를 구하면 된다. 문제 풀이 문제의 상황을 그림 그려보면 위와 같다. 우리는 a와 b에 어떤 값이 들어가면 되는지를 찾으면 쉽게 문제를 해결할 수 있다. 이때 갈색 격자의 수는 8~5,000, 노란 격자의 수는 1~2,000,000라고 한다. 즉 2a*2b+4

문제 https://www.acmicpc.net/problem/11564 문제 내용 좌표축이 -10^18 ~ 10^18까지 주어진다. 점프력 k와 초콜릿이 놓여있는 시작 위치 a, 끝 위치 b를 입력받아 몇 개의 초콜릿을 먹을 수 있는지 출력한다. 점프 횟수에는 제한이 없다. 문제 풀이 일단 좌표의 범위가 int 범위를 넘어가기 때문에, long long으로 선언한다. 점프력이 k로 고정되어 있고, 점프 횟수에 제한이 없기 때문에, 수학적으로 계산만 하면 된다. 0으로 시작하거나 끝나거나, 0을 포함하는 구간의 경우에는 초콜릿이 0번 자리에도 있으니 +1 하는 것을 잊으면 안 된다. 0이 포함되지 않고 한쪽으로 치우쳐져 있는 경우는, 음수나 양수나 계산 방법이 똑같다. 편의를 위해 음수일 경우 양수로 바..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12973 문제 내용 문자열에서 같은 글자 2개가 붙어있으면 제거해 주면 된다. (계속해서 지워나가야 함) b aa baa -> bb aa -> aa -> 위와 같이 연달아 같은 문자가 있으면 제거해주면 된다. 끝까지 제거했을 때, 문자열을 모두 제거할 수 있으면 1을, 문자열이 남게 되면 0을 return 한다. 문제 풀이 맨처음에는 문자열에서 붙어있는 곳을 찾아서 그 부분만 빼고 삭제하는 방법으로 구현을 했다. 이 풀이는 반복문을 여러 번 돌아야 하기 때문에 효율성 체크에서 실패가 떴다. (해당 코드가 궁금하면 더보기 클릭) 더보기 정확성 체크는 통과, 효율성 체크는 실패하는 코드 #inclu..

문제 https://www.acmicpc.net/problem/2170 문제 내용 선분을 여러 개 입력받아, 선분끼리 이을 수 있는 것은 잇는다. 최종적으로 그려져있는 선들의 길이의 총합을 구하면 된다. (서로 이어진 선분은 하나의 선으로 생각한다) 문제 풀이 골드 5 문제이지만, 문제의 풀이 방법을 떠올리면 그렇게 어렵지 않다. 1. 먼저 선분들을 정렬한다. (c++ sort 함수 쓰면, 선분의 시작이 증가하는 순으로 + 같을 경우 선분의 끝 지점이 증가하는 순으로 알아서 정렬해준다.) 2. 선분이 이어지는지를 체크한다 ( 이전 선분의 끝 지점 >= 현재 선분의 시작 지점 )이면 두 선분은 이어진다고 볼 수 있다. 이 경우, 이전 선분의 끝 지점을 갱신해 주면 된다. (max 값으로 갱신해야 한다. (..

문제 https://www.acmicpc.net/problem/7576 문제 내용 1은 익은 토마토를, 0은 아직 익지 않은 토마토를, -1을 토마토가 없는 칸을 뜻한다. 토마토는 인접한 토마토에게 영향을 받는데, 익은 토마토 옆의 익지 않은 토마토는 하루 뒤에 익게 된다. 토마토가 모두 익을 때까지의 최소 날짜를 출력하면 된다. (불가능한 경우 -1 출력) 문제 풀이 bfs로 문제를 풀면 된다. 단, 처음 시작할 때 1이었던 토마토들을 queue에 모두 넣은 상태로 돌려야 한다. 전부 익을 때까지 얼마나 걸리는지를 구하고 싶기 때문에, 이는 최단거리 문제라고 볼 수 있다. (거리는 아니지만 개념은 같다) 토마토 개수를 입력받을 때 세어둔 뒤에, bfs를 통해 익은 토마토를 체크하면서 -1 하고, 마지막..

문제 https://www.acmicpc.net/problem/10816 문제 내용 숫자 카드들을 입력받고 수를 입력받아, 그 수에 해당하는 숫자 카드의 개수가 몇 개인지를 출력하면 된다. 이때 숫자 카드의 개수는 500,000까지이고, 숫자 카드에 적혀있는 정수는 -10,000,000~10,000,000이다. 입력받는 수 또한 500,000개까지 주어질 수 있다. 문제 풀이 배열을 크게 선언해두고, 있으면 값을 증가시키는 방법은 사용할 수 없다. 숫자 카드에 적힌 정수의 범위가 너무 크기 때문이다. 이 문제는 이분탐색을 사용하면 좋다. 이분탐색이라 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법으로 탐색 전에 반드시 ..

문제 상황 코딩테스트 문제를 풀며 terminated with exit code: 3221225477. 라는 에러 문구를 만나게 되었다. 분명 코드 상 로직이 틀린 것 같지는 않아 의아했다. 문제 해결 방법 입력받는 부분에서 실수가 있었다. 10번째 줄에 vector arr; 코드가 문제였다. 선언은 했으나 초기화를 안 한 상태에서 입력을 받아 문제가 생겼다. (초기화를 해주니 코드가 잘 돌아간다) 참고한 글 https://0netw0m1ra.tistory.com/5 [VScode] 오류 잡기 - exit code: 3221225477 C언어 작성시, scanf() 함수에서의 사용자 오타로 인해 발생하는 문법 오류 (오류 발생) scanf("%d", num); (오류 해결) scanf("%d", &num..

문제 https://www.acmicpc.net/problem/1806 문제 내용 합이 S이상이 되는 연속되는 수열의 부분합 중에, 가장 짧은 길이를 출력하면 된다. 문제 풀이 투포인터 방식으로 문제를 해결하면 쉽게 해결할 수 있다. st와 en 포인터를 두고, st~en까지의 합이 S보다 작으면 en을 증가시키고, 그렇지 않으면 st를 증가시키면 된다. 인덱스(st, en)가 바뀌면 total 값도 조정을 해주어야 한다. st가 en을 앞서는 순간이 오거나, st나 en이 n이 되면 break를 걸어 불필요한 연산을 줄이고 인덱스 에러를 막아야 한다. 또한 합이 S이상인 부분합을 만들지 못하면 0을 출력해야 한다는 것을 놓치면 안 된다. 코드 #include #include using namespace..

문제 https://www.acmicpc.net/problem/14888 문제 내용 연산에 사용될 수들과 연산자가 주어진다. 연산에 사용되는 수들은 순서를 바꾸지 않고 입력된 순서대로 사용한다. 연산자는 순서를 바꾸어 식을 계산했을 때 가장 큰 결과와 작은 결과를 출력하면 된다. (단, 연산은 우선순위 관계없이 좌->우로 계산한다.) 문제 풀이 백트래킹을 통해 연산자의 순서를 결정하면 된다. 같은 연산자가 여러번 사용될 수도 있지만, 개수의 제한이 있다는 것을 유념해야 한다. 아래 N과 M(9) 문제와 푸는 방식이 유사하다. [BOJ/백준 15663][C++] N과 M (9) 문제 https://www.acmicpc.net/problem/15663 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열..