최선을다하는

저번 주 토요일 검정시험을 마지막으로 방학 동안 했던 SWEA 특강이 마무리되었다. 풀어야 하는 문제 수도 많고 쉽게 쉽게 풀리지 않는 문제들이 대다수였는데 이 때문에 코딩 문제 풀이 실력이 많이 는 것 같다. 특히 인상 깊었던 것 세 가지를 꼽자면 비트 마스킹/ 메모리풀 / 해시라고 할 수 있을 것 같다. 우선 비트 마스킹은 이름만 많이 들어보고 실제로 사용해본 적이 없던 것 같다. 배열을 사용해도 풀 수 있는 문제들이 많았기 때문인데 비트 마스킹을 사용하다보니 배열과 비트마스킹이 서로 강한 부분들을 느낄 수 있었고 이제는 그래도 상황에 맞게 비트마스킹을 사용할 수 있게 된 것 같다. 그다음으로는 링크드리스트 자료구조를 사용할 때 메모리풀 기법을 사용하는 것이었다. 실제 코딩 테스트 문제에서는 mall..

No1. 메모장 프로그램 실제 메모장 처럼 원래 있는 텍스트 문자열을 읽어들인 다음 커서의 위치에 삽입, 커서 옮기기, 그리고 커서 뒤에있는 특정 원소의 개수 찾기 총 3가지의 기능을 만드는 문제였다. 구상을 최소 한시간 그리고 1시간 반까지도 해도 된다는 코치님들의 말을 실천하고자 우선 펜 부터 잡았다. 처음에는 메모장의 최대 크기가 300*300 이여서 배열을 2배 사이즈로 놓고 짝수 인덱스는 커서 홀수 인덱스는 문자로 놓고 풀려고 했다. 하지만 조금만 더 생각 해보니 삽입 연산을 추가하면 문자들이 한칸 씩 뒤로 밀리게 되어 배열을 사용하면 절대 안될 것 같았다. 만약 구상을 하지 않았다면 배열로 열심히 구현하다가 눈물을 머금고 지울뻔 했다. 그래서 삽입 연산에 유리한 링크드 리스트를 활용하려 하였고..

오늘 강의는 해쉬에 대한 내용이었다. 해쉬는 프로그래밍을 공부하기 시작하면서 처음부터 되게 많이 들어본 자료구조인데 실제로는 한 번도 써보지 않았다. 그냥 막연히 해쉬 버킷을 나누고 버킷에 원소를 넣어두는 형식으로 알고만 있었는데 실제로 해쉬 버킷을 나누고 관리하는 것이 중요한 부분이었다. 들어오는 원소를 특정 변환 함수로 변환을 해서 키값을 얻어내는데 이 키값으로 해쉬 버킷을 나누는 것이었다. 해쉬 버킷이 총원소의 수보다 적기 때문에 키값이 겹칠 수밖에 없는데 이때 해쉬 버킷의 원소는 최대한 균등하게 배분되어야 해쉬 버킷으로 나누는 의미가 있기 때문에 균등하게 나누는 것 역시 중요하였다. 연습 문제는 많이 풀지 못했는데 처음 사용하는 자료구조라 쉽게 풀 엄두를 내지 못하였다. 주말에 풀고 다시 올려야겠..

이번 시간에는 힙에 관한 내용이었다. 저번 학기 알고리즘 수업 때 힙을 되게 많이 다루어서 힙에는 자신감이 있었다. 수업을 듣기 전에는 힙을 이름만 알고 잘 몰랐지만 학기 중에 여러 번 구현하면서 잘하는 줄 알았지만 아니었다! 수업 때 강의자료에 있는 adjust() 코드를 항상 옆에 참조해서 풀어서 그런가 보다. 수업 때 배운 adjust는 미리 수의 배열이 있고 마지막 부모 노드부터 자식 노드들을 확인하며 자신 아래의 트리가 힙의 원칙에 맞는지 판단하는 방식으로 O(n)의 시간이 걸렸고 heap에서 꺼내어 정렬하는데 O(nlogn)의 시간이 걸려 총 O(nlogn)의 시간이 걸린다. 이번 강에서 배운 내용은 숫자가 주어질 때 heap에 push와 pop을 하는 방법이었다. 처음에 adjust를 사용하..

설날 연휴 기간에는 추가로 진도를 나가지 않아 그동안 풀지 않았던 문제들을 풀기로 하였다. 내 코드들은 깃허브에 커밋해두었다! https://github.com/Ho-hoho/SWEA/tree/main No3. 동아리실 관리하기 (SWEA 3316) 부원이 4명이기 때문에 비트마스킹으로 겹치는 사람들을 잘 확인하면 되는 문제였다. 처음엔 일일이 스위치문을 사용하여 ABCD 를 비트로 바꿨는데 다른 사람의 코드를 보니 1

6번째 내용은 트리였다. 강의 내용은 역시 어려운 것은 없었고 순회 방식등에 대한 내용이었다. 그리고 4문제가 기본문제로 주어졌는데 처음 2문제는 어렵지 않게 풀 수 있었다. 3번째 문제는 SWEA 1232번 사칙연산 문제였다. 앞선 두문제와 다르게 한자리 숫자가 아닌 여러자리 숫자가 올 수 있었으며 인덱스가 N의 반이 넘어가도 리프노드가 아닐 수 있어 문자가 올지 숫자가 올지 모르는 경우였다. 그래서 사칙연산 자체는 쉬웠으나 입력값을 받는데 난항을 겪었다. char 형식으로 받으려다가 마지막에서야 string 으로 받은 다음에 숫자면은 int 로 변환을 하는 방법을 사용했다. string stream 을 사용했지만 그냥 stoi 를 사용하는게 더 편했을 것 같다. vector 나 queue를 사용하면서..

SWEA의 5번째 내용은 그래프 탐색에 관한 내용이었다. 그래프 탐색에는 여러 가지 이론들이 있지만 강의에서는 대표적인 DFS와 BFS에 관한 내용이 나왔다. 강의는 너무 쉬운 내용이라 금방 넘겼고 바로 문제 풀이에 들어갔다. 기초 DFS와 BFS라는 제목을 가진 문제 두 개를 풀었는데 DFS와 BFS를 활용하는 문제였는데 문제가 굉장히 불친절했다. 입력값도 트리를 파악할 수 없게 만들어 직접 출력해보아야 했고 입력값에 쓰레기 값도 들어있어서 문제 풀이에 굉장히 난항이 있었다. BFS 문제는 그보다 나았지만 행과 열 순서로 주지 않고 열 과 행 순서로 좌표를 주고 인덱스는 (0,0)부터 주지만 실제 좌표는 (1,1)부터 시작하여 굉장히 혼란스러웠다. 그리고 난 후 기본문제를 풀기 시작했는데 프로세서 연결..

이번 내용은 분할 정복에 관한 내용이었다. 분할 정복의 대표적인 문제로 머지 소트, 퀵 소트, 그리고 이진 탐색을 공부하였다. 특별히 어려운 내용은 없었다. 저번 학기에 알고리즘 수업에서 되게 자세히 배운 내용이라 친숙하였다. 대부분의 내용이 수업 때 배운 내용보다 깊지 않은 내용이었는데 임인성 교수님이 굉장히 잘 가르쳐 주시고 시험 문제도 시간 복잡도와 다양한 코드를 접할 수 있게 출제하셔서인지 기본적인 알고리즘에 대한 이해도가 굉장히 높아졌다는 것을 느낄 수 있었다! 주어진 문제를 보니 바로 vector를 이용한 쉬운 풀이와 오늘 배운 분할정복으로 직접 정렬하여 문제를 풀 수 있겠다. 하지만 두 문제 다 50개의 테스트 케이스 중 0개 성공, 즉 다 실패해버렸다. 2시간을 고민하고 답을 뒤지던 중 정..

3번째 강의는 그리디, 완전 탐색, DP에 관한 내용이었다. 대부분은 친숙한 내용이었지만 visited를 비트 마스킹으로 배열이 아닌 int로 사용한다는 것이 신기했다. 이러한 비트 연산을 통해 재귀와 DP를 같이 사용할 때에도 [N][1

오늘은 링크드 리스트에 관한 내용을 공부하였다. 링크드 리스트의 경우 코딩 테스트 문제들에서는 한 번도 사용한 기억이 없는 것 같다. 보통 배열을 사용하거나 요즘 들어서는 vector를 사용하는 경우가 더 많았던 것 같다. 그래서 링크드 리스트는 학교 수업에서만 몇 번 사용한 것 같다. 하지만 학교 수업에서 배열을 이용하여 huffman encoding을 하려고 했을 때 배열로 구현하려다가 실패하고 링크드 리스트로 구현했던 기억이 있다. 오늘 들은 강의에서도 코딩 테스트 문제에서 링크드 리스트는 많이 쓰이는 자료구조라고 하니 이렇게 배열이나 vector 보다 링크드 리스트가 편한 경우도 있나 보다! 강의자료의 처음에 메모리 풀이라는 정적 할당의 한 방식을 보았다. 처음 보는 방식이었는데 되게 신기하였다...