Algorithm/백준
-
[C][백준] ChatGPT로 백준 문제를 풀었다? - Python to C language migration, 9012번 괄호Algorithm/백준 2023. 3. 18. 22:03
들어가기에 앞서... 이 포스트는 BOJ의 치팅을 권장하는 것이 아닙니다. 작성자도 기존에 Python으로 풀었던 문제를 C언어로 변환한 것입니다. 도입 ChatGPT는 코딩도 뚝딱해준다. 그러면 혹시 코딩테스트도 통과할 수 있을까..? 그렇지만, 처음 보는 문제를 내가 안 풀었는데, ChatGPT가 쓴 코드로 제출한다면 반칙이다. 그래서, 예전에 Python으로 쓴 코드를 C언어로 code migration하는 것으로 대체하겠다. 추후 양심에 털이 난다면, 아예 새로운 문제로 실험해보겠다. 문제 실험에 사용될 문제는 Baekjoon Online Judge에 있는 9012번 '괄호'이다. https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis..
-
[C][백준] 5567. 결혼식 구현하기 | 깊이 제한 그래프 탐색Algorithm/백준 2023. 3. 6. 10:00
이 문제의 핵심은 자신의 친구, 친구의 친구만 초대하는 것이다. 즉, 나(1번 노드)를 기준으로, 2단계 이내로 연결된 친구만 초대하는 것이다. 그렇다면 이 문제는 그래프 탐색 알고리즘에서 깊이를 제한하는 코드를 만들면 되는 것이다. 문득, 궁금증이 들었다. ChatGPT에 물어볼까? 그래서 ChatGPT에 이렇게 물어보았다. 자세한 답변 분석은 다음 포스트에 하겠다 아무튼 이 코드를 그대로 복붙할 수는 없으니 나의 코드와 결합하여 문제에 맞게 수정하였다. ChatGPT에서 얻은 것은 level 배열을 쓰는 모티브랄까? #include #define MAX_SIZE 10005 int vertex, edge; int table[505][505] = {0}; int visit[MAX_SIZE] = {0}; ..
-
[C][백준] 20055번 컨베이어 벨트 위의 로봇 풀이 : 원형 연결리스트, 삼성 SW 역량 테스트 기출 문제Algorithm/백준 2022. 11. 2. 23:12
무려 삼성 SW 역량 테스트 기출 문제 이다. ㄷㄷ 상당히 문제가 난해하다. 난해하다는게, 문제의 조건을 오해하기 쉽다는 것이다. 사람들이 자주 햇갈리는 문제의 조건은 다음과 같다. 1단계는 과정 1, 2, 3, 4를 한꺼번에 묶은 것이다. 과정 1 → 2 → 3 → 4 → 1 → 2 → 3을 하고 끝나면 2단계에서 종료된 것이다! 처음에 로봇이 없어도 컨베이어 벨트는 돌아간다. N번째 칸에 가면 무조건 로봇을 내린다. 과정 2: 가장 먼저 벨트에 올라간 로봇부터 한 칸씩 이동한다. 이 조건을 간과하면 예제 입력 4번이 틀릴 것이다. 문제만 잘 이해하면 코드는 금방 짤 것이다. 그러나 문제를 이해하지 못하면 이런 사태가 날 것이다. 이게 코딩 문제야? 논술 문제야? 백문이 불여일견 코드를 보고 이해해보자..
-
[C][백준] 1357번 뒤집힌 덧셈 풀이 : 문자열, 배열을 쓰지 않고, C 숫자 분리Algorithm/백준 2022. 9. 29. 21:39
뒤집힌 덧셈. 학생들이 반복문을 배웠을 때 이 문제를 풀어야한다더라 처음에는 배열을 이용하여 풀었..지만 아뿔싸! 커리큘럼상 반복문을 배우고 나서 배열과 문자열을 배운다. 어떻게 하면 반복문과 조건문만을 가지고 이 문제를 풀 수 있을까?? 이 2가지를 잘 생각하면 문제를 풀 수 있다. 1. 주어지는 수는 1000 보다 작거나 같다. 2. 수에서 숫자 분리하는 방법. // 수에서 숫자 하나씩 분리 int num = 123; while(num) { printf("%d", num % 10); num /= 10; } // 출력결과: 321 수를 10으로 나눈 나머지를 출력하고 수를 10으로 나누면 수를 숫자 하나하나씩 분리할 수 있다. 풀이: // 문자열, 배열을 사용하지 않고, 반복문, 조건문만 사용해서 풀 ..
-
[C][백준] 2346번 풍선 터뜨리기 문제 풀이 : 원형 연결리스트를 사용하여Algorithm/백준 2022. 9. 7. 18:27
#include #include #include typedef struct _node { int data; int pos; struct _node *next; struct _node *prev; } node; node *head; node *tail; node *cur; void init() { head = (node *)malloc(sizeof(node)); tail = (node *)malloc(sizeof(node)); head->data = 'H'; tail->data = 'T'; head->pos = 0; tail->pos = -1; head->next = tail; head->prev = tail; tail->next = head; tail->prev = head; cur = head; } i..
-
[C][백준] 1158번 요세푸스 문제 : C, 원형연결리스트로 해결Algorithm/백준 2022. 9. 1. 19:35
#include #include typedef struct _node { int data; struct _node *next; struct _node *prev; }node; int N,M; node *head; node *tail; node *cur; void init() { head = (node*)malloc(sizeof(node)); tail = (node*)malloc(sizeof(node)); head->data = 'H'; tail->data = 'T'; head->next = tail; head->prev = tail; tail->next = head; tail->prev = head; cur=head; } int main() { scanf("%d%d",&N,&M); printf(""); ..
-
[Python][백준] 누적 합 알고리즘 | 11659번 구간 합 구하기 4 시간초과 해결Algorithm/백준 2022. 4. 18. 10:00
누적 합(prefix sum)이란? 배열에서 특정 구간의 합을 구할 때 사용하는 방법이다. 만약 이때 일반적인 순회법을 사용하면 시간복잡도가 O(n^2)일 것이다. 하지만 누적 합을 사용하면 O(n)의 시간복잡도를 가진다. # 리스트를 슬라이싱하고, 합을 구하는 소스코드... 시간초과 import sys def P11659(): N, M = map(int, input().split()) numbers = [0] + list(map(int, input().split())) for _ in range(M): s, e = map(int, input().split()) print(sum(numbers[s-1:e])) if __name__ == '__main__': input = sys.stdin.readline..