직사각형 && 약 팔기 직사각형 약 팔기 문제 풀이 날먹문제집? 시리즈에 있어서 넌센스 겸으로 풀어봤다. 애드 훅이지만 다행히도 풀이가 간단하게 생각나서 쉽게 푼 것 같다. 이제 붙어 있는 값을 더해서 1~1000000 까지의 숫자를 만들 수 있으면 된다. 처음에는 2진수로 1 2 4 1 2 4 8 … 이런식으로 하면 되지 않...

빙고 빙고 문제 구데기컵에 나온 빙고를 푸는 문제이다. 풀이 재밌어 보이고 티어도 높아서 1시간 동안 열심히 풀었는데 점수를 안 준다고 한다. ㅠ 그래도 푸는 과정이 퍼즐 푸는 것 같아서 재밌었다. 우선 C3는 반드시 참이다. 색칠되지 않으면 모순이 생기기 때문이다. B1이 참이 아니라면 빙고줄의 일부지만 체크가 되면 안되므로 모순이 ...

학부 연구생 민상 새벽까지 계속 고치고 고쳐봐도 문제가 풀리지 않는다. 문제는 빡구현이라고 할 수 있는 귀찮은 dfs? 문제라고 생각했고 어쨌든 구현은 다 했다. 그런데 59%에서 시간 초과도 아니고 자꾸 메모리 초과가 발생한다. 처음에는 배열 index를 넘어간다거나 그런게 있나? 하고 찾아봤는데 아무것도 없다. 문제 제한을 봐도 메모리 ...

백준 문제를 푸는데, 분명 로직이 맞는 것 같은데 안되는 경우가 있다. int ma=-1; for(int i=1;i<=n;i++){ if(ma < graph[i].size()){ ma = graph[i].size(); save = i; } } 이런 코드...

경비병 세우기 게임 경비병 세우기 게임 문제 Yuto 와 Platina가 보초 세우기 게임이라는 새로운 게임을 해보려고 한다. 이 게임은 N × M의 가로가 긴 격자판에서 진행된다. 게임은 항상 Yuto부터 시작하며, 둘은 번갈아 가면서 자신의 턴에 원하는 빈 위치에 경비병을 세운다. 이 게임에서 ‘안전상태’라는 것은 격자판 안에 완벽히 포함되는...

최솟값 찾기 최솟값 찾기 문제 N개의 수 A1, A2, …, AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N...

소트 소트 문제 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. N개의 수는 1,000보...

동전 뒤집기 동전 뒤집기 풀이 비트 마스킹 문제인데 아직 어색하다. 우선 아이디어 1. 같은 자리를 두 번 이상 뒤집는 것은 아무런 의미가 없다. 그렇기에 모든 가로에 대해 뒤집는 경우 2^20을 해보고, 세로에 대해 그리디하게 뒤집으면 된다. 그러면 시간 복잡도는 2^n * n^2이니까 충분히 해결이 가능하다. 계속 시간 초과가 나서 다...

절망적인 줄 절망적인 줄 문제 해빈시의 공원에는 화장실이 두 개가 있다. 그런데 그 중 하나가 얼마전에 고장났다. 이제 남은 건 한 개 뿐이다…. 문제는 해빈이는 당장 화장실이 가고 싶은데, 화장실 앞의 줄이 매우 길다는 것이다! 고통을 잊기 위해 해빈이는 절망적인 줄을 쳐다보며 아래와 같은 문제를 풀기 시작했다. 화장실 사용료는 50원이다....

냅색 문제 냅색 문제 문제 세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 ...

**팰린드롬 인코딩 ** 팰린드롬 인코딩 문제 준규는 심심해서 팰린드롬 인코딩이라는 새로운 인코딩 방법을 만들었다. 팰린드롬 인코딩은 0과 1로만 이루어진 자료만 인코딩 할 수 있으며, 다음과 같은 과정을 거친다. 문자열 S에서 짝수 길이인 팰린드롬 연속 부분 문자열을 찾는다. 팰린드롬은 앞에서부터 읽을 때와 뒤에서부터 읽을때가 똑같은 문자열...

보이는 산맥 보이는 산맥 문제 맑은 날 울릉도에서 태백산맥을 바라보면 수평선 위로 N개의 산봉우리가(1 ≤ N ≤ 100,000) 보인다. 다음은 N = 5인 경우의 예이다. /\ /\ / \ /\ / \/\ /\/ \/ \ / \ \ / \ / \ ---...

최대공약수 하나 빼기 최대공약수 하나 빼기 문제 정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다. 최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다. N개의 정수 중에서 임의의 수 K를 뺐을...

별 찍기 시리즈 별 찍기 시리즈

차원의 나무 여행 차원의 나무 문제 정점의 개수가 N, 간선의 개수가 N-1인 트리가 주어진다. 간선으로 직접 연결되지 않은 정점으로 이동하는 것을 워프라고 한다. 각 정점을 최대 한 번만 방문할 수 있을 때, 가능한 워프의 최대 횟수를 구하여라. 시작 정점은 임의로 고를 수 있으며, 시작 정점을 고르는 것도 워프이다. 입력 첫 번째 줄에 N이 ...

Consonants (Large) Consonants (Large) 마라톤에 나와 푼 영어 문제라 눈에 안 들어온다.. 코드 잼 2013년 문젠데 이게 왜 골드 5지.. 생각하기 어려운 애드 훅 같은데 문제는 이런 입력에서 예제 입력 1 4 quartz 3 straight 3 gcj 2 tsetse 2 예제 출력 1 Case #1: 4 Ca...

풍선 풍선 문제 전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다. 풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 각 팀에게 달아줘야 하는 풍선의 수와 방 A와 ...

호반우가 학교에 지각한 이유 2 호반우가 학교에 지각한 이유 2 문제 이세계를 모험할 때는 무기가 필요한 법이기에 호반우는 현재 신에게 받은 소수소수검의 사용법을 익히고 있다. 소수소수검을 사용하기 위해서는 검이 제시하는 두 자릿수의 소수 A,B와 양의 정수 N을 이용해 소수소수를 만들어야 한다. 소수소수란 해당 수 자체가 소수일 필요는 없지만...

곱셈 곱셈 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나...

좌표 압축 좌표 압축 문제 수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자. 입력 ...

회의실 배정 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과...

평범한 배낭 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치...

시간복잡도 시간 복잡도란 특정한 크기의 입력에 대해 알고리즘의 수행 시간을 평가한다. 알고리즘 문제를 풀다보면 입력의 크기에 따라 시간을 어느정도 계산할 필요가 생긴다. 입력 데이터가 최선의 경우, 평균적인 경우, 최악의 경우에 따라 시간 복잡도를 나누게 되고 문제에서는 보통 최악의 경우로 알고리즘의 성능을 파악한다. 최선의 경우는 빅 오메가 표...

algorithm 시작 방학 목표가 백준 플레 + 코드포스 블루까지 가는 것이었는데 자꾸 안하게 된다. 코드포스는 2학기 기말 전까지 열심히 해서 민트 단 다음에 그 뒤로 안하고 있고 백준도 스트릭은 계속 잇고 있긴한데 많이 풀고 있진 않다. 티어작을 하려면 금방 올리겠지만 그것보단 다양하게 공부하고 싶다. 그래서 자료구조, 알고리즘 개...

블로그 계획 사실 C언어 정리를 1월 초~중이면 끝낼 줄 알았는데 생각보다 늦어졌다. 알고리즘도 정리해야 하고, 문제 푸는 것도 정리를 시작해야겠다. 주 공부는 보안이었으면 좋겠는데, CTF랑 개념 정리한 것도 만들어아 하고 학교 공부나 추가로 CS 공부한 것도 만들어야겠고, 언어도 시간이 되면 조금씩 해야겠다. 일단 하나씩 꾸준하게 쓰는 것을...

C언어 (26) visual studio visual studio 오류랑 편리하게 쓸 수 있는 디버깅 모드들 오류 모음 #_CRT_SECURE… visual studio만의 오류?라고 볼 수도 있는 오류이다. scanf뿐만 아니라 입출력, string 관련 함수에서도 다 이런 에러를 낸다. 실제로 이 함수들이 버퍼 오버플로우 및 기타 ...

C언어 (25) 조건부, 분할 컴파일 마지막으로 조건부, 분할 컴파일에 대한 내용이다. 이론적이라기 보다는 컴파일 방법에 대한 내용이니 간단히 적어도 될 것 같다. 조건부 컴파일 C언어는 다양한 OS에서 사용되었기에 제공하는 표준 함수나 동작이 조금씩 다를 수 있다. 같은 운영체제를 사용한다 하더라도 사용하는 컴파일러와 라이브러리가 다를 수도...

C언어 (24) 매크로와 인라인 함수 C언어 책 마지막엔 전처리기와 분할 컴파일에 대한 이야기가 있다. 사실 잘 안쓰는 잡다한 내용이라 여기까지 진도도 안나가고 안 읽어봐서 처음 보는 내용이었다. 이번에 싹 정리하는 겸 다 내용을 알아보자. 전처리기 전처리는 본격적으로 소스 파일을 컴파일 하기 전에 먼저 처리해야 하는 일이다. 코드의 가장 위...

C언어 (23) 동적 메모리 할당2 지난번에 안본 realloc과 free를 보고, 동적 메모리를 끝내자. 동적 메모리 할당 함수 함수명 설명 반환 값 malloc(size) 지정된 크기만큼 메모리를 할당하며 초기화되지 않은 메모리를 반환. ...

C언어 (22) 동적 메모리 할당 프로그램에서 사용되는 메모리는 정적 메모리와 동적 메모리가 있다. 우리가 선언하던 일반 배열들은 컴파일 할 때 메모리의 크기가 정해진다. 이런 정적 메모리는 프로그램을 실행하면서 메모리의 크기를 변경하는 것이 불가능하다. 이 문제점을 해결 하기 위해서 동적으로 메모리를 할당하고 해제하는 작업이 필요하다. 프...

C언어 (21) 파일 입출력2 stream이란 무엇인지, 파일을 어떻게 여는지 알았으니 이제 입출력 함수를 사용해본다. 표준 파일 입출력 함수 표준 파일 입출력 함수는 이렇게 입출력 스트림을 정해서 원하는 입력 방법을 선택할 수 있다. 함수들을 하나씩 사용하면서 기능을 정리해보자. 문자 단위 표준 파일 입출력 함수 fgetc(), fpu...

C언어 (20) 파일 입출력 프로그램은 파일을 통해 데이터를 받거나 쓰는 경우가 많다. 이런 동작을 C언어로 해보자. 스트림(stream) 스트림(stream)이란 데이터를 입력하고 출력하기 위한 다리 같은 역할이다. 키보드, 모니터 같은 입출력 장치들은 다양한 방식으로 데이터를 주고받는다. 이 키보드와 프로그램, 프로그래뫄 모니터를 이어 ...

C언어 (19) 문자열 이용하기 지난번에 문자열의 입출력 함수에 대해 자세히 알아봤다. 이제 문자열을 처리하는 함수와 포인터로 문자열을 사용해보자. 문자열 처리 함수 문자열을 프로그램에서 사용하다보면 문자열을 붙이거나, 길이를 구하거나, 비교하는 작업이 필요하다. 직접 함수로 작성해도 되지만 C에서는 이런 역할을 하는 여러 함수를 라이브러리로...

C언어 (18) 문자열 C언어에서의 문자열은 상당히 복잡하고 신경 쓸 것이 많다. 그래서 python을 먼저 배우고 C언어를 배울 때 제일 헷갈려하는게 이 문자열 부분인 것 같다. 또 python이나 C++ string STL을 사용하면 문자열 다루기가 굉장히 편하다. 그럼에도 C언어로 문자열을 사용해야 하는 일이 있을 수도 있고, 여러 함...

C언어 (17) 구조체와 공용체3 함수에 구조체를 이용하는 방법과 공용체, 열거형을 보자 . 구조체와 함수 구조체를 함수로 사용하는 경우는 두 가지가 있다. 구조체를 함수의 인자로 전달하기 구조체를 함수의 반환형으로 전달하기 인자로 사용할 때도 값으로 전달하는 방법과 주소로 전달하는 방법이 있다. #include <stdio...

C언어 (16) 구조체와 공용체2 구조체에서 배열과 포인터를 어떻게 쓰는지 자세히 보자. 구조체의 메모리 저장 방법 구조체가 메모리에 저장되는 방식은 그림과 같다. 각각의 멤버 변수는 시작 주소부터 연속되어 저장을 한다. 크기는 구조체의 멤버 중 가장 큰 멤버의 자료형에 영향을 받는다. 예시로 확인을 해보자. typedef s...

C언어 (15) 구조체와 공용체 새로운 자료 구조인 구조체와 공용체, 열거형까지 알아보자. 구조체 배열이 타입이 같은 데이터를 하나로 묶는다면 구조체는 타입이 다른 데이터도 묶을 수 있다. 학생의 정보를 저장한다고 할 때 이름, 나이, 점수를 하나로 묶어 저장할 수 있으면 편할 것이다. 이런 여러개의 변수를 그룹화하여 새로운 자료형으로 만...

C언어 (14-2) 함수와 포인터 ex 책에는 있는데 알면 좋고 중요한 것도 맞긴 한데 이해하기 어렵기도 하고 C언어를 배우는 과정에서 꼭 알아야하는 건 아닌 것 같아서 간단히 정리만 했다. main() 함수에 인자를 넣을 수 있다? 여태까지 본 main() 함수는 인자가 없는 main(void) 형태였다. 그런데 다른 형태의 main()함수...

함수는 어떻게 저장되는가? 함수 포인터를 알아보다 작은 궁금증이 생겨서 찾아보고 정리해봤다. 다시 생각하보니 간단한 것이었는데 알아보면서 재밌었으니까~ 함수는 어떻게 메모리에 저장되는가? 함수의 포인터는 함수의 원형과 거의 비슷하게 생겼다. int (*pointer) (int, int) 변수의 포인터는 int*, double* 등으로 참조하...

C언어 (14) 함수와 포인터 여태까지 배운 것을 합쳐서 함수에서 어떻게 포인터를 활용하는지 알아보자. call by value vs call by reference 값에 의한 호출(call by value)은 변수의 값을 복사해서 함수를 호출하는 방식이다. #include <stdio.h> int func(int n); int m...

C언어 (13) 함수2 함수의 선언 방법을 알아보았고, 어떻게 사용하는지 좀 더 알아보자. 또 변수의 선언 위치에 따른 차이점과 종류를 알아보자. 변수의 종류와 범위 변수는 선언되는 위치나 종류에 따라 메모리 상에 존재하는 기간이 다르다. 지역 변수 전역 변수 정적 변수 외부 변수 레지스터 변수 이렇게 5가지로 나눌 수...

C언어 (12) 함수 책을 보면 함수를 간단하게 소개하고, 그 다음이 배열, 포인터 순서로 하는 것이 대부분이다. 하지만 포인터, 포인터-배열 관계, 함수, 포인터-함수 관계로 잇고 싶어서 순서를 조금 꼬았다. 흐름만 이해하면 함수는 쉽게 이해하는 것 같다. 함수 수학에서 함수란 어떤 x를 넣었을 때 y라는 값을 내는 f(x)같은 것이다....

C언어 (11) 포인터와 배열2 포인터와 배열의 관계를 이어서 더 보자. 포인터 변수를 통한 1차원 배열 접근 배열의 이름은 배열의 시작 주소와 같다고 했다. 그리고 배열의 주소에 +1, +2를 하면 주소는 배열의 요소 크기만큼 증가한다. #include <stdio.h> int main() { int arr[5] = { 1...

C언어 (10) 포인터와 배열 포인터에 대해 간단히 보았는데, 활용에 대해서는 아직 잘 모르겠다. 포인터의 특성을 좀 더 보고, 배열과 연관지어 보며 어떻게 사용하는지 알아보자. 다중 포인터 int** ppnum; 이런 포인터는 존재할 수 있을까? 포인터 변수도 주소를 가지고, 8바이트 또는 4바이트의 크기를 가진 변수이다. 그렇다면 포인터...

C언어 (9) 포인터 C언어에서 가장 중요하고 이해하기 어려운 개념으로 꼽히는 것이 포인터일 것이다. 변수와 배열 이야기를 하며 계속 주소를 언급했는데, 이 주소를 어떻게 쓸 수 있는가?에 대한 이야기다. 중학생 때 처음 C언어를 학원에서 배웠었는데 포인터는 어려우니까 넘어가자~라고 말했었다. 지금 생각해보면 이해가 안되는 말인 것이 포인터...

C언어 (8) 배열 학교의 모든 학생의 성적을 변수에 저장하고 싶은데 각각 변수를 생성하면 변수의 개수가 너무 많아진다. 이 때 같은 자료형을 가진 변수를 묶어 배열이라는 자료구조로 처리할 수 있다. 배열 변수란 우리가 프로그램을 작성할 때 숫자나 문자 같은 데이터를 저장하기 위한 공간이다. 변수는 저장되는 주소가 있고, 공간이 있다. 배...

switch case의 작동 방식 호기심 탐구라는 탭은 공부하면서 갑자기 궁금했던 것을 좀 깊게 알아보려고 만들었다. if-else와 switch-case의 차이를 알아보면서 생긴 궁금증인 switch-case의 특징에 대해 더 알아보자. switch-case란 가나다라 abcd

C언어 (7) 반복문 반복문이랑 동일한 문장을 여러 번 반복하는 구조이다. 동일한 작업을 계속해야 한다면 똑같은 문장을 crtl+c, crtl+v하는 것보다 반복문을 사용하는 편이 좋다. 반복문 노트북을 구매하기 위해 월급을 받아 저축하는 사람의 경우를 프로그램으로 만들어보자. 저축한 돈이 240만원 이상이 될때까지 아르바이트를 하고, 이...

C언어 (6) 조건문 프로그램은 사용자의 선택에 의해 동작해야 한다. 입력이나 신호에 따라 변화하는 프로그램을 만들기 위해 조건문을 알아야 한다. 조건문 자판기 내부의 과정을 간단하게 도식화해서 보면 이런 동작들이 있을 것이다. 이 때 마름모안에 들어있는 문장들을 조건문이라고 부르고, 문장의 참, 거짓에 따라 동작이 바뀐다. 여태까지 ma...

C언어 (5) 연산자 컴퓨터의 연산이란 사칙연산을 포함해 대입, 지수, 조건 등이 있다. 상황에 맞는 연산을 할 수 있도록 연산자를 알고 있어야한다. 분류 연산자 설명 대입 연산자 = 대입 산술 연산자 ...

C언어 (4) 자료형2 정수형 변수에 이어 실수형 변수를 알아보자. 자료형 변환에 대해서도 알아보자. 자료형 키워드 바이트 수 범위 정수형 short 2 -32,768 ~ 32,767 ...

C언어 (3) 자료형 변수를 선언할 때 어떤 자료형을 받을지 앞에 적어줘야 한다. 자료형이란 뭘까? 이 자료형에 따라 메모리에 어떻게 값이 저장되는지 자세히 알아보자. 자료형 데이터는 정수형, 실수형, 문자형과 같이 다양한 type을 가진다. 이 type이 자료형이다. 나누는 기준은 변수 앞에 붙여진 int, double 등의 키워드를 보고 ...

C언어 (2) 변수와 상수 프로그램은 사용자에게 입력을 받고 그에 따라 다른 값을 내놓는다. 상수와 값을 저장하는 공간인 변수의 차이를 알아보고 입력 함수 scanf를 써보자. 변수 변수란 우리가 프로그램을 작성할 때 숫자나 문자 같은 데이터를 저장하기 위한 공간이다. #include <stdio.h> int main() { ...

C언어 (1) 기초 사항 비주얼 스튜디오를 설치하고 이제 프로그램을 직접 만들어 본다. 문장, 주석, 함수, 출력 함수를 본다. 입출력 방법 #include<stdio.h> /*주석*/ int main(void){ printf("Hello World!"); //hello world! return 0; } 위의 코...

C언어 (0) 개요 공부한 것을 적으려고 만든 블로그인데 어떻게 시작할지 모르겠다. 일단 컴공의 시작은 C언어! 같은 느낌이니까 c언어 정리로 시작하자 코딩 학원 강사로 일한지가 24년 1월 말부터니까 거의 1년이 되어간다. 수업을 하며 이건 알았으면 좋겠다거나 많이 실수하는 것도 적어야겠다. 수업 자료처럼 쓰기 위해서.. 책은 C언어 콘서...

마크다운 문법 정리 github.io를 처음 만들고 마크다운으로 글을 쓰는 것이 처음이라 한 번 정리하고 노트처럼 쓰기 위해 작성합니다. 1. 제목 (Headers) 제목을 표시할 때는 #을 사용하고. #의 개수에 따라 제목의 레벨이 된다. # 제목 1 ## 제목 2 ### 제목 3 #### 제목 4 2. 강조 (Emphasis) 텍스트...