본문 바로가기

프로그래밍

 (61)
문제해결기법 조교를 하며 이번에 과제로 https://www.acmicpc.net/problem/11048해당 문제와 비슷한 문제가 나왔다, 차이가 있다면 최대가 아니라 최소라는 것 그래서 해당 문제에서 유의해야할 것은 두 가지 있다. 위 문제에서는 r+1,c+1을 이용할 필요가 전혀 없다. 음수인 값도 없기 때문에 r+1 -> c+1이나 c+1 -> r+1을 해서 손해를 볼 일이 없기 때문이다. 최소가 되도록 하기 위해서는 r+1과 c+1도 의미가 있다. 사실상 백준의 저 문제에서도 구현에서 r+1,c+1을 포함해도 문제가 없기 때문에 과제로 나온 문제에서 문제가 발생한 사람은 없었다. 다른 하나는 dp를 이용해 이 문제를 해결한다면 테두리의 값을 신경써야 한다. 보통 dp 테이블을 만들 때 n+1, m+1로 제작을 하는데 이..
[파이썬 문법] 나는 재귀를 안 썼는데 왜 recursionError가? 최근 백준 문제를 풀다가 좀 편하게 짜려고 이상한 코드를 하나 짰었다.백준 게시판에 질문도 했었는데 아무도 답이 없었고, 이상한 짓이 굉장히 하고싶어지는 시험기간의 영향으로 해결하게 된 문제이다. 문제는 요약하면 문자열 여러개가 주어지고 배치되는 순서가 주어지면 그거에 맞춰서 문자열을 배치하면 되는 문제이다. n이 50만이나 되고, 문자열 길이의 총합도 50만까지 가능하다. 따라서 일반적으로 문자열을 합치는 방식으로 풀게된다면 시간 초과가 나게 된다. 그 이유는 파이썬 문자열 연산은 최종적으로 완성되는 문자의 길이만큼의 시간이 소요된다. 조금 깊게 가보면 파이썬 문자열은 "불변성"을 갖고, 뒤에 추가되는 것이 아닌 불변하는 여러개의 문자열에서 문자를 긁어와 새로운 문자열을 만드는 것이기 때문이다.a라는 ..
백준 9663 NQueen 파이썬으로 다양하게 풀어보기 1년에 한두번씩은 꼭 푸는 것 같은 NQueen 문제, 옛날 풀이부터 차근차근 한번 되짚어 보자, 기본적인 틀은 다 같다. 백트래킹을 사용하며, 한 행을 기준으로 백트래킹을 진행하며, 가능한 위치를 찾아 퀸을 배치한다. 0. 배치할 수 있는지 8방향 탐색해서 판별하는 경우배열에 퀸을 놓고, 현재 놓을 위치 기반으로 8방향을 탐색해서(6방향만 탐색해도 문제 없다, 왜냐하면 한 행에는 하나의 퀸만 놓을 수 있기 때문에) 퀸이 존재한다면 불가능할 것이고, 퀸이 존재하지 않는다면 가능할 것이다.노란색이 이미 배치된 퀸이고, 주황색에 배치가능한지 판별하려 했을 때 저 8방향을 모두 탐색해서 다른 퀸이 존재하는지 아닌지 판별한다.존재한다면 넘어갈 것이고, 존재하지 않는다면 배치할 것이다.불필요한 탐색이 굉장히 많다..
[백준/C++] 10216, 12004 10216 Count Circle Groups 문제난이도 : G4 알고리즘 : 분리집합  풀이좌표 x,y와 반지름 R이 주어진다. 원이 겹치는 부분끼리 그룹을 지어주고 최종적으로 남은 그룹의 개수를 출력해주면 된다.float를 최대한 피하는게 좋으므로 거리를 구할때 x1,y1,r1과 x2,y2,r2가 있을 때 (x1-x2)^2+(y1-y2)^2와 (r1+r2)^2를 비교해주면 된다. #include #include #include #include using namespace std;int par[3001];int find(int x){ if (x == par[x]) return x; par[x] = find(par[x]); return par[x];}void uni(int a,int b){ a = fin..
[코테 유형별로 씹어먹기] BFS 어떤 문제에 사용될까? 개념 트리나 그래프, 혹은 다른 것들에 대해 탐색을 진행할때 사용하는 방법들이 BFS와 DFS이다. BFS는 한칸씩 이동, DFS는 한쪽으로 이동 대략적으로 이렇게 이해하고 가면 된다. 코테나 대회에서 그래프/트리 문제나 BFS DFS를 응용한 문제들은 꼭 하나씩은 봤던 것 같다. 구현# 크기가 N*M인 2차원 행렬 탐색 (가로 M, 세로 N)from collections import dequedx=[1,-1,0,0]dy=[0,0,-1,1]def bfs(X,Y): vi=[[0]*M for i in range(N)] queue=deque([(X,Y)]) vi[Y][X]=1 while queue: x,y=queue.popleft() for i in range(n): ..
[코테 유형별로 씹어먹기]우선순위 큐 어떤 문제에 사용될까? 개념우선순위 큐는 항상 최소 / 최대 값이 가장 맨 앞에 오도록 하는 자료구조이다.우선순위 큐의 내부는 힙이라는 자료구조로, 완전 이진 트리의 일종이다.그에 따라 우선순위 큐에서 값의 삭제 및 삽입의 시간 복잡도가 LogN이다. 그럼 PS에서 우선순위 큐가 필요한 경우에 대해서 생각해보자,자료구조의 특성을 생각해보면 우선순위 큐가 필요한 상황은 값의 삽입과 삭제가 빈번하게 일어나는 경우이다. 예시만약 10만개의 원소가 있는 배열에서 아래와 같은 문제들을 푼다고 해보자. 1. 원소의 삽입 연산만 10만번 혹은 가장 작은/큰 값 삭제 연산만 10만번 주어진다. 연산 후의 가장 작은 값/ 가장 큰 값을 출력해라 만약 삽입만 일어나거나 삭제만 일어나는 경우에는 가장 작은 값, 가장 큰 값만 알고 있으면 된다. ..
[TOPCIT Essence] 02 소프트웨어 개발 방법론 소프트웨어 개발 방법론의 특징은 개발 단계를 각각 정의하고 각 단계별 수행활동, 산출물, 검증절차, 완료 기준을 정의하고, 개발 계획, 분석, 설계 및 구현 단계에 대해 정형화된 방법과 절차, 지원 도구를 정의한다. 소프트웨어 개발 방법론의 필요성1. 개발 경험의 축적 및 재활용을 통한 개발 생산성을 향상2. 효과적인 프로젝트 관리3. 공식 절차와 산출물을 제시하고 표준용어 통일하여 의사소통 수단 제공4. 각 단계별 검증과 승인된 종료를 통해 일정 수준의 품질 보증 소프트웨어 개발 방법론 비교구분구조적 방법론정보공학 방법론객체 지향 방법론CBD 방법개요업무 활동 중심의 방법론데이터 중심의 방법론객체, 클래스 간의 관계를 식별하여 설계 모델로 변환하는 방법론재사용이 가능한 컴포넌트의 개발/상용 컴포넌트를 ..
[TOPCIT Essence] 01 소프트웨어 공학의 배경과 목적 5/18일 TOPCIT까지 2주간 달리기 시작 1) 소프트웨어 공학이란?다기능화 및 대규모화 된 소프트웨어 개발을 위해서 요구사항 분석부터 유지보수까지의 과정에 발생하는 어려움을 해결하기 위한 체계적인 관리와 효율적 업무 수행을 지원해주는 기술 효과적인 소프트웨어 공학 기술 적용을 위해서는 체계적인 업무 방식 및 흐름의 정의와 이를 적용할 수 있는 프로세스(Process), 전문적 지식을 갖춘 조직 및 인력(People), 정의된 업무 방식과 조직 인력이 효율적으로 운영되기 위한 기반 인프라 기술(Technology)이 3가지 핵심 요소를 갖춰야 한다.  2) 소프트웨어 공학 배경소프트웨어 공학의 변천사는 다음과 같다. 1950년대에 소프트웨어 개발 프로젝트를 위해 하드웨어 공학과 유사한 소프트웨어 공학..
지금까지 써본 언어 중 가장 어지러운 언어 [Arm Assembly] 간단?한 hello world 출력 예제인데.. hello world 출력하는 코드가 아래랑 같다..text_start: .global _start @ sys_write ( fd, pstr, len ) @ r7=4 r0 r1 r2 mov r0, #1 @fd  천천히 코드를 하나하나 뜯어보자, 일단 큼지막하게 .text, _start, .global, msg:, .end로 나눠보자. 섹션크게 데이터 섹션과 코드 섹션으로 나눌 수 있고, 각각 .data, .text로 나뉜다.데이터 섹션에는 프로그램에서 사용하는 데이터 (변수, 상수, 배열, 문자열 등)이 포함되고, .data 혹은 .section .data와 같은 지시문으로 정의된다. 이 섹션에 선언..
년/월/일/시/분/초 에 대한 고찰 이번 카카오 코딩 테스트도 그렇고 이러한 시간을 이용한 문제는 자주 출제되고는 한다. 나는 보통 이런 문제를 풀 때 가장 큰 단위부터 가장 작은 단위로 바꿔준다. 예를 들면 1년을 초로 바꾼다면 1*365*24*60*60이 될 것이다. 이렇게 바꿈으로써 문제 해결이 쉬워지는 문제들이 여럿 있다. 일단 이런 문제가 있다. https://www.acmicpc.net/problem/2525 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net hour,minute=map(int,input().split())..

티스토리툴바