g1embed

네트워크에 연결된 컴퓨터 중, 1번 컴퓨터로 인해 바이러스가 전파된 컴퓨터의 수를 구하는 문제입니다. 유의할 점은 데이터를 받으며 그래프 정보를 입력 시 양방향으로 입력해주는 것과, Queue에 Push할 때 방문처리를 해주는 것입니다. 1. 그래프 입력 2. 시작 노드 Push 후 방문처리 3. BFS : 2차원 배열 BFS와는 다르게 갈 수 있는 방향이 그래프에 연결되 노드의 개수만큼 있습니다. 방문 후 Push 될 경우 감염된 컴퓨터의 수를 증가시키며, 1번 컴퓨터는 세지 않기 때문에 0부터 시작합니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; queue q; vector com[1..

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - 버튼을 이용해 특정 채널로 이동하려고 할 때 망가지지 않은 버튼을 이용해 이동하려면 최소 몇 번 버튼을 눌러야 하는지 계산하는 문제입니다. 유의해야 할 점은, 목표 채널로 이동하기 위해 숫자를 누르지 않는 것이 빠를 수 있다는 점입니다. 또한, 목표채널 N이 어디에 존재할 지 모르므로 뺄셈 연산 후 절대값을 취해줘야 함을 잊지 말아야 합니다. 1. 모든 번호를 Brute Force 로 탐색(0 에서 500000까지의 N 이 존재하지만, 이동할 수 있는 채널의 제한은 없으므로 1000000 까지의 채널을 탐색하도록 합니다. 망가진 버튼이 무엇인가에 따라 N 범위를 벗어난 채널에서 이동하는 것이 더 빠를 수 있습니다. 2. 고른 채널을 숫자를 눌..

부등호를 입력받으면 그 사이에 들어갈 수들을 붙여놓은 것 중 가장 큰 수와 작은 수를 찾아내는 문제입니다. 처음에 접근한 방식은 모든 경우의 수를 찾고 부등호에 대한 조건은 모든 수를 선택한 후에 알아보도록 하는 것이었습니다. 보통 재귀를 설계하는 방식처럼 final condition을 먼저 명시하였고, 이후에는 0에서 9까지의 반복문 안에서 check 배열을 넣었다가 풀며 재귀를 돌렸습니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include /* 부등호 */ using namespace std; char a[15], check[15]; int k; vector ans; string to_string(int i) { char j = i + '0'; ..

완전탐색 대신 투포인터 (two pointers) 알고리즘 활용 입력: N: 데이터 수 M: 구간의 합과 비교해볼 값 ㅁㅁㅁㅁㅁ: N개의 데이터 각 'ㅁ' 마다 데이터가 들어오는 칸이라고 생각하면, 들어온 값들의 합이 M과 일치할 수 있는 '경우의 수'를 구해야 합니다. ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ 위 예시와 같이 밑줄친 곳과 중앙선이 그어진 곳 모두 합이 M과 일치할 수 있습니다. 시간복잡도를 낮추기 위해 두 개의 포인터를 활용해 front 와 back의 위치에 대해 알고 있도록 합니다. 주의할 점은, 합이 M 보다 클 때 front에 해당하는 값을 한 번 지워서는 M과 일치할 수도 있는 합을 놓칠수도 있다는 것입니다. 이 부분은 테스트케이스에 나와있지 않아 틀리기 쉽습니다. #include /* 수들의 합..

복습한다는 개념으로 볼 수 있게 필요한 개념을 정리하였습니다. Integer Types char short int int long int long long int Pointers 변수 이름은 특정 데이터 타입을 가진 주소로 가기 위한 인덱스로 사용됩니다. 포인터는 값을 직접 가지지는 않으나 값을 지칭합니다. 또한, 포인터는 strongly typed 로서 컴파일러가 포인터를 int, char 등의 자료형과 연관시킵니다. 임베디드 개발 시 struct data를 넘겨줄 때 데이터 전체를 넘기기에 부담이 되니 포인터를 넘겨주는 작업을 자주 하곤 합니다. #include int main() { int y = 42; int *ip = &y; printf("The value of y is %d\n", y); pr..

자주 쓰는 기능이 있다면 함수로 만들어 모듈화를 해야 한다. 이 것이 간결하고 유지보수가 쉬운 프로그램을 만들기 위한 가장 첫 번째 단계이다. 함수를 만든다는 것은 여러 명령들의 집합을 만들어 묶는 것과 같다. 수학에서의 함수를 생각하면 쉽다. 아래와 같이 함수에 인풋을 전달하면 정해놓은 지시대로 인풋의 데이터를 처리해 아웃풋을 낸다. Input -----(함수 안에 프로그래머가 정의한 지시들) ----> Ouput 나중에 나아가서 프로그램을 짜는 것에 능숙해진다는 것은, 함수와 클래스를 어떻게 짤 것인지, 즉 아키텍쳐를 빨리 생각해내는 능력이라고 한다. 그 단계까지 최대한 빨리 갈 수 있도록 얼른 공부해야겠다! 주의할 것들 함수는 단 하나의 기능을 수행하도록 하는 것이 좋다. 함수를 호출하면 CPU 사..

조금 더 자세히 들어가 왜 타입 캐스팅을 잘못하면 오버플로우가 나는지에 대해 알아보도록 한다. 먼저, 이진법에서 음수를 어떻게 활용하는지를 파악하는 것이 중요하다. 2진법에서는 음수를 표현하기 위해 '보수' (complement)의 개념을 활용한다. Most Significant Bit (가장 왼쪽에 있는 비트)가 부호를 나타내기 위한 비트이다. 5 00000101 Signed Magnitude 10000101 +0 과 -0 존재 10000000 00000000 1's Complement 1의 보수 11111010 +0과 -0 존재 11111111 00000000 2's Complement 2의 보수 11111011 Unique Value of 0 2의 보수의 표현범위는 다음과 같다 8비트 : -128 ..

형변환은 (type_name) expression 으로 가능하다. 예를 들어 원의 체적을 구하는 식을 계산하려 할 때 (int) 4/3 * PI * r * r * r 에서는 (int)가 type_name 이고 나머지가 expression 이다. 위 그림은 형 변환을 할 때의 서열이라고 생각하면 된다. int형과 float형을 계산한다면 float 형으로 결과가 저장되는 방식이다. float 나 double 에서 int 형으로 변환 할 때에는 소수점 밑 숫자들이 모두 내림처리된다. (반올림되지 않음) 예제를 보며 이해하는 편이 빠르다. 여담이지만 scanf 함수 쓸 때, 두 번째 parameter에 &를 넣지 않는 실수를 자주 한다. 그러고서 형변환 에 문제가 있나?? 하고 한참 삽질하기 전에 꼭 확인해야..

단일 연결리스트는 인덱스를 이용한 참조는 힘들지만 데이터 삽입과 제거가 용이하다. 다음과 같은 구조를 가지고 있다. 1. 먼저 typedef struct를 이용해 구조체를 만들어 줌 2. 구조체에는 int/float/double/char 등등 의 데이터 부분과 Node 포인터인 next 가 만들어져야 한다. 3. Alias는 Node로 설정. 4. 전역에서 head 노드 포인터 변수를 만들어 준다. head는 자료의 시작지점이라고 생각하면 된다. - 전역에서 만들어주는 이유는 추후 함수형으로 프로그래밍을 할 때, 함수로 찾기 편하게 하기 위해서이다. 5. main 함수에서 head를 동적할당 시켜준다.. 6. node1을 동적할당 합니다. node1의 데이터에 들어가는 값은 1로 한다. node2도 동적..

배열(Array)는 자료를 나열하고 접근할 때 아주 편리. 배열의 장점: 1) 특정한 원소로 즉시 접근할 수 있음 하지만 자료가 100000개 정도 있고, 2번째 요소를 지우고자 한다면 뒤에 있는 99998개의 요소를 한 칸 앞으로 덮어쓰기 해 주어야만 한다. 또 맨 앞에 요소를 추가할 때는 배열을 모두 한 칸씩 뒤로 미룬 다음 배열의 0번째 인덱스에 값을 입력한다. 코드상으로는 이렇게 표현할 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #define INF 10000 int arr[INF]; int count = 0; void addBack(int data) { arr[count] = data; count++; } void addFirst(int data) { f..