alps-jbnu / 22alpstudy Goto Github PK

@jys-jeong @AFpine @bootkorea @곽성대 (<-santam? 맞나요?)
매주 자료구조 관련 문제풀이를 진행하는 것 같은데 문제를 선별해서 진행하는 것인지 궁금합니다. 예를 들어서 몇 문제는 정해두고 멤버들이 다 푸는 방식으로 진행하는 것인가요? 문제를 미리 선별해서 진행하는 것이라면 선별되는 문제 목록도 같이 정리해주면 좋을 것 같습니다.

금주 해결할 문제의 양이 많아, 효율적인 스터디 진행을 위해 필요한 내용을 조사하려 합니다.

3/29 18:00까지 풀어보시고, 그 이후부터 올려주시면 되겠습니다.
'풀어보았지만 끝까지 해결하지 못한 문제' 를 적어주시고, 이후 본인의 풀이 방법을 공유하고자 하는 분은 '좋아요'를 남겨주시면 되겠습니다.

@zs0057 @JC-arl @tjdeo1102 @vuswltmd

금일 자료구조 B 스터디 중 다루었던 문제입니다.
예제 Case도 만족하고, 스터디원들과 코드 내 어떤 문제가 있는지 고민해보았지만..
끝까지 해결하지 못했습니다.

다음은 문제의 코드 전문입니다.

#include <iostream>
#include <set>
#include <map>

using namespace std;

multiset<int> team;
map<int,int, greater<int>> student_h;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int temp_h, temp_k;
		cin >> temp_h >> temp_k;
		student_h.insert(make_pair(temp_h,temp_k));
	}
	for (auto &cnt:student_h)
	{
		int temp = cnt.second - 1;
		auto at = team.lower_bound(temp);
		if (team.empty())
		{
			team.insert(1);
			continue;
		}// team에 요소 없을때 새로운 팀 생성
		if(at==team.end()) //lower_bound는 해당 값보다 같거나 큰값에서 가장 첫번째 요소를 반환하는 건데, 반환값이 teeam.end()면 해당 값보다 큰값이 없다는 것이므로 가장 큰 요소를 지우고 카운트
		{
			int temp2 = *--team.end(); //큰 수에 넣을 수록 가장 팀을 많이 줄일 수 있음-> 키 큰 사람을 수용할 사람은 많지 않기에..
			team.erase(--team.end());
			team.insert(temp2 + 1);
			continue;
		}
		if (at == team.begin()) //찾은 값이 처음 요소일때는 입력했던 값이 가장 작은 경우일 때도 있으므로-> 이 경우에는 어떤 팀을 가더라도 키큰 사람많아서 탈주한다.
		{
			if (temp < *team.begin())
			{
				team.insert(1);
				continue;
			}
		}
		int temp3 = *at; //위의 경우가 아니라면 lower_bound에 해당되는 값을 찾은 것이므로, 해당 위치 값을 삭제하고 그 해당 위치값 +1을 카운트 해서 다시 삽입
		team.erase(at);
		team.insert(temp+1);
	}
	cout << team.size();
	return 0;
}

채점 중 오답으로 처리되는 것으로 보아, 분명한 반례가 존재하는 것 같지만 어떤 반례가 있는지 갈피를 잡을 수 없었습니다.
도움을 주시면 감사하겠습니다!

스터디가 많이 남지 않아서 마지막 주제는 Segment Tree로 할게요~

1, 2, 3

segment tree 기본 연습한다는 느낌으로 하면 좋을 것 같습니다

@bootkorea , @jys-jeong, @rkdbq , @tlstmdgjs , @tjdeo1102

Minimum Spanning Tree 파트 관련 과제 (난이도 순서)

필수
[1] [2] [3]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 시간복잡도는?

스터디 전까지 모두 풀어와주세요!

스터디 시작 전까지 Issue에 자신만의 답을 남겨주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

톡방에 전달 부탁드립니다~

@tjdeo1102 @rkdbq @jys-jeong @bootkorea @tlstmdgjs

1

효율적인 스터디 진행을 위해 필요한 내용을 조사하겠습니다.

4/5 18:00까지 풀어보시고, 그 이후부터 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

1. 해결하였지만, 어려움을 겪었던 문제
2. 끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
3. 이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제
   를 댓글로 남겨주시면 됩니다.

댓글로 남겨진 문제는 스터디 시간에 필수적으로 다루어지므로 가능하다면 무조건적으로 해결하는 편을 권장합니다.

@alphasobs @tjdeo1102 @zs0057 @vuswltmd @JC-arl

' 누르기 귀찮은데;

Stack/Queue/Deque 파트 관련 과제 (난이도 순서)

필수
[1] [2] [3]

• 문제집에 체크 표시 된 문제들

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 구현은 어떻게?
4. 시간복잡도는?

다음주 (14일 ~ 30일) 스터디 전까지 모두 풀어와주세요! (최소한 필수 문제라도)

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

@Zun-H-fighter @chan-gi @enjuS2 @esther107 @eunly00 @rlathdns @ledohy @qowlgur121 @seg7577 @wss0702 @yseoha

효율적인 스터디 진행을 위해 필요한 내용을 조사하겠습니다.

5/15 18:00까지 풀어보면서, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

@AFpine @Zoe305 @tlstmdgjs @IMAYOUNG @rkdbq @jys-jeong

알고리즘 A 공지

9/13 18:00까지, 아래 조건에 해당하는 문제라 판단되면 댓글로 남겨주세요!

• 해결하였지만, 어려움을 겪었던 문제
• 끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
• 이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

댓글로 남겨진 문제는 최대한 해결해보는 것을 추천드립니다.

Dynamic Programming 파트 관련 과제 (난이도 순서)

필수
[1] [2]

보너스 (위 문제와 비슷함)
[1] [2] [3] [4] [5] [6]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지? (특히, 점화식은 어떻게 세울지)
3. 구현은 어떻게?
4. 시간복잡도는?

다음주 (19일 ~ 23일) 스터디 전까지 모두 풀어와주세요! (최소한 필수 문제라도)

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

(전달 받으신 분은 각 스터디 톡방에 공유 부탁드립니다~)

@tjdeo1102 @rkdbq @jys-jeong @bootkorea @OH-JUHYONG @tlstmdgjs @HwangSgHn @vuswltmd

5/29 18:00까지 풀어보면서, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

댓글로 남겨진 문제는 스터디 시간에 필수적으로 다루어지므로 가능하다면 무조건 해결하는 편을 권장합니다.

@alphasobs @tjdeo1102 @zs0057 @vuswltmd @JC-arl

Array/Linked List 파트 관련 과제 (난이도 순서)

필수
[1] [2]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 구현은 어떻게?
4. 시간복잡도는?

다음주 (19일 ~ 23일) 스터디 전까지 모두 풀어와주세요! (최소한 필수 문제라도)

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

(전달 받으신 분은 각 스터디 톡방에 공유 부탁드립니다~)

@Zun-H-fighter @chan-gi @enjuS2 @esther107 @eunly00 @rlathdns @ledohy @seg7577 @wss0702 @yseoha

@copyrat90 @qhur135 @Sabro98

자신이 내일 어떤 문제를 설명할건지 간략하게 써주세요~

여기 적힌 문제들은 최소 한번쯤은 생각해보고 스터디 시간에 공유하는게 좋아보이네요

<Heap => Priority_queue>

5/29 18:00 이후, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

@AFpine @Zoe305 @tlstmdgjs @IMAYOUNG @rkdbq @jys-jeong

Hash 연습문제를 행렬의 각 성분에서 깊이 우선 탐색을 활용해 접근하였는데 메모리 초과가 발생했습니다. 저번 재귀함수 이슈와 유사한 에러인가 싶어 고민해보았지만 해결하지 못했습니다. 어떤 부분에서 왜 메모리 초과가 발생했는지 궁금합니다.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

int N, M;
string map[11];
vector<string> godStr;
int dx[8]{ 0,1,0,-1,1,1,-1,-1 };
int dy[8]{ 1,0,-1,0,1,-1,1,-1 };
int K;

unordered_map<string, long long> ans;
string cur;

void dfs(int curX, int curY) {
	cur += map[curX][curY];
	//cout << cur << "\n";

	if (cur.length() >= K) {
		ans[cur]++;
		return;
	}
		
	for (int i{}; i < 8; i++) {
		int nxtX{ curX + dx[i] };
		int nxtY{ curY + dy[i] };
		if (nxtX >= N) nxtX = 0;
		else if (nxtX < 0) nxtX = N - 1;
		if (nxtY >= M) nxtY = 0;
		else if (nxtY < 0) nxtY = M - 1;
		dfs(nxtX, nxtY);
		cur.pop_back();
	}
    return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M >> K;
	for (int i{}; i < N; i++) {
		cin >> map[i];
	}
	for (int i{}; i < K; i++) {
		string str;
		cin >> str;
		godStr.push_back(str);
	}
	for (int i{}; i < N; i++) {
		for (int j{}; j < M; j++) {
			cur.clear();
			dfs(i, j);
		}
	}
	for (auto it{ godStr.begin() }; it != godStr.end(); it++) {
		cout << ans[*it] << "\n";
	}
	
	return 0;
}

23번째줄 if문 occur역할이 뭔지모르겠어요.

코드

효율적인 스터디 진행을 위해 필요한 내용을 조사하겠습니다.

5/10 18:00까지 풀어보면서, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

댓글로 남겨진 문제는 스터디 시간에 필수적으로 다루어지므로 가능하다면 무조건 해결하는 편을 권장합니다.

@alphasobs @tjdeo1102 @zs0057 @vuswltmd @JC-arl

1. 예외처리
2. dx, dy 값 오타
3. h, w 입력 순서와 사용 순서

말이 되고픈 원숭이 문제를 풀며 위의 세 가지를 중점적으로 체크해보았을 때 이상없다고 생각하는데 제가 찾지 못한 오류가 있는 것 같습니다.
AC를 위해 조언해주시면 감사드리겠습니다.

#define MAX 201

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

class Monkey
{
public:
  int x;
  int y;
  int horse;
  Monkey()
  {
    x = 0;
    y = 0;
    horse = 0;
  }
};

int k;
int w, h;
bool board[MAX][MAX];

int dx[4]{1, -1, 0, 0};
int dy[4]{0, 0, 1, -1};
int dxHorse[8]{1, -1, 1, -1, 2, -2, 2, -2};
int dyHorse[8]{2, 2, -2, -2, 1, 1, -1, -1};
int vis[MAX][MAX][31];
queue<Monkey> Q;

void showBoard(int k)
{
  for (int i{}; i < h; i++)
  {
    for (int j{}; j < w; j++)
    {
      cout << vis[i][j][k] << " ";
    }
    cout << "\n";
  }
}

void init()
{
  for (int i{}; i < MAX; i++)
  {
    for (int j{}; j < MAX; j++)
    {
      for (int k{}; k < 31; k++)
      {
        vis[i][j][k] = MAX;
      }
    }
  }
}

void bfs()
{
  while (!Q.empty())
  {
    Monkey cur{Q.front()};
    Q.pop();
    for (int i{}; i < 8; i++)
    {
      Monkey nxt{cur};
      nxt.x += dxHorse[i];
      nxt.y += dyHorse[i];
      nxt.horse++;
      if (nxt.horse > k)
        continue; // overThanK
      if (nxt.x < 0 || nxt.x >= h)
        continue; // outOfMap
      if (nxt.y < 0 || nxt.y >= w)
        continue; // outOfMap
      if (board[nxt.x][nxt.y])
        continue; // obstacle
      if (vis[nxt.x][nxt.y][nxt.horse] != MAX)
        continue; // visited
      Q.push(nxt);
      vis[nxt.x][nxt.y][nxt.horse] = vis[cur.x][cur.y][cur.horse] + 1;
    }
    for (int i{}; i < 4; i++)
    {
      Monkey nxt{cur};
      nxt.x += dx[i];
      nxt.y += dy[i];
      if (nxt.x < 0 || nxt.x >= h)
        continue; // outOfMap
      if (nxt.y < 0 || nxt.y >= w)
        continue; // outOfMap
      if (board[nxt.x][nxt.y])
        continue; // obstacle
      if (vis[nxt.x][nxt.y][nxt.horse] != MAX)
        continue; // visited
      Q.push(nxt);
      vis[nxt.x][nxt.y][nxt.horse] = vis[cur.x][cur.y][cur.horse] + 1;
    }
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> k;
  cin >> w >> h;
  for (int i{}; i < h; i++)
  {
    for (int j{}; j < w; j++)
    {
      cin >> board[i][j];
    }
  }

  init();
  Monkey st = Monkey();
  Q.push(st);
  vis[st.x][st.y][st.horse] = 0;
  bfs();

  // cout<<"\n";
  // for(int i{}; i<=k; i++) {
  //   showBoard(i);
  //   cout<<"\n";
  // }

  int ans{*min_element(vis[h - 1][w - 1], vis[h - 1][w - 1] + k + 1)};
  if (ans == MAX)
    ans = -1;
  cout << ans;

  return 0;
}

테스트123

Floyd 파트 관련 과제 (난이도 순서)

필수
[1] [2]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 시간복잡도는?

스터디 전까지 모두 풀어와주세요!

스터디 시작 전까지 Issue에 자신만의 답을 남겨주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

톡방에 전달 부탁드립니다~

@tjdeo1102 @rkdbq @jys-jeong @bootkorea @tlstmdgjs

위상 정렬 파트 관련 과제 (난이도 순서)

필수
[1] [2] [3]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 구현은 어떻게?
4. 시간복잡도는?

다음주 (24일 ~ 30일) 스터디 전까지 모두 풀어와주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

톡방에 전달 부탁드립니다~

@tjdeo1102 @rkdbq @jys-jeong @bootkorea @tlstmdgjs

5/24 18:00까지 풀어보면서, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

댓글로 남겨진 문제는 스터디 시간에 필수적으로 다루어지므로 가능하다면 무조건 해결하는 편을 권장합니다.

@alphasobs @tjdeo1102 @zs0057 @vuswltmd @JC-arl

https://www.sourcetreeapp.com/

5년 전부터 종종 쓰고 있는데, git 어려운 분 있으면 이거 써보세요

갑자기 생각나서 추천하고 갑니다

Recursion 파트 관련 과제

필수
[1] [2]

• 문제집의 실버 문제들

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 시간복잡도는?

스터디 전까지 모두 풀어와주세요!

스터디 시작 전까지 Issue에 자신만의 답을 남겨주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

@Sabro98

기업/대학원에서 어떤 절차와 어떤 종류의 문제로 코딩테스트를 진행하는지 웹 서베이도 같이 진행하시고 정리해서 공유하면 좋을 것 같습니다 (대표 기업/대학원 몇 개만 선별해서 진행하면 좋을 것 같습니다).

[예시]

Grarph/DFS/BFS 파트 관련 과제 (2주 분량)

필수
[1] [2] [3] [4]

• 문제집에 체크 표시 된 문제들

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 구현은 어떻게?
4. 시간복잡도는?

스터디 전까지 모두 풀어와주세요! (최소한 필수 문제라도)

또한, 스터디 시작 전까지 Issue에 자신만의 답을 남겨주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

@Zun-H-fighter @chan-gi @enjuS2 @esther107 @eunly00 @rlathdns @ledohy @qowlgur121 @seg7577 @wss0702 @yseoha

자료구조 스터디 피드백 중 가장 많이 나온 이야기가 양이 너무 많다 입니다.

더 나은 2학기 알고리즘 스터디의 진행을 진도를 개강 전/개강 후 2부분으로 진행할 필요가 있다고 생각합니다.
이를 위해 약간의 과제를 부여하게 되었고, 시간 많은 방학에 잘 공부하면 좋을 것 같습니다.

1. 자료구조 스터디 중 어려웠던 부분 복습. 특히 후반부 (재귀, 트리, BST, 해시 등) 꼼꼼하게
2. 쉬운 알고리즘을 방학 때 공부하기 [링크]
3. 공부 중 어려운 부분이 있으면 Issue에 등록해서 같이 해결

아쉽게도 방학 중 스터디를 하기에는 무리가 있어서 각자 개강 전까지 공부를 해야겠네요.
코드는 1학기와 비슷하게 /2022-2/Algorithm/Code/{name}/{topic}/{problem_number.cpp}형식으로 등록하면 될 것 같습니다.

@AFpine @rkdbq @jys-jeong @IMAYOUNG @tlstmdgjs @Zoe305 @bootkorea @vuswltmd @JC-arl @zs0057 @choi-w-s

<트리, BST>

5/22 18:00 이후, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

@AFpine @Zoe305 @tlstmdgjs @IMAYOUNG @rkdbq @jys-jeong

N(0 ≤ N ≤ 12)일 때 N!을 출력하는 문제입니다.
아래 두 코드 중 위의 코드는 정답 처리를 받았고, 아래 코드는 메모리 초과 판정을 받았습니다.
컴파일 시에도 그렇고 제 생각으로는 아래 풀이에 치명적 오류는 없는 것 같은데 메모리 초과 판정을 받은 이유가 궁금합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int factorial(int n) {
	if (n == 0 || n == 1) return 1;
	else return n * factorial(n - 1);
}
int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", factorial(n));
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int ans = 1;
int factorial(int n) {
	if (n == 0 || n == 1) return 1;
	ans *= n;
	factorial(n - 1);
}
int main() {
	int n;
	scanf("%d", &n);
	factorial(n);
	printf("%d\n", ans);
}

@copyrat90 @qhur135 @Sabro98

자신이 내일 어떤 문제를 설명할건지 간략하게 써주세요~

여기 적힌 문제들은 최소 한번쯤은 생각해보고 스터디 시간에 공유하는게 좋아보이네요

효율적인 스터디 진행을 위해 필요한 내용을 조사하려 합니다.

4/3 21:00까지 풀어보시고, 그 이후부터 올려주시면 되겠습니다.
'풀어보았지만 끝까지 해결하지 못한 문제' 를 적어주시고, 이후 본인의 풀이 방법을 공유하고자 하는 분은 '좋아요'를 남겨주시면 되겠습니다.

@AFpine @Zoe305 @tlstmdgjs @IMAYOUNG @rkdbq

안녕하세요 졸업생 윤준하라고 합니다 반가워요.

작은 이벤트를 하나 열까하는데요, 혹시 지금 비대면으로 진행되고 있나요?

안녕하세요.

모두들 한 학기 동안 학업에 스터디를 병행하느라 고생 많으셨습니다 👏

지난 미팅때 논의 했던 내용을 간략하게 정리하고 다같이 공유하면 좋을 것 같습니다. 학기 말에 바쁘겠지만 조금의 에너지를 투입해서 정리를 하고 넘어가면 여름방학, 2학기를 보내는데 많은 도움이 될거에요. 6월 30일까지 정리하고 산뜻하게 7월을 맞이하는게 어떨까요?!

스터디 관련해서 매니저분 (@bootkorea, @jys-jeong, @AFpine, @santam) 들께서 주로 정리해주시면 좋을 것 같고요 회장님 (@Sabro98)께서는 좀 더 큰 틀에서 조율을 해주면 좋을 것 같아요. 스터디 참여 했던 멤버 분들도 스터디를 진행하면서 좋았던 점, 힘들었던 점, 개선점 등을 적극적으로 게시해주시면 향후 스터디 계획에 반영에 도움이 될 것 같습니다 (그래야 다음 스터디도 효과적으로 할 수 있고 여러분들의 후배들에게도 도움이 됩니다. ALPS 멤버들은 서로 도움을 받기도 하고 도움을 줄 수도 있는 그런 멤버였으면 좋겠습니다!)

우선 여기 issue에서 안건별로 정리하고 추가적으로 논의가 필요한 부분은 여기에서 같이 논의하면 좋겠습니다. 지난 번에 이야기 나왔던 사항을 안건 단위로 정리해 보았습니다.

1. 2학년 대상 [여름방학 - 2학기] 알고리즘 스터디 계획 (1학기 자료구조 스터디 피드백 반영하여)
2. 신입생 대상 [여름방학 - 2학기] 자료구조 스터디 계획
3. 프로그래밍 대회/해커톤 등 참여 (특히 3/4학년)
4. 저장소를 (매 스터디마다 새로 파지 않고) 지속적으로 운영할 수 있는 방안 생각하기
5. ICPC 대회 준비팀도 정리/공유겸 README 수준으로 공부 자료와 준비 history를 한 번 정리하고 꾸준히 업데이트하는 것은 어떨까요?

@joonas-yoon 선배님께서도 (3번 관련해서) 의견 주면 정말 고맙겠습니다 👏

학생들 스터디 진행 사항을 확인하러 왔는데 현재 저장소에 있는 내용으로는 확인이 쉽지 않네요. 정리가 필요해보이는데 우선 아래 내용을 진행해줄 수 있을까요? @Sabro98

• 레포에 굳이 필요 없는 파일이나 자료는 삭제해주세요.
• 레포 root에는 Coding_Interview, Data_Strcuture, Programming_Contest 폴더로만 구성하고 각 스터디에 맞춰서 자료를 정리하면 좋을 것 같습니다.
• 각 스터디 별로 README를 두고 운영방식, 공부계획, 자료 링크를 포함하여 조원별로 계획 달성 여부나 진도를 쉽게 확인 할 수 있도록 정리해줄 수 있을까요? (각 스터디 매니저가 봉사해주면 고맙겠습니다).

5214번 환승

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

질문

틀린 코드에서 어떤 케이스가 만족하지 않은지 또는 맞은 코드와 차이점이 뭔지 알고 싶습니다.

틀린 코드

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
vector<int> adj[100000 + 1000 +1];
int dist[100000 + 1000 + 1];
int arr[1001];
int n, k, m;
int bfs(int cur) {
	dist[cur] = 1;
	q.push(cur);
	while (!q.empty()) {
		cur = q.front(); q.pop();
		
		for (auto nxt : adj[cur]) {
			if (dist[nxt] > -1) continue;
			q.push(nxt);
			if (nxt > 100000)
				dist[nxt] = dist[cur];
			else
				dist[nxt] = dist[cur] + 1;
			if (nxt == n) return dist[nxt];  // 맞은 코드와 다른 부분
			
		}
	}
	return -1;
}

int main(void) {
	
	cin >> n >> k >> m;
	int idx = 1;

	while (m--) {
		for (int i = 0; i < k; i++) {
			cin >> arr[i];
		}
		for (int i = 0; i < k; i++) {
			adj[arr[i]].push_back(100000 + idx);
			adj[100000 + idx].push_back(arr[i]);
		}
		idx++;
	}
	fill(dist, dist + 100000 + 1000 + 1, -1);
	cout << bfs(1) << '\n';
	

}

맞은 코드

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
vector<int> adj[100000 + 1000 +1];
int dist[100000 + 1000 + 1];
int arr[1001];
int n, k, m;
int bfs(int cur) {
	dist[cur] = 1;
	q.push(cur);
	while (!q.empty()) {
		cur = q.front(); q.pop();
		if (cur == n) return dist[cur]; // 틀린 코드와 다른 부분
		for (auto nxt : adj[cur]) {
			if (dist[nxt] > -1) continue;
			q.push(nxt);
			if (nxt > 100000)
				dist[nxt] = dist[cur];
			else
				dist[nxt] = dist[cur] + 1;
			
		}
	}
	return -1;
}

int main(void) {
	
	cin >> n >> k >> m;
	int idx = 1;

	while (m--) {
		for (int i = 0; i < k; i++) {
			cin >> arr[i];
		}
		for (int i = 0; i < k; i++) {
			adj[arr[i]].push_back(100000 + idx);
			adj[100000 + idx].push_back(arr[i]);
		}
		idx++;
	}
	fill(dist, dist + 100000 + 1000 + 1, -1);
	cout << bfs(1) << '\n';
	

}

효율적인 스터디 진행을 위해 필요한 내용을 조사하겠습니다.

5/10 18:00까지 풀어보면서, 본인이 생각하기에 아래 조건에 해당하는 문제를 올려주시면 되겠습니다.

스터디 진행 중 공지한대로

해결하였지만, 어려움을 겪었던 문제
끝까지 해결하지 못하여 그룹원과 토의하고 싶은 문제
이외 스터디 시간에 다루면 좋을 것이라 여겨지는 문제

를 댓글로 남겨주시면 됩니다.

댓글로 남겨진 문제는 스터디 시간에 필수적으로 다루어지므로 가능하다면 무조건 해결하는 편을 권장합니다.

@alphasobs @tjdeo1102 @zs0057 @vuswltmd @JC-arl