본문 바로가기

Algorithm

 (640)
백준 3613번 Java vs C++ 문제 Java 예찬론자 김동규와 C++ 옹호가 김동혁은 서로 어떤 프로그래밍 언어가 최고인지 몇 시간동안 토론을 하곤 했다. 동규는 Java가 명확하고 에러가 적은 프로그램을 만든다고 주장했고, 동혁이는 Java는 프로그램이 느리고, 긴 소스 코드를 갖는 점과 제네릭 배열의 인스턴스화의 무능력을 비웃었다. 또, 김동규와 김동혁은 변수 이름을 짓는 방식도 서로 달랐다. Java에서는 변수의 이름이 여러 단어로 이루어져있을 때, 다음과 같은 방법으로 변수명을 짓는다. 첫 단어는 소문자로 쓰고, 다음 단어부터는 첫 문자만 대문자로 쓴다. 또, 모든 단어는 붙여쓴다. 따라서 Java의 변수명은 javaIdentifier, longAndMnemonicIdentifier, name, bAEKJOON과 같은 형태이다..
백준 9933번 민균이의 비밀번호 문제 창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다. 파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다. 예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다. 알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다. 민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오. 입..
백준 1764번 듣보잡 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 1. java와 달리 c++은 string객체에 있어서 내용이 같으면 같은 인스턴스로 봄. 2. vector push_back하면 인덱스 배열로 바로 참조 가능. 간단한 문제였지만 더 간단한 문..
5648. [모의 SW 역량테스트] 원자 소멸 시뮬레이션 출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 구조체 배열 초기화는 for문으로 값을 입력시켜서 초기화 시키면 시간이 2배 증가. 따라서 memset사용. 2. 아이디어 -기본적으로 BFS로 구현함. -음수좌표 양수로 치환. -터지는 경우 어떤 지점에 도착했을 때, 같은 시점에 누군가가 도착한 경우 혹은 같은 시점에 그지점이 터져있는 경우 current+1(이동한 후의 current) 와 해당 지점의 current가 일치 할 때 폭파, 폭파되었다는 check를 심어줌. 그리고 그위치..
7673. 영이는 영이 시져시져! 출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do DP 문제 -이유. 값을 누적 저장 불가. -> DFS나 BFS를 통해 누적된 값을 전달하는 방식을 쓰려고 해도 한번의 곱에 최대 10^6씩 곱해지므로 1000번 곱해지면 받아줄 수 있는 자료형이 없다. (최대 10^6000.... ㅎㄷㄷ) 아이디어 1. 0을 만드는 경우를 분석한다 -> 2와 5의 곱 한번으로 0이 하나 만들어진다. 만약 2개의 2와 3개의 5가 곱해진다면 0이 2개 만들어진다. 즉 어떤 곱에 이르렀을 때 , 그 수가 가지고 있는 2와 5의 거듭 제곱의 갯수 중에 최소값 만큼 0이 생성됨. 2. 그렇다면 2와 5를 줄이는 방식으로 가야 한다. 1) 2과 최소인 방향..
1247. [S/W 문제해결 응용] 3일차 - 최적 경로 처음에 다익스트라인가 했다가 크루스칼인가 했다가 문제 자세히 보니 효율적인 경로 찾기 문제가 아니였다. 즉 시간복잡도 측에서 줄여야 하는 문제가 아닌것을 확인. 시간을 C++ 기준 10초나 줬다. 그래서 DFS로 풀어버림. 다익스트라는 어떤 출발점에서 도착점 처음에 다익스트라인가 했다가 크루스칼인가 했다가 문제 자세히 보니 효율적인 경로 찾기 문제가 아니였다. 즉 시간복잡도 측에서 줄여야 하는 문제가 아닌것을 확인. 시간을 C++ 기준 10초나 줬다. 그래서 DFS로 풀어버림. 다익스트라는 어떤 출발점에서 도착점까지 최단거리로 이동하는 것이고 크루스칼은 간선마다 가중치가 존재하는데 도착점이 정해지지 않고 최소비용으로만 연결된 트리를 만들어 내는 것이 목적. 즉 어떤 지점에서 어떤 지점으로의 이동이 목적이..
1953. [모의 SW 역량테스트] 탈주범 검거 출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do BFS로 구현해서 풀었다. => 제한시간이 촉박하다 느끼는 경우 BFS , 메모리가 부족하다 생각되는 경우 DFS 각 파이프 마다 사방의 위치에서 이어질 수 있는 파이프들에 대한 조건을 각각 지정. 예를 들면 1번 파이프의 왼쪽에는 3,4,5,6번 파이프가 연결되지 않으면 이동 불가. 이동이 가능한 경우 카운트를 올려주고 이동한 지점에 대해서는 visit처리를 해줌. 한 지역에 머무름 방지 ( 시간초과 발생) 그리고 time값을 매개변수로 계속 전달하여 이동한 시간이 탈주범에게 주어진 시간과 같아지는 경우에 break시킴 count는 그전에 올려주기 때문에 상관 없음. #includ..
4112. 이상한 피라미드 탐험 출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do BFS로 구현 하였으나 답은 잘 나오는데 1000개의 테스트 케이스에서 시간초과가 발생하였다. 하지만 이 문제는 BFS가 아닌 일반 로직을 구현해서 풀 수 있었다. 시작점이 종료지점보다 위에 존재하는 경우 1) 시작점의 x좌표가 종료점의 x좌표보다 작거나 같다. 2) 시작점의 x좌표가 종료점의 x좌표보다 크다. 시작점이 종료지점보다 아래에 존재하는 경우 1) 시작점의 x좌표가 종료점의 x좌표보다 크거나 같다. 2) 시작점의 x좌표가 종료점의 x좌표보다 작다. 기본적으로 각 케이스의 1번 같은 경우는 시작점과 종료점의 x좌표 차이와 y좌표 차이중 큰 값만큼 시간이 소비된다. 하지만 각..

티스토리툴바