시나위

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 요약 비교 상태를 사용하여 줄 세우기, 위상 정렬 접근 1. 트리 트리를 생성한다음 최상위 노드에서 후위 순회하는 방식으로 접근했다. 이 접근방식을 구현할때 반례가 바로 떠올라 안될거같아서 적당히 구현했다. #define MAX_SIZE 32000 int visit[MAX_SIZE + 1]; // 128kb int parent[MAX_SIZE + 1]; // 128kb void postorder(int index,..

1. 회사 쓸만한 이야기가 없다. 지난주와 별반 다르지 않았다. 추석 이후에 동기들이랑 회식도 있고 야구도 같이 보러갈듯하다. 야구장은 처음 가보는데 괜찮으려나. 2. 미라클 모닝 매일 아침 일찍 일어나 자기개발을 하고 있다. 아침에 일찍 일어나는건 꽤 오래 되었다. 취업한 이후에 전날 회식이 없는 한 네시 반쯤 일어난다. 다들 일찍 일어나면 뭐하냐고 물어보는데 지금까진 딱히 한게 없었다. 늦게 자는 사람이 저녁부터 밤시간에 하는 걸 나는 일어나서 하기때문에 뭐라고 할말이 없다. 조금의 차이가 있다면 일어날 때 조금 개운하다는 것이다. 취업 이후 지금까지 일찍은 일어났지만 아무것도 하지않았는데 그럴거면 오히려 저녁에 깨있는게 낫지 않나 생각이 들었다. 그런 생각이 들어서 출근 전에 공부를 해서 나에게 도..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 요약 N개의 물건으로 가방을 싸는 문제 최대 무게 K를 넘지 않으면서 가방에 든 물건이 최대 가치를 지녀야한다. 접근 1. Greedy 무게가 높고 가치가 높은 순으로 정렬한 뒤에 하나씩 넣으면서 해도 정렬을 한뒤에 풀어도 괜찮은지 고민해봤지만 풀리지 않는 예제가 있어서 바로 넘어갔다. 2. Bruteforce 그 다음 쉬운 방법인 브루트 포스 이다. 모든 물건에 대해서 넣거나 넣지 않거나 모..

11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 요약 수열 A에서 증가 부분 수열 중 합의 최댓값 찾기 접근 1. 규칙찾기 알고리즘 규칙찾기 새로 알게된 것 dp 너무 어려운데..? 전체 코드 #include #include // max #define MAX 1000 using namespace std; int N, answer; int arr[MAX]; int memo[MAX][MAX]; void printMemo(int size) { for (..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 요약 3xN 크기의 벽을 2x1, 1x2의 타일로 채우는 경우의 수 접근 1. 규칙찾기 n이 홀수면 만들수 없음 n이 짝수인 경우 만들수 있음. n= 2: 3개 n= 4: (n = 2인 타일에 n = 2인 타일을 추가하는 경우) + (n=4인 타일을 추가하는 경우, 새로운 타일) 3*3 + 2 개 = 11개 n= 6: (n = 4인 타일에 n = 2인 타일을 추가하는 경우) + (n = 2 인 타일에 n=4인 타일을 추가하는 경우) + (n = 6 인 타일을 추가하는 경우, 새로운 타일) - (중복값 제거) 11*3 + 2 + 2*3 = 33 + 2 + 6 = 41개..

0. 타임라인 8월22일 # 8월23일 #노래추천받습니다 8월24일 #멍청비용 #4극오디오케이블 8월25일 #스터디2주차 #7월관리비 #추석버스예매 8월26일 #노래방 8월27일 #악몽 #아침산책 #싸피강연 #오프라인 8월28일 #피곤 1. 회사 프로젝트에 참여하면서 회의에 참여하게되었다. 회의에 참여해서 느낀바는 전기쪽 지식도 잘 알아야하면서 sw도 잘해야한다는 것이었다. 들으면서 이해가 가지 않는게 많았고 모르는 용어들에 대해서 수첩에 다 적었다. 회의가 끝난 이후부터 모르는 것들에 대해서 인터넷 검색으로 단편적인 지식들을 흡수했고, 지난주부터 보고있던 User Manual을 정독했다. 유저매뉴얼도 업무에 필요한게 있을때 보는게 좋긴한데 아는게 없으니 어디서 부터 봐야할지도 몰라서 정독하고있었다. 팀..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 요약 스도쿠 정답을 찾으면된다. 행과 열, 3X3 안에 1~9가 중복없이 들어가야한다. 접근 1. Brute-force 숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 981 이 된다. O(232) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다. 물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다. 2. Backtracking 백..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 손님들이 주문한 단품 메뉴로 코스요리(조합)를 만든다. 코스 요리는 단품 두개 이 상으로 이루어져있다. 코스 요리의 길이(단품 메뉴의 개수)를 보고 그 중에 가장 많이 선택된 조합을 반환한다. 접근 모든 손님들이 주문한 단품 메뉴로 모든 조합을 만들어야한다. 조합을 만들 때 반복문, 라이브러리, 백트래킹으로 구현할수 있다. 1. 조합만들기 - 반복문 반복문을 중첩해서 사용하면 쉽게 조합을 만들수 있다. 예를 들면 ABCDE에서 3개의 원소를 가지는 조합을 만들기 위해선 다음과 같이 짜면 된다. st..

0. 타임라인 8월15일 #광복절 8월16일 #스터디첫날 #알고리즘스터디 8월17일 #동기회식 8월18일 #스터디 #2일차 8월19일 #대학교동기 #치맥 8월20일 #컨디션난조 8월21일 #대청소 1. 회사 현재도 계속 일을 돕고 배우고 있다. Aurix TriCore 칩을 사용하는데 해당 유저매뉴얼이랑 데이터시트, PMIC에 대한 매뉴얼, 데이터시트를 계속 보고있다. 이해는 잘 가지 않지만 여러번 보다보면 언젠가는 잘 사용할 수 있지않을까. 뭔가 팀에 도움이 되는거 같으면서도 1인분하려면 아직 멀었다고 생각이 든다. 임베디드 관련해선 팀원 분들과 일하는 것도 많지만 인터넷에서도 많은 도움을 받고있다. 최근에 본 블로그는 아래 블로그인데 임베디드 SW이기도 하고 TC275 Lite Kit를 사용해서 내가..

2641번: 다각형그리기 모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 www.acmicpc.net 문제 요약 처음 주어지는 모양수열로 만들어진 도형과 같은 도형이 나오는 수열을 찾는 문제이다. 모양수열은 방향을 가리키는 숫자 (1: 우, 2: 상, 3: 좌, 4: 하)로 이루어진 수열이다. 회전이나 뒤집었을때 같은 도형은 다른 것으로 생각한다. 접근 1. 쉬운 도형을 직접 그려서 규칙 확인 크기가 1인 정사각형의 모양수열을 확인했다. 좌측 상위의 점을 시작점으로 잡았을 때 시계방향으로 도는 모양수열은 1-4-3-2가 된다. 같은 시작점이고 반시계방향인 모양수..