스터디

• 주 1회

• 강의 : 이선협 강사님 동영상 강의 + 관련자료(공유)

• 해당 주제를 돌아가며 진행

• 폴더 구조 : 해당 주차 → 이름 → 문제

• 커밋 메시지 형식: Feat: 주제명 문제제목(1023번)

• 요일 : 화요일

• 시간 : 15시

스터디 목차

1. 연결 리스트, 스택, 큐 - (종운님)
발표 자료
KDT FEDC - 자료구조&알고리즘 스터디 - 배열과 연결리스트
배열과 연결리스트 오늘 알아볼 주제는 배열, 연결 리스트, 스택, 큐 인데요 배열과 연결리스트, 스택과 큐 두 파트로 나눠서 진행해보려고 하고요 어려운 내용은 아니니 편하게 들어주시고 중간 중간 잘못된 부분이나 궁금하신 부분이 있다면 말씀주시면 좋을 것 같습니다.

https://docs.google.com/presentation/d/1vovrQj7xb864nFnrPMqqgpVhHQUNlx5nuRNSwfYI4Eo/edit?usp=sharing

KDT FEDC - 자료구조&알고리즘 스터디 - 스택과 큐
스택과 큐

https://docs.google.com/presentation/d/1S_aX7C2zo4BuUge1CPu4R-9sCS5ws4xgtmeA0c9CJ9A/edit?usp=sharing

코딩 테스트 문제

school.programmers.co.kr

https://school.programmers.co.kr/learn/courses/30/lessons/12906

school.programmers.co.kr

https://school.programmers.co.kr/learn/courses/30/lessons/12909

3190번: 뱀

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.



https://www.acmicpc.net/problem/3190



// baekjoon 예제 코드

// baekjoon에 제출하여 동작할때는 input에 baekjoon의 입력이 들어오고
// 로컬 환경에서 동작할때는 input에 ``안에 넣어둔 문자열이 들어옴
const input = process.execArgv.includes("--stack-size=65536") ? require('fs').readFileSync('dev/stdin').toString() : `
예제 입력
`.trim()

// 제출할 정답
console.log(`제출할 정답`)

2. 해시테이블 - (수혁님)
발표 자료
https://docs.google.com/presentation/d/1wrmzlC2cC7aBoRYBFDwYSyT-WvW5JxHKfH61QPxmHNw/edit#slide=id.p
코딩 테스트 문제
1269번: 대칭 차집합
자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

https://www.acmicpc.net/problem/1269

14425번: 문자열 집합
총 N개의 문자열로 이루어진 집합 S가 주어진다.

https://www.acmicpc.net/problem/14425

school.programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/42579

3. 그래프 - (혜연님)
발표 자료
코딩 테스트 문제
2178번: 미로 탐색
N×M크기의 배열로 표현되는 미로가 있다.

https://www.acmicpc.net/problem/2178

1922번: 네트워크 연결
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

https://www.acmicpc.net/problem/1922

school.programmers.co.kr
https://school.programmers.co.kr/tryouts/101815/challenges

4. 트리 - (유경님)
발표 자료
코딩 테스트 문제
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/11725

2533번: 사회망 서비스(SNS)
페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 

https://www.acmicpc.net/problem/2533

school.programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/42892

5. 힙 - (진아님)
코딩 테스트 문제
프로그래머스 - 더 맵게 (level2)
school.programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/42626
백준 - 최소 힙 (실버1)
1927번: 최소 힙
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/1927

백준 - 카드정렬하기 (골드4)
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

https://www.acmicpc.net/problem/1715

6. 트라이 - (혜연님)
발표 자료
코딩 테스트 문제
14426번: 접두사 찾기
문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다.

https://www.acmicpc.net/problem/14426

school.programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/42577
school.programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/17685

7. 정렬 - (수혁님)
발표자료
코딩 테스트 문제
1374번: 강의실
N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

https://www.acmicpc.net/problem/1374

1141번: 접두사
접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

https://www.acmicpc.net/problem/1141

1461번: 도서관
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

https://www.acmicpc.net/problem/1461

8. 이진 탐색 - (종운님)
발표자료
KDT FEDC - 자료구조&알고리즘 스터디 - 이진 탐색
Binary Search 이진 탐색

https://docs.google.com/presentation/d/1VWYdlbc1rOjVgFUOZOJu3pwH3wUmAIPq9T0KGX9B4vE/edit?usp=sharing

코딩 테스트 문제
school.programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/43238
16401번: 과자 나눠주기
명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

https://www.acmicpc.net/problem/16401

10815번: 숫자 카드
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/10815

9. BFS, DFS - (진아님)
발표자료
[알고리즘]깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)
DFS/BFS 는 그래프 자료구조에 기반한 대표적인 '탐색' 알고리즘이다. 그래프 탐색 순서에 따라 DFS 와 BFS 가 구분된다. 💡 그래프 탐색 알고리즘 그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. 그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다. 많은 그래프에 대한 문제를 해결하기 위해서 그래프 탐색 알고리즘을 알아야하는데 예를들어 다음과 같은 상황에서 탐색이 필요하다. 한 정점과 다른 정점의 경로를 구할 때 그래프가 연결되어 있는지 확인할 때 신장 트리(Spanning Tree)를 찾을 때 💡 깊이 우선 탐색(DFS - Depth-First Search) DFS 는 한국어로 '깊이 우선 탐색' 이라고 불리며, '스택'..

https://codingkitty.tistory.com/54

코딩 테스트 문제
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/2667

11724번: 연결 요소의 개수
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/11724

2606번: 바이러스
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

https://www.acmicpc.net/problem/2606

10. 그리디(유경님)

11. 백트래킹

12. 동적계획법